链表实现

链表 v0：最简单的单链表

class Node:  
    def __init__(self, data=None, next_pointer: "Node" = None):  
        self.data = data  
        self.next_pointer = next_pointer  
  
  
class LinkedList:  
    def __init__(self, next_pointer: Node | None = None):  
        self.next_pointer = next_pointer  
  
  
if __name__ == '__main__':  
    x = LinkedList()  
    node1 = Node(1)  
    node2 = Node(2)  
    node3 = Node(3)  
    node4 = Node(4)  
    node5 = Node(5)  
  
    x.next_pointer = node1  
    node1.next_pointer = node2  
    node2.next_pointer = node3  
    node3.next_pointer = node4  
    node4.next_pointer = node5  
  
    print(x.next_pointer.data)  
    print(node3.next_pointer.data)
    # 1
    # 4

定义了两个类，节点类Node和列表本身的LinkedList。

LinkedList只做了一件事，作为表头（头指针）链接到第一个节点Node。

链表 v1: 实现append方法

添加新节点有：

头插法（Head Insert）
尾插法（Tail Insert）

可以同时提供这两种方法append和appendleft，如同deque。

v1版本，先来实现尾插法。并且，为了能够更加清楚地看到append和节点信息，这一版本还实现了__repr__ 方法：


class Node:  
    def __init__(self, data):  
        self.data = data  
        self.next_ = None  
  
    def __repr__(self):  
        return f'{self.__class__.__name__}({self.data})'  
  
  
class LinkedList:  
    def __init__(self):  
        self.head = None  
  
    def append(self, data):  
        if self.head:  
            current = self.head  
            while current.next_:  
                current = current.next_  
            current.next_ = Node(data)  
        else:  
            self.head = Node(data)  
  
    def __repr__(self):  
        nodes = []  
        current = self.head  
        count = 0  
  
        while current:  
            nodes.append(repr(current))  
            current = current.next_  
            count += 1  
  
        return f'{self.__class__.__name__}({nodes})'  
  
  
  
if __name__ == '__main__':  
    x = LinkedList()  
    x.append(1)  
    x.append(2)  
    x.append(3)  
    print(x)
    # LinkedList(['Node(1)', 'Node(2)', 'Node(3)'])

链表 v2：双向链表 + 保存尾节点


class Node:  
    def __init__(self, data, prev=None, next_=None):  
        self.data = data  
        self.prev = prev  
        self.next_ = next_  
  
    def __repr__(self):  
        return f'{self.__class__.__name__}({self.data})'  
  
  
class LinkedList:  
    def __init__(self):  
        self.head = None  
        self.tail = None  
  
    def append(self, data):  
        if self.tail:  
            node = Node(data, prev=self.tail)  
            self.tail.next_ = node  
            self.tail = node  
        else:  
            node = Node(data)  
            self.head = node  
            self.tail = node  
  
    def __repr__(self):  
        nodes = []  
        current = self.head  
        count = 0  
  
        while current:  
            nodes.append(repr(current))  
            current = current.next_  
            count += 1  
  
        return f'{self.__class__.__name__}({nodes})'  
  
  
  
if __name__ == '__main__':  
    x = LinkedList()  
    x.append(1)  
    x.append(2)  
    x.append(3)  
    print(x)

链表 v3: 静态链表

通过一个列表来保存数据节点，而数据节点上的prev和next都是数字（代表索引下标），通过读取数字来找到相应的节点位置，实现相同的指针效果。

  
class Node:  
    def __init__(self, data, prev=None, next_=None):  
        self.data = data  
        self.prev = prev  
        self.next_ = next_  
  
    def __repr__(self):  
        return f'{self.__class__.__name__}({self.data},{self.prev},{self.next_})'  
  
  
class StaticLinkedList:  
    def __init__(self):  
        self._nodes = []  
        self.head = None  
        self.tail = None  
  
    def append(self, data):  
        if self._nodes:  
            node = Node(data, prev=self.tail)  
  
            self._nodes[self.tail].next_ = len(self._nodes)  
            self.tail = len(self._nodes)  
  
            self._nodes.append(node)  
  
        else:  
            node = Node(data)  
            self._nodes.append(node)  
            self.head = 0  
            self.tail = 0  
  
    def __repr__(self):  
        return f'{self._nodes}'  
  
  
if __name__ == '__main__':  
    x = StaticLinkedList()  
    x.append('a')  
    x.append('b')  
    x.append('c')  
    print(x)

链表实现总结

通过最简单的方式实现单链表，慢慢完善。

通过实现特殊方法，例如__repr__ ，更加Pythonic。

next是内置函数的名称，为了避免重名，通常的做法是在后面加一个下划线（next_）。

通过保存头尾节点，使得append或appendleft方法的时间复杂度变为O(1)。

静态链表是另一种实现，将列表用作存储，将数字用作指针。

007 链表