python基础综合：链表

心已赠人 2022-11-29 03:06 276阅读 0赞

### 文章目录 ###

*  导读
 *  链表结构复习
 *  \`Python\`对比预习
 *  从节点的定义开始编码
 *  从链表的功能开始完善
 *  全自动构造链表
 *  删除节点
 *  模块化
 *   *  Node.py
     *  Link.py
     *  linklist.csv
     *  linklist.py（主文件）

# 导读 #

**因为研究生生涯开始了，所以需要暂时停掉`Java`的学习，开始使用`Python`的学习和实践了。于是花了一个小时从完全没学过到实现了最基础的单链表。这里就记录一下。**

# 链表结构复习 #

首先我们回顾链表由什么构成。在`C`语言中，对链表的定义就是：

> 链表是一种动态数据结构。它主要是利用动态内存分配、使用结构体并配合之镇来实现的一种数据结构。
> 
> ——摘自《C语言程序设计（第三版）》苏小红、王宇颖、孙志岗等编著

也就是说，链表有以下几个特点：

*  是类似数组的链式结构
 *  内存分配并不像数组一样完全连续
 *  每个节点使用结构体，每个节点也就有了更高的自由度和更大的存储量
 *  下一个节点的位置保存在上一个节点中

# `Python`对比预习 #

复习了链表之后，让我们再看看`Python`语言相对于`C`语言和`Java`有什么不同：

*  不需要显式声明`private`、`protected`和`public`
 *  对象名直接对应对象的地址，这一点和`Java`非常相似
 *  没有括号限制函数体，直接用缩进表示
 *  `None`对应`C`语言和`Java`的`null`
 *  `self`代替了`C`语言和`Java`的`this`指针
 *  魔法函数`__init__`直接定义了结构体的属性构成，而不需要显式定义结构体具体有哪些属性

主要就是这些了。具体的细节我们遇到了再去查[**菜鸟教程**][Link 1]就好了。当然，如果能够直接查[`Python`][Python]官方文档更好，毕竟都贴心地给出了中文版（*但是点进去每个函数的解释还是**英文**，而且没有实例*）。

# 从节点的定义开始编码 #

那么，为了先熟悉`Python`的语法，我们先来个小小的结构体试试水：

# -*- coding: UTF-8 -*-
    # 链表节点
    class Node:
      def __init__(self, data, next, index):
        self.data = data
        self.next = next
        self.index = index
        pass
      pass
    
    # 测试节点
    node = Node(0, None, 0)
    print(node.data)

当然，没有悬念，输出`0`。

第一行首先是确认字符编码。默认是`UTF-8`，根据需要可以更换成别的；其次是使用`__init__`函数定义一个具有三个属性的类作为结构体；最后的pass则是占位符，表示一个域的结束，相当于`}`。因为`Python`直接使用缩进表示是否结束，所以这个仅仅作为个人习惯出现在这里。

# 从链表的功能开始完善 #

既然我们完成了节点的构造，那么我们一口气把整个链表攻下来吧！

# 链表
    class Link:
      # 初始化 / 不需要参数，自带空的头节点
      def __init__(self):
        self.head = None
        self.length = 0
        pass
      # 尾插法插入数据
      def insert_tail(self, index, data):
        # 当尾节点为空时，使用头插法确定尾节点
        if self.tail is None:
          self.insert_head(index, data)
          pass
        # 在尾节点非空时往后接节点
        else:
          node = Node(data, None, index)
          self.tail.next = node
          self.tail = node
          pass
        pass
      # 头插法插入数据
      def insert_head(self, index, data):
        node = Node(data, self.head, index)
        self.head = node
        self.length += 1
        # 当只有一个元素的时候，确定尾节点
        if self.length == 1:
          self.tail = node
          pass
        pass
      # 输出链表 / 从头开始顺序输出
      def output(self):
        node = self.head
        while node is not None:
          print(f'{node.index}: {node.data}', end = ' ')
          node = node.next
          pass
        print()
        pass
      pass
    
    link = Link()
    link.insert_head(1, 2)
    link.insert_tail(3, 4)
    link.output()

在这里的`self`关键字在**函数体内**就是**作为`this`指针**使用，而作为**参数**出现的时候就是声明该函数是一个**成员函数**。后面有一句：

print(f'{node.index}: {node.data}', end = ' ')

这是`Python`3.6以后的新特性，使用`f`直接将字符串格式化，另外使用`end`规定输出结尾是空格而不是默认的换行结尾。

于是，这次的输出就是：`1:2 3:4`。

# 全自动构造链表 #

但是这还差一个输入。不想一个字一个字输入的我直接定义了一个随机生成的函数，让链表自己随便生成什么东西。

# 文件开头加上：
    import random
    LETTERS = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    LETTERS_LEN = len(LETTERS)
    
    # 在Link类中添加成员函数
    # 随机生成链表
    def random_link(self):
      size = random.randint(0, 20)
      for i in range(0, size):
        self.insert_tail(i + 1, LETTERS[random.randint(0, LETTERS_LEN - 1)])
        pass
      pass
    
    # 全自动生成
    if __name__ == '__main__':
      link = Link()
      link.random_link()
      link.output()
      pass

于是每次编译输出都有完全不一样的结果。

好了，到这里构造链表就没有什么大问题了。

# 删除节点 #

接下来就是很恼人的删除节点了。和`C++`一样，可以直接使用`del`命令显式删除对象。值得一提的是，这里显式删除之后只是将内存标记为“**可使用**”，该部分内存并没有被回收。之后`GC`会过来打扫的。

为了能够保持数组每次都是一致的，方便查看位置，这里添加了文件读取，能够在每次运行的时候从`linklist.csv`中读取一模一样的数据。

数据文件`linklist.csv`：

1
    2
    3
    10
    11
    a
    b
    3
    1000
    7
    p
    q
    h
    @
    !
    ,
    >
    shift

然后是读取文件并解决`readline`方法读取时最后的`\n`误读的情况：

# 读取固定的链表
    def read_file(self, filepath):
      index = 1
      with open(filepath, 'r') as lines:
        for line in lines:
          self.insert_tail(index, line.rstrip('\n'))
          index += 1
          pass
        pass
      pass

接着是删除某个位置的节点。这里虽然没有难点，但是很难在细节上保持平衡。需要考虑以下几种情况：

*  链表**没有节点**
 *  链表**有且仅有**一个节点
 *  中间**任意位置**删除
 *  要删除的是**第一个元素**
 *  要删除的是**最后一个元素**

如果面面俱到，代码一定会纷繁复杂。所以我们需要根据这些非常神奇的地方巧妙避雷：

*  如果链表没有节点，**直接结束**
 *  如果链表仅一个节点，删除时需要同时解除`head`指针、`tail`指针，**避免指针指了个寂寞**，然后一脸哀怨的给你报了个错
 *  在删除的时候，使用临时指针`node`指向`head`指针或者`tail`指针，并删除`node`指针的时候，你会发现`head`和`tail`实际指向的地址依然存在原有的实例对象。所以实际步骤应当是**先重置原先指向需要删除地址的指针，再删除临时指针**
 *  删除的时候需要在最后修改链表长度，避免下次使用的时候**索引超限**

# 使用索引删除节点
    def delete_node_by_index(self, index):
      # 没有节点
      if self.head is None:
        return
        pass
      # 删除头
      elif index == 1:
        node = self.head
        self.head = self.head.next
        del node
        # 检查是不是只有这个节点
        # 如果无视tail，head将会为None而tail保持原样
        if self.head is None:
          self.tail = self.head
          pass
        pass
      # 中间任意位置删除
      else:
        node = self.get_node(index - 1)
        temp = node.next
        if temp is self.tail:
          node.next = None
          self.tail = node
          del temp
          pass
        else:
          node.next = temp.next
          del temp
          pass
        pass

然后我们来测试一下：

# 测试删除是否成功
    if __name__ == '__main__':
      link = Link()
      link.read_file('/home/sakebow/python/linklist/linklist.csv')
      link.delete_node_by_index(link.length)
      link.output()
      pass

这里要强调的是`read_file`命令需要**完整的绝对路径**，否则无法读取文件。

当然，很完美地删掉了最后一个元素：

1: 1 2: 2 3: 3 4: 10 5: 11 6: a 7: b 8: 3 9: 1000 10: 7 11: p 12: q 13: h 14: @ 15: ! 16: , 17: >

接着我们再来完善匹配所有项的方法：

# 匹配内容删除节点
    def delete_node_by_data(self, data):
      # 强行改为有头节点的链表 / 内容随意，仅需保证next指向head
      node = Node('a', self.head, 0)
      # 保持标识，最后需要删除
      # 如果head移动了也不要紧，node将会控制下一跳的位置
      stay_head = node
      # 游标，规定temp为必删项，node为上一项
      temp = self.head
      # 遍历链表
      while temp is not None:
        # 如果要删第一个
        if temp is self.head and temp.data == data:
          # 先重置
          node.next = temp.next
          # 检查tail
          if temp is self.tail:
            self.tail = self.head = node.next
            pass
          # 再删除
          del temp
          # 因为下次循环依然需要使用temp，所以重置为node下一跳
          temp = node.next
          # 修改长度
          self.length -= 1
          pass
        # 中间任意项删除
        # 原理同上
        elif temp is not self.head and temp.data == data:
          node.next = temp.next
          if temp is self.tail:
            self.tail = node
            pass
          del temp
          temp = node.next
          self.length -= 1
          pass
        # 如果不匹配，全部下一跳，且长度不变
        else:
          temp = temp.next
          node = node.next
        pass
      # 最终删除辅助节点
      del stay_head
      pass

那我们来测试一下：

if __name__ == '__main__':
      link = Link()
      link.read_file('/home/sakebow/python/linklist/linklist.csv')
      # 因为数据集里面3出现了两次，所以选择3
      link.delete_node_by_data('3')
      link.output()
      pass

当然，最终结果把两个3全部删掉了：

1: 1 2: 2 4: 10 5: 11 6: a 7: b 9: 1000 10: 7 11: p 12: q 13: h 14: @ 15: ! 16: , 17: > 18: shift

也没有问题！

当然你也可以使用各种各样的数据测试。就算是60万行数据也能用 1 ′ 3 2 ′ ′ 1'32'' 1′32′′秒给出答案。（*实际测量可能和电脑运算能力有误差*）

总之，我认为是相当成功的。如果百万级甚至以上的数据量，如果使用多线程、优化数据结构也是能够解决相当一部分问题的。

# 模块化 #

最后，为了代码简洁、项目结构清晰，我们将各个部分拆开。

所以这里就总结性地贴上各个部分的文件内容：

## Node.py ##

# 链表节点
    class Node:
      def __init__(self, data, next, index):
        self.data = data
        self.next = next
        self.index = index
        pass
      pass

## Link.py ##

from Node import *
    # 链表
    class Link:
      # 初始化 / 不需要参数，自带空的头节点
      def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0
        pass
    
      # 尾插法插入数据
      def insert_tail(self, index, data):
        if self.tail is None:
          self.insert_head(index, data)
        else:
          node = Node(data, None, index)
          self.tail.next = node
          self.tail = node
          self.length += 1
        pass
      
      # 头插法插入数据 
      def insert_head(self, index, data):
        node = Node(data, self.head, index)
        self.head = node
        self.length += 1
        # 当只有一个元素的时候，确定尾节点
        if self.length == 1:
          self.tail = node
          pass
        pass
      
      # 输出链表
      def output(self):
        if self.head is None:
          print('Nothing')
          return
          pass
        else:
          node = self.head
          while node is not None:
            print(f'{node.index}: {node.data}', end=' ')
            node = node.next
            pass
          print()
          pass
        pass
      
      # 随机生成链表
      def random_link(self):
        size = random.randint(0, 20)
        for i in range(0, size):
          self.insert_tail(i + 1, LETTERS[random.randint(0, LETTERS_LEN - 1)])
          pass
        pass
      
      # 读取固定的链表
      def read_file(self, filepath):
        index = 1
        with open(filepath, 'r') as lines:
          for line in lines:
            self.insert_tail(index, line.rstrip('\n'))
            index += 1
            pass
          pass
        pass
      
      # 通过索引获得指定节点
      def get_node(self, index):
        node = self.head
        for i in range(1, index):
          node = node.next
          pass
        pass
        return node
      
      # 匹配内容删除节点
      def delete_node_by_data(self, data):
        # 强行改为有头节点的链表
        node = Node('a', self.head, 0)
        # 保持标识，最后需要删除
        stayHead = node
        # 游标，规定temp为必删项，node为上一项
        temp = self.head
        while temp is not None:
          if temp is self.head and temp.data == data:
            node.next = self.head = temp.next
            if temp is self.tail:
              self.tail = self.head = node.next
              pass
            del temp
            temp = node.next
            self.length -= 1
            pass
          elif temp is not self.head and temp.data == data:
            node.next = temp.next
            if temp is self.tail:
              self.tail = node
              pass
            del temp
            temp = node.next
            self.length -= 1
            pass
          else:
            temp = temp.next
            node = node.next
          pass
        del stayHead
        pass
      
      # 使用索引删除节点
      def delete_node_by_index(self, index):
        if self.head is None:
          return
          pass
        elif index == 1:
          node = self.head
          self.head = self.head.next
          if self.head is None:
            self.tail = self.head
            pass
          pass
          del node
        else:
          node = self.get_node(index - 1)
          temp = node.next
          if temp is self.tail:
            node.next = None
            self.tail = node
            del temp
            pass
          else:
            node.next = temp.next
            del temp
          pass
        pass
      pass

## linklist.csv ##

由于文件非常大，一共22932行数据，所以我放到了`GitHub`上，大家可以[点击我的`GitHub`][GitHub]下载完整文件。

## linklist.py（主文件） ##

# -*- coding: UTF-8 -*-
    import random
    from Link import *
    
    LETTERS = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    LETTERS_LEN = len(LETTERS)
    
    if __name__ == '__main__':
      link = Link()
      link.read_file('/home/sakebow/python/linklist/linklist.csv')
      # link.delete_node_by_index(link.length)
      link.delete_node_by_data('3')
      link.output()
      pass

[Link 1]: https://www.runoob.com/python3/python3-tutorial.html
[Python]: https://docs.python.org/zh-cn/3/
[GitHub]: https://github.com/sakebow/python-study/tree/master/linklist