链表实现
链表 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)。
静态链表是另一种实现，将列表用作存储，将数字用作指针。
