让GPT实现了一下单链表、单循环链表和双向链表，大体看一看差异。
首先是两个节点基类和链表基类，双向节点继承了基础的单项节点。链表基类则将空链表判断、长度判断、搜索写入基类：
class Node():
def __init__(self, item):
super().__init__(item)
self.item = item
self.next = None
# 双向节点
class DoubleNode(Node):
def __init__(self, item):
super().__init__(item) # 调用父类的__init__方法。
self.prev = None
self.next = None
class BaseLinkedList:
"""链表基类：封装通用方法"""
def __init__(self):
self._head = None
def is_empty(self):
return self._head is None
def length(self):
count = 0
for _ in self: # 用迭代器遍历
count += 1
return count
def search(self, item):
for node in self:
if node.item == item:
return True
return False
def __iter__(self):
"""迭代器方法，子类必须重写"""
raise NotImplementedError
# 这儿就是一个提醒，意思是父类没有实现这个方法我们具体来看看三个链表实现上的差异：
| 单向链表 | 单向循环链表 | 双向链表 |
| class SingleLinkedList(BaseLinkedList): def __init__(self): super().__init__() | class SingleCircularLinkedList(SingleLinkedList): | class DoubleLinkedList(BaseLinkedList): def __init__(self): super().__init__() |
| def __iter__(self): cur = self._head while cur: yield cur cur = cur.next | def __iter__(self): “””循环链表迭代器””” if self.is_empty(): return cur = self._head while True: yield cur cur = cur.next if cur == self._head: # 回到起点就停 break | def __iter__(self): cur = self._head while cur: yield cur cur = cur.next |
| def add(self, item): node = Node(item) node.next = self._head self._head = node | def add(self, item): node = Node(item) if self.is_empty(): self._head = node node.next = self._head else: cur = self._head while cur.next != self._head: cur = cur.next node.next = self._head self._head = node cur.next = self._head | def add(self, item): node = DoubleNode(item) node.next = self._head if self._head: self._head.prev = node self._head = node |
| def append(self, item): node = Node(item) if self.is_empty(): self._head = node else: cur = self._head while cur.next: cur = cur.next cur.next = node | def append(self, item): node = Node(item) if self.is_empty(): self._head = node node.next = self._head else: cur = self._head while cur.next != self._head: cur = cur.next cur.next = node node.next = self._head | def append(self, item): node = DoubleNode(item) if self.is_empty(): self._head = node else: cur = self._head while cur.next: cur = cur.next cur.next = node node.prev = cur |
| def insert(self, pos, item): if pos <= 0: self.add(item) elif pos >= self.length(): self.append(item) else: node = Node(item) cur = self._head for _ in range(pos – 1): cur = cur.next node.next = cur.next cur.next = node | def insert(self, pos, item): if pos <= 0: self.add(item) elif pos >= self.length(): self.append(item) else: node = DoubleNode(item) cur = self._head for _ in range(pos – 1): cur = cur.next node.next = cur.next node.prev = cur cur.next.prev = node cur.next = nodedef remove(self, item): cur = self._head pre = None while cur: if cur.item == item: if pre is None: self._head = cur.next else: pre.next = cur.next return True pre = cur cur = cur.next return False | |
| def remove(self, item): cur = self._head pre = None while cur: if cur.item == item: if pre is None: self._head = cur.next else: pre.next = cur.next return True pre = cur cur = cur.next return False | def remove(self, item): if self.is_empty(): return False cur = self._head pre = None while True: if cur.item == item: if cur == self._head: # 找到尾节点 tail = self._head while tail.next != self._head: tail = tail.next if self._head == self._head.next: self._head = None else: self._head = self._head.next tail.next = self._head else: pre.next = cur.next return True pre = cur cur = cur.next if cur == self._head: break return False | def remove(self, item): cur = self._head while cur: if cur.item == item: if cur.prev: cur.prev.next = cur.next else: self._head = cur.next if cur.next: cur.next.prev = cur.prev return True cur = cur.next return False |
第一行定义，单向链表和双向链表都继承BaseLinkedList，而单向循环链表继承单项链表。
第二行迭代器，单向和双向链表一致，而单向循环链表首位相连，循环时候需要注意，避免死循环。
第三行add，链表头插入，单向链表常规操作，双向链表考虑一下头指针，单向循环列表需要最后一个元素的指针指回到新的链表，所以需要循环找最后一个元素。
第四行append，链表尾部插入，单向链表常规操作，双向链表类似，单向循环链表也就是需要特殊判断下末尾位置。
第五行insert，三个表大差不差。
第五行remove剔除元素，考虑情况略多一些，其他类似。
完整代码
# 单链表个人测试
# 为了进一步学习使用下python继承相关的面向对象特点
# 红茶半两酒
# 2025/08/08
# -*- coding: utf-8 -*-
# ========== 节点基类 ==========
# 单向节点
class Node():
def __init__(self, item):
super().__init__(item)
self.item = item
self.next = None
# 双向节点
class DoubleNode(Node):
def __init__(self, item):
super().__init__(item) # 调用父类的__init__方法。
self.prev = None
self.next = None
# ========== 链表基类 ==========
class BaseLinkedList:
"""链表基类：封装通用方法"""
def __init__(self):
self._head = None
def is_empty(self):
return self._head is None
def length(self):
count = 0
for _ in self: # 用迭代器遍历
count += 1
return count
def search(self, item):
for node in self:
if node.item == item:
return True
return False
def __iter__(self):
"""迭代器方法，子类必须重写"""
raise NotImplementedError
# 这儿就是一个提醒，意思是父类没有实现这个方法
# ========== 单向链表 ==========
class SingleLinkedList(BaseLinkedList):
def __init__(self):
super().__init__()
def __iter__(self):
cur = self._head
while cur:
yield cur
# 类似于return cur，但是可以保存记忆，同时可以节省内存
cur = cur.next
def add(self, item):
node = Node(item)
node.next = self._head
self._head = node
def append(self, item):
node = Node(item)
if self.is_empty():
self._head = node
else:
cur = self._head
while cur.next:
cur = cur.next
cur.next = node
def insert(self, pos, item):
if pos <= 0:
self.add(item)
elif pos >= self.length():
self.append(item)
else:
node = Node(item)
cur = self._head
for _ in range(pos - 1):
cur = cur.next
node.next = cur.next
cur.next = node
def remove(self, item):
cur = self._head
pre = None
while cur:
if cur.item == item:
if pre is None:
self._head = cur.next
else:
pre.next = cur.next
return True
pre = cur
cur = cur.next
return False
# ========== 单向循环链表 ==========
class SingleCircularLinkedList(SingleLinkedList):
def __iter__(self):
"""循环链表迭代器"""
if self.is_empty():
return
cur = self._head
while True:
yield cur
cur = cur.next
if cur == self._head: # 回到起点就停
break
def append(self, item):
node = Node(item)
if self.is_empty():
self._head = node
node.next = self._head
else:
cur = self._head
while cur.next != self._head:
cur = cur.next
cur.next = node
node.next = self._head
def add(self, item):
node = Node(item)
if self.is_empty():
self._head = node
node.next = self._head
else:
cur = self._head
while cur.next != self._head:
cur = cur.next
node.next = self._head
self._head = node
cur.next = self._head
def remove(self, item):
if self.is_empty():
return False
cur = self._head
pre = None
while True:
if cur.item == item:
if cur == self._head:
# 找到尾节点
tail = self._head
while tail.next != self._head:
tail = tail.next
if self._head == self._head.next:
self._head = None
else:
self._head = self._head.next
tail.next = self._head
else:
pre.next = cur.next
return True
pre = cur
cur = cur.next
if cur == self._head:
break
return False
# ========== 双向链表 ==========
class DoubleLinkedList(BaseLinkedList):
def __init__(self):
super().__init__()
def __iter__(self):
cur = self._head
while cur:
yield cur
cur = cur.next
def add(self, item):
node = DoubleNode(item)
node.next = self._head
if self._head:
self._head.prev = node
self._head = node
def append(self, item):
node = DoubleNode(item)
if self.is_empty():
self._head = node
else:
cur = self._head
while cur.next:
cur = cur.next
cur.next = node
node.prev = cur
def insert(self, pos, item):
if pos <= 0:
self.add(item)
elif pos >= self.length():
self.append(item)
else:
node = DoubleNode(item)
cur = self._head
for _ in range(pos - 1):
cur = cur.next
node.next = cur.next
node.prev = cur
cur.next.prev = node
cur.next = node
def remove(self, item):
cur = self._head
while cur:
if cur.item == item:
if cur.prev:
cur.prev.next = cur.next
else:
self._head = cur.next
if cur.next:
cur.next.prev = cur.prev
return True
cur = cur.next
return False
# ========== 测试 ==========
if __name__ == "__main__":
print("=== 单向链表 ===")
sll = SingleLinkedList()
sll.append(1)
sll.append(2)
sll.add(0)
for node in sll:
print(node.item)
print("\n=== 单向循环链表 ===")
scll = SingleCircularLinkedList()
scll.append(1)
scll.append(2)
scll.add(0)
for node in scll:
print(node.item)
print("\n=== 双向链表 ===")
dll = DoubleLinkedList()
dll.append(1)
dll.append(2)
dll.add(0)
for node in dll:
print(node.item)