手写 List 容器的核心算法：双向链表的遍历与操作
·
双向链表的核心算法：遍历与操作
在实现自定义 List 容器时，双向链表是一种高效的基础数据结构，因为它允许双向遍历（前向和后向后向），并支持快速插入、删除等操作。每个节点包含数据、指向前一个节点的指针（prev）和指向后一个节点的指针（next）。下面我将逐步解释双向链表的遍历和核心操作算法，并提供 Python 代码实现。所有实现均基于标准数据结构原理，确保真实可靠。
步骤 1: 定义节点类
双向链表的基础是节点（Node）类。每个节点存储数据、前驱指针和后继指针。
class Node:
def __init__(self, data):
self.data = data # 节点存储的数据
self.prev = None # 指向前一个节点的指针
self.next = None # 指向后一个节点的指针
步骤 2: 定义双向链表类
我们创建一个 DoublyLinkedList 类，管理链表的头节点（head）和尾节点（tail）。初始化时链表为空。
class DoublyLinkedList:
def __init__(self):
self.head = None # 链表头节点
self.tail = None # 链表尾节点
步骤 3: 遍历算法
遍历是访问每个节点的过程。双向链表支持前向遍历（从头到尾）和后向遍历（从尾到头）。时间复杂度为 $O(n)$，其中 $n$ 是节点数。
- 前向遍历：从头节点开始，依次访问每个节点，直到
next为None。 - 后向遍历：从尾节点开始，依次访问每个节点，直到
prev为None。
在 DoublyLinkedList 类中添加遍历方法：
def forward_traversal(self):
"""前向遍历：从头到尾打印节点数据"""
current = self.head
while current:
print(current.data, end=" -> ") # 打印当前节点数据
current = current.next
print("None") # 表示遍历结束
def backward_traversal(self):
"""后向遍历：从尾到头打印节点数据"""
current = self.tail
while current:
print(current.data, end=" -> ") # 打印当前节点数据
current = current.prev
print("None") # 表示遍历结束
步骤 4: 核心操作算法
核心操作包括插入、删除和查找。这些操作需要处理指针的更新，确保链表完整性。时间复杂度分析：
- 插入和删除在头部或尾部为 $O(1)$，在中间为 $O(n)$。
- 查找为 $O(n)$。
在 DoublyLinkedList 类中添加操作方法：
插入操作
- 在头部插入：创建新节点，更新头节点和相邻节点的指针。
- 在尾部插入：创建新节点，更新尾节点和相邻节点的指针。
- 在特定位置插入：先查找位置，再插入节点。
def insert_at_head(self, data):
"""在链表头部插入节点"""
new_node = Node(data)
if self.head is None: # 空链表时，新节点同时是头和尾
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def insert_at_tail(self, data):
"""在链表尾部插入节点"""
new_node = Node(data)
if self.tail is None: # 空链表时，新节点同时是头和尾
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
def insert_at_position(self, data, position):
"""在指定位置插入节点（位置从 0 开始计数）"""
if position < 0:
raise ValueError("位置不能为负")
if position == 0:
self.insert_at_head(data)
return
new_node = Node(data)
current = self.head
index = 0
# 移动到指定位置的前一个节点
while current and index < position - 1:
current = current.next
index += 1
if current is None: # 位置超出链表长度，插入尾部
self.insert_at_tail(data)
else:
new_node.next = current.next
new_node.prev = current
if current.next: # 如果当前节点不是尾节点
current.next.prev = new_node
current.next = new_node
if new_node.next is None: # 如果新节点是尾节点
self.tail = new_node
删除操作
- 删除头部节点：更新头节点指针。
- 删除尾部节点：更新尾节点指针。
- 删除特定节点：先查找节点，再更新指针。
def delete_at_head(self):
"""删除链表头部节点"""
if self.head is None:
return # 空链表，无操作
if self.head == self.tail: # 只有一个节点
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
def delete_at_tail(self):
"""删除链表尾部节点"""
if self.tail is None:
return # 空链表，无操作
if self.head == self.tail: # 只有一个节点
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
def delete_node(self, data):
"""删除指定数据的节点（只删除第一个匹配项）"""
current = self.head
while current:
if current.data == data:
if current == self.head:
self.delete_at_head()
elif current == self.tail:
self.delete_at_tail()
else:
current.prev.next = current.next
current.next.prev = current.prev
return # 删除成功，退出
current = current.next
查找操作
- 查找节点：遍历链表，返回第一个匹配数据的节点。
def find(self, data):
"""查找指定数据的节点，返回节点或 None"""
current = self.head
while current:
if current.data == data:
return current
current = current.next
return None
步骤 5: 完整代码示例
以下是完整的双向链表实现，包括遍历和操作。使用时，可以创建链表对象并调用方法。
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def forward_traversal(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
def backward_traversal(self):
current = self.tail
while current:
print(current.data, end=" -> ")
current = current.prev
print("None")
def insert_at_head(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def insert_at_tail(self, data):
new_node = Node(data)
if self.tail is None:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
def insert_at_position(self, data, position):
if position < 0:
raise ValueError("位置不能为负")
if position == 0:
self.insert_at_head(data)
return
new_node = Node(data)
current = self.head
index = 0
while current and index < position - 1:
current = current.next
index += 1
if current is None:
self.insert_at_tail(data)
else:
new_node.next = current.next
new_node.prev = current
if current.next:
current.next.prev = new_node
current.next = new_node
if new_node.next is None:
self.tail = new_node
def delete_at_head(self):
if self.head is None:
return
if self.head == self.tail:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
def delete_at_tail(self):
if self.tail is None:
return
if self.head == self.tail:
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
def delete_node(self, data):
current = self.head
while current:
if current.data == data:
if current == self.head:
self.delete_at_head()
elif current == self.tail:
self.delete_at_tail()
else:
current.prev.next = current.next
current.next.prev = current.prev
return
current = current.next
def find(self, data):
current = self.head
while current:
if current.data == data:
return current
current = current.next
return None
使用示例
# 创建双向链表
dll = DoublyLinkedList()
dll.insert_at_head(10) # 头部插入
dll.insert_at_tail(20) # 尾部插入
dll.insert_at_position(15, 1) # 在位置1插入
print("前向遍历:")
dll.forward_traversal() # 输出: 10 -> 15 -> 20 -> None
print("后向遍历:")
dll.backward_traversal() # 输出: 20 -> 15 -> 10 -> None
dll.delete_node(15) # 删除节点15
print("删除后前向遍历:")
dll.forward_traversal() # 输出: 10 -> 20 -> None
总结
通过以上实现，双向链表的核心算法包括：
- 遍历：前向和后向遍历均高效，时间复杂度为 $O(n)$。
- 操作：插入和删除在头尾部为 $O(1)$，在中间为 $O(n)$；查找为 $O(n)$。
- 优势：双向指针使得操作更灵活，适合作为 List 容器的底层结构。
您可以根据需要扩展功能，如添加长度计算或迭代器。实际应用中，注意处理边界情况（如空链表或单节点链表）以保持代码健壮性。
更多推荐
3
0- 0
已为社区贡献9条内容
所有评论(0)