Python 数据结构之链表：单向链表，双向链表，循环链表实现。

女爷i 2023-07-25 09:25 16阅读 0赞

# 1. 链表 #

我们在 [Python 序列：列表 (list)，元组（tuple），字符串（str）深入分析（包括扩容和摊销）。][Python _ _list_tuple_str] 和 [Python：栈和队列的 python 列表实现][Python_ python] 中可以看出列表是存在一定问题的：

1.  由于动态数组，底层的数组长度可能会超过实际存储元素的个数，造成空间上的浪费。
2.  我们 append 的平均时间复杂度是 O(1)，但是这是摊销的结果，某一次的时间复杂度最坏为 O(n)。
3.  队列的一般实现，每次出队的时间复杂度是 O(n)

于是就有了另外一种结构，就是链表。链表和列表可以对其中的元素保持一定的顺序，但是实现方式不同：

1.  数组采用一种集中式，一个大的内存区域进行元素的存放。
2.  链表是一种分布式的方法，每个元素是一个节点。每个节点有当前节点自身元素的值（引用方式，也就是存放的是指向真正对象的地址），还有一个下一对象的引用（指向下一对象）。这样链表的元素实际存放在不同的区域，靠着指向来保证遍历和顺序。

# 2. 链表的实现（单链表） #

class Node:
        def __init__(self, val):
            self.val = val
            self.next = None

定义我们的节点，节点中 val 为本节点的值，next 指向下一个节点（如果没有则为空）

class SingleLinkedList:
        def __init__(self, node=None):
            self.head = node
            if node:
                self.size = 1
            else:
                self.size = 0

初始化我们的单链表，简单的提供了两种初始化方法，一种是空的初始化，一种使用一个节点初始化。为了直接返回链表的长度，不必遍历整个链表，因此保存了一个链表长度的变量，时间复杂度为 O(1)。  
注意：如果没有 size 变量，那么求链表的长度的时间复杂度为 O(n)，因为我们只有链表的头结点，我们不知道尾节点（当然你也可以用一个变量来保存，每次操作的时候要考虑尾节点是否变化），因此只能根据头结点的 next 来遍历整个链表，然后计数才能知道链表的长度。  
我们实现的方法有：

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>操作</th> 
   <th>时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>is_empty</td> 
   <td>判断是否为空链表</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>length</td> 
   <td>链表长度</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>add_first</td> 
   <td>在头部添加元素</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>append</td> 
   <td>在尾部添加元素</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>insert_by_position</td> 
   <td>按位置插入</td> 
   <td>O(k)</td> 
  </tr> 
  <tr> 
   <td>remove_by_value</td> 
   <td>删除链表中包含改值的第一个节点</td> 
   <td>O(k)</td> 
  </tr> 
  <tr> 
   <td>search</td> 
   <td>查找某元素</td> 
   <td>O(k)</td> 
  </tr> 
  <tr> 
   <td>travel</td> 
   <td>遍历打印元素</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

其中 k 是第几个节点或位置满足条件。

注意：我们的实现中 append 的复杂度是 O(n)，这是为了和一般的链表实现一致，只有头结点，一个简单的方法降为 O(1) 的操作是，链表中用一个变量保存尾节点的引用。这样只需要尾节点的 next 指向新加入的节点即可。

在上面中，我们发现删除节点：

def remove_by_value(self, val):
        current = self.head
        pre = None
        while current:
            if current.val == val:
                if pre:
                    pre.next = current.next
                else:
                    self.head = current.next
                self.size -= 1
                return
            pre = current
            current = current.next
        print('Not found value!')

需要维护一个 pre 变量指向此元素的上一个元素，因为每个节点只有 next 指向下一节点，并没有指向前一节点，删除的时候要修改上一指针的 next 指向。所以添加了一个辅助节点来指向当前节点的上一节点，这个方法在链表中很常用，这个节点一般叫哨兵节点。为了可以方便的访问之前和之后节点，于是有了双向链表。

# 3. 双向链表的实现 #

class Node:
        def __init__(self, val):
            self.val = val
            self.next = None
            self.pre = None
    
    
    class DoubleLinkedList:
        def __init__(self, node=None):
            self.head = node
            if node:
                self.size = 1
            else:
                self.size = 0
    
        def is_empty(self):
            return self.size == 0
    
        def length(self):
            return self.size
    
        def travel(self):
            current = self.head
            while current:
                print(current.val, end=' ')
                current = current.next
            print()
    
        def add_first(self, val):
            node = Node(val)
            current = self.head
            if current:
                node.next = current
                current.pre = node
                self.head = node
            else:
                self.head = node
            self.size += 1
    
        def append(self, val):
            node = Node(val)
            current = self.head
            if self.head:
                while current.next:
                    current = current.next
                current.next = node
                node.pre = current
            else:
                self.head = node
            self.size += 1
    
        def insert_by_position(self, pos, val):
            if pos < 0 or pos > self.size:
                print('Out of linked list index!')
            elif pos == 0:
                self.add_first(val)
            else:
                count = 0
                node = Node(val)
    
                current = self.head
    
                while current < pos - 1:
                    current = current.next
                    count += 1
    
                node.next = current.next
                node.pre = current
                current.next.pre = node
                current.next = node
                self.size += 1
    
        def remove_by_value(self, val):
            current = self.head
            if current:
                if current.val == val:
                    if current.next is None:
                        self.head = None
                    else:
                        current.next.pre = None
                        self.head = current.next
                    self.size -= 1
                    return
                while current:
                    if current.val == val:
                        current.pre.next = current.next
                        current.next.pre = current.pre
                        self.size -= 1
                        return
                    else:
                        current = current.next
                print('Not found value!')
            else:
                print('Not found value!')
    
        def search(self, val):
            current = self.head
            while current:
                if current.val == val:
                    return True
                else:
                    current = current.next
            return False
    
    
    if __name__ == "__main__":
        pass

