链表是一种常见的数据结构，用于存储一系列元素。与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针连接。Python 中并没有内置的链表类型，但可以通过类或结构体来实现链表。 ### 单向链表 单向链表由节点组成，每个节点包含两个部分：数据和指向下一个节点的引用。以下是单向链表的实现方式： #### 节点类 ```python class Node: def __init__(self, data): self.data = data self.next = None ``` #### 链表类 ```python class LinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last_node = self.head while last_node.next: last_node = last_node.next last_node.next = new_node def prepend(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node def insert_after(self, prev_node, data): if not prev_node: raise ValueError("Previous node cannot be None") new_node = Node(data) new_node.next = prev_node.next prev_node.next = new_node def delete(self, key): current = self.head previous = None found = False while current and not found: if current.data == key: found = True else: previous = current current = current.next if current is None: return if previous is None: self.head = current.next else: previous.next = current.next def search(self, key): current = self.head found = False while current and not found: if current.data == key: found = True else: current = current.next return found def display(self): current = self.head while current: print(current.data, end=" -> ") current = current.next print("None") ``` ### 使用示例 以下是如何使用上述链表类的示例： ```python # 创建链表实例 llist = LinkedList() # 添加节点 llist.append(1) llist.append(2) llist.append(3) # 显示链表 llist.display() # 输出: 1 -> 2 -> 3 -> None # 在头部添加节点 llist.prepend(0) llist.display() # 输出: 0 -> 1 -> 2 -> 3 -> None # 插入节点 prev_node = llist.head.next # 指向节点 1 llist.insert_after(prev_node, 1.5) llist.display() # 输出: 0 -> 1 -> 1.5 -> 2 -> 3 -> None # 删除节点 llist.delete(1.5) llist.display() # 输出: 0 -> 1 -> 2 -> 3 -> None # 搜索节点 print(llist.search(2)) # 输出: True print(llist.search(4)) # 输出: False ``` ### 双向链表 双向链表与单向链表类似，但每个节点包含两个指针：一个指向前一个节点，另一个指向后一个节点。以下是双向链表的实现方式： #### 节点类 ```python class Node: def __init__(self, data): self.data = data self.prev = None self.next = None ``` #### 链表类 ```python class DoublyLinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last_node = self.head while last_node.next: last_node = last_node.next last_node.next = new_node new_node.prev = last_node def prepend(self, data): new_node = Node(data) new_node.next = self.head if self.head: self.head.prev = new_node self.head = new_node def insert_after(self, prev_node, data): if not prev_node: raise ValueError("Previous node cannot be None") new_node = Node(data) new_node.next = prev_node.next prev_node.next = new_node new_node.prev = prev_node if new_node.next: new_node.next.prev = new_node def delete(self, key): current = self.head while current: if current.data == key: if current.prev: current.prev.next = current.next else: self.head = current.next if current.next: current.next.prev = current.prev return current = current.next def display_forward(self): current = self.head while current: print(current.data, end=" <-> ") current = current.next print("None") def display_backward(self): current = self.head while current and current.next: current = current.next while current: print(current.data, end=" <-> ") current = current.prev print("None") ``` ### 使用示例 以下是如何使用上述双向链表类的示例： ```python # 创建链表实例 dllist = DoublyLinkedList() # 添加节点 dllist.append(1) dllist.append(2) dllist.append(3) # 显示链表 dllist.display_forward() # 输出: 1 <-> 2 <-> 3 <-> None # 在头部添加节点 dllist.prepend(0) dllist.display_forward() # 输出: 0 <-> 1 <-> 2 <-> 3 <-> None # 插入节点 prev_node = dllist.head.next # 指向节点 1 dllist.insert_after(prev_node, 1.5) dllist.display_forward() # 输出: 0 <-> 1 <-> 1.5 <-> 2 <-> 3 <-> None # 删除节点 dllist.delete(1.5) dllist.display_forward() # 输出: 0 <-> 1 <-> 2 <-> 3 <-> None # 反向显示链表 dllist.display_backward() # 输出: 3 <-> 2 <-> 1 <-> 0 <-> None ``` 链表在 Python 中的应用非常广泛，尤其适用于需要频繁插入和删除操作的场景。通过实现单向链表和双向链表，可以更好地理解和掌握链表的基本操作和应用场景。