class Node:
        def __init__(self, val):
            self.val = val
            self.next = None
            self.pre = None

双向链表的节点相对于担心链表的节点多了一个 pre 变量指向上一节点（如果是头结点，则为空）。

# 4. 循环链表的实现： #

class Node:
        def __init__(self, val):
            self.val = val
            self.next = None
    
    
    class SingleLinkedList:
        def __init__(self, node=None):
            self.head = node
            if node:
                self.size = 1
            else:
                self.size = 0
    
        def is_empty(self):
            return self.size == 0
    
        def length(self):
            return self.size
    
        def add_first(self, val):
            node = Node(val)
            if self.is_empty():
                self.head = node
                node.next = self.head
            else:
                node.next = self.head
                current = self.head
                while current.next != self.head:
                    current = current.next
                current.next = node
                self.head = node
            self.size += 1
    
        def append(self, val):
            node = Node(val)
            current = self.head
            if current is None:
                self.head = node
                node.next = self.head
            else:
                while current.next != self.head:
                    current = current.next
                current.next = node
                node.next = self.head
            self.size += 1
    
        def insert_by_position(self, pos, val):
            if pos > self.size or pos < 0:
                print('Out of linked list index!')
            elif pos == 0:
                self.add_first(val)
            else:
                node = Node(val)
                count = 0
                pre = self.head
                while count < (pos-1):
                    pre = pre.next
                    count = count + 1
    
                node.next = pre.next
                pre.next = node
                self.size += 1
    
        def remove_by_value(self, val):
            if self.is_empty():
                print('Not found value!')
                return
            current = self.head
            pre = None
    
            if current.val == val:
                if current.next != self.head:
                    while current.next != self.head:
                        current = current.next
                    current.next = self.head.next
                    self.head = self.head.next
                else:
                    self.head = None
                self.size -= 1
            else:
                pre = self.head
                while current.next != self.head:
                    if current.val == val:
                        pre.next = current.next
                        self.size -= 1
                        return
                    else:
                        pre = current
                        current = current.next
                if current.val == val:
                    pre.next = current.next
                    self.size -= 1
            print('Not found value!')
    
        def search(self, val):
            if self.is_empty():
                return False
            current = self.head
            if current.val == val:
                return True
            while current.next != self.head:
                current = current.next
                if current.val == val:
                    return True
            return False
    
        def travel(self):
            current = self.head
            for _ in range(self.size):
                print(current.val, end=' ')
                current = current.next
            print()
    
    
    if __name__ == '__main__':
        pass

循环链表值得是链表尾节点的 next 不是指向 None，而是指向头结点。最大的改变就是遍历的时候，尾节点的判断条件不是 next == None，而是 next == self.head。另外也可以加一个计数变量来比较和链表长度的关系。

# 5. 基于链表的栈和队列 #

1.  栈：前面提到可以增加尾节点变量使得操作链头链尾的时间复杂度变为 O(1)，因此栈的实现就很自然了。
2.  队列：同样的，假如有尾节点变量可以很简单地实现。时间复杂度都是 O(1)。

# 6. 链表和列表的对比： #

## 6.1 列表的优点： ##

1.  基于整数索引访问一个元素的时间复杂度为 O(1)，一般的链表只能从头开始计数遍历。
2.  大部分操作列表和链表时间复杂度一样，但是常数项更小。比如添加元素，链表涉及节点实例化，节点之间指向改变等。而列表只需要添加元素即可（不考虑底部数组扩容）。
3.  列表需要的存储更少：这可能有悖于直觉，因为列表是基于动态数组，底层数组可能没有完全使用，但是我们知道列表和链表都是引用结构的，所以存储的都是地址，地址指向的对象大小之和是一样的。对于列表，长度为 n，最坏情况，底层数组为 2n (假设刚刚扩容，且为 2 倍扩容)。对于链表，由于每个节点除了存放本节点元素的引用还要存放下一元素的引用，因此长度为 n 的链表需要至少存放 2n 个引用。一个最多，一个至少。
4.  查找速度快 （已排序的列表二分查找 logn）

## 6.2 链表的优点： ##

1.  链表提供了最坏的时间界限：以保存了尾节点的链表的 append 操作为例：append 操作的最坏情况也只是 O(1)，而列表是平均摊销为 O(1)，最坏情况为 O(n)（扩容的时候）。再就是头部元素的删除，列表的时间复杂度为 O(n)，而链表为 O(1)——栈和队列的实现上表现很明显。
2.  和列表不一样，申请内存的时候不一定要一块连续的内存空间。
3.  插入删除简单，只需要改变节点之间指向，而列表需要移动元素。

[Python _ _list_tuple_str]: https://editor.csdn.net/md/?articleId=105470849
[Python_ python]: https://editor.csdn.net/md/?articleId=105483607