Python 算法基础篇：链表和双向链表的实现与应用
Python 算法基础篇：链表和双向链表的实现与应用
引言
链表和双向链表是常用的线性数据结构，它们在算法和程序设计中有着广泛的应用。本篇博客将重点介绍链表和双向链表的原理、实现以及它们在不同场景下的应用。我们将使用 Python 来演示链表和双向链表的实现，并通过实例展示每一行代码的运行过程。
😃😄 ❤️ ❤️ ❤️
1. 链表的概念与特点
链表是一种线性数据结构，它由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储节点的值，指针域用于指向下一个节点的地址。通过指针的连接，所有节点在内存中不必连续存储，从而实现灵活的内存分配。
链表的特点：
- 链表中的每个节点都有一个指向下一个节点的指针；
- 链表可以根据需要动态分配内存；
- 插入和删除节点时只需要调整指针，不需要移动其他节点；
- 链表可以用单向链表和双向链表两种形式实现。
2. 单向链表的实现与应用
2.1 单向链表的实现
下面是单向链表的 Python 实现：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class SinglyLinkedList:
def __init__(self):
self.head = None
def is_empty(self):
return self.head is None
def add_at_head(self, val):
new_node = ListNode(val)
new_node.next = self.head
self.head = new_node
def add_at_tail(self, val):
new_node = ListNode(val)
if self.is_empty():
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def add_after_node(self, node, val):
if not node:
return
new_node = ListNode(val)
new_node.next = node.next
node.next = new_node
def delete_at_head(self):
if not self.is_empty():
self.head = self.head.next
def delete_after_node(self, node):
if not node or not node.next:
return
node.next = node.next.next
def search(self, val):
current = self.head
while current:
if current.val == val:
return True
current = current.next
return False
def display(self):
current = self.head
while current:
print(current.val, end=" -> ")
current = current.next
print("None")代码解释：上述代码定义了一个单向链表类 SinglyLinkedList ，以及一个节点类 ListNode 。类中的方法包括：判断链表是否为空 is_empty ，在链表头部添加节点 add_at_head ，在链表尾部添加节点 add_at_tail ，在指定节点后插入节点 add_after_node ，删除链表头部节点 delete_at_head ，删除指定节点后的节点 delete_after_node ，搜索指定值是否存在于链表中 search ，以及打印链表的内容 display 。
2.2 单向链表的应用
单向链表在算法和程序设计中有着广泛的应用，以下是一些常见的应用场景：
2.2.1 链表反转
链表反转是将原链表中的节点顺序反转，成为一个新的链表。例如，将链表 1 -> 2 -> 3 -> 4 -> 5 反转为 5 -> 4 -> 3 -> 2 -> 1 ：
def reverse_linked_list(head):
prev = None
current = head
while current:
temp = current.next
current.next = prev
prev = current
current = temp
return prev代码解释：上述代码定义了一个函数 reverse_linked_list ，它接收链表的头节点 head 作为参数，然后使用迭代方式将链表反转。我们使用三个指针 prev 、 current 和 temp ，将当前节点的指针指向前一个节点，然后更新指针继续遍历链表，直到最后一个节点。
2.2.2 链表中的环检测
链表中的环检测是判断链表是否存在环的问题。例如，给定链表 1 -> 2 -> 3 -> 4 -> 2 ，它存在环，因为节点 2 指向了之前出现过的节点 2 ：
def has_cycle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False代码解释：上述代码定义了一个函数 has_cycle ，它接收链表的头节点 head 作为参数，然后使用快慢指针的方法来检测链表中是否存在环。快指针每次移动两步，慢指针每次移动一步，如果快慢指针相遇，则说明链表中存在环。
3. 双向链表的实现与应用
3.1 双向链表的实现
下面是双向链表的 Python 实现：
class DoubleListNode:
def __init__(self, val=0, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def is_empty(self):
return self.head is None
def add_at_head(self, val):
new_node = DoubleListNode(val)
if self.is_empty():
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def add_at_tail(self, val):
new_node = DoubleListNode(val)
if self.is_empty():
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
def add_after_node(self, node, val):
if not node:
return
new_node = DoubleListNode(val)
new_node.prev = node
new_node.next = node.next
if node.next:
node.next.prev = new_node
else:
self.tail = new_node
node.next = new_node
def delete_at_head(self):
if not self.is_empty():
self.head = self.head.next
if self.head:
self.head.prev = None
else:
self.tail = None
def delete_after_node(self, node):
if not node or not node.next:
return
node.next = node.next.next
if node.next:
node.next.prev = node
else:
self.tail = node
def search(self, val):
current = self.head
while current:
if current.val == val:
return True
current = current.next
return False
def display(self):
current = self.head
while current:
print(current.val, end=" <-> ")
current = current.next
print("None")代码解释：上述代码定义了一个双向链表类 DoublyLinkedList ，以及一个节点类 DoubleListNode 。类中的方法包括：判断链表是否为空 is_empty ，在链表头部添加节点 add_at_head ，在链表尾部添加节点 add_at_tail ，在指定节点后插入节点 add_after_node ，删除链表头部节点 delete_at_head ，删除指定节点后的节点 delete_after_node ，搜索指定值是否存在于链表中 search ，以及打印链表的内容 display 。
3.2 双向链表的应用
双向链表在算法和程序设计中也有着广泛的应用，以下是一些常见的应用场景：
3.2.1 LRU 缓存淘汰算法
LRU （ Least Recently Used ）缓存淘汰算法是一种常见的缓存管理策略，它根据数据的访问时间来淘汰最近最少使用的数据。当缓存满时，新加入的数据将替换掉最近最少使用的数据。
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = DoublyLinkedList()
self.key_to_node = {}
def get(self, key):
if key in self.key_to_node:
node = self.key_to_node[key]
self.cache.delete_after_node(node.prev)
self.cache.add_after_node(self.cache.head, node.val)
return node.val[1]
return -1
def put(self, key, value):
if key in self.key_to_node:
node = self.key_to_node[key]
self.cache.delete_after_node(node.prev)
elif len(self.key_to_node) >= self.capacity:
del self.key_to_node[self.cache.tail.val[0]]
self.cache.delete_at_head()
self.cache.add_after_node(self.cache.head, (key, value))
self.key_to_node[key] = self.cache.head.next代码解释：上述代码定义了一个 LRU 缓存类 LRUCache ，它使用双向链表来实现缓存的淘汰策略。类中的方法包括：获取缓存数据 get ，将最近访问的数据移动到链表头部，并返回数据的值；插入缓存数据 put ，如果缓存已满则删除最久未访问的数据，并将新数据插入链表头部。
总结
本篇博客重点介绍了链表和双向链表的概念、实现和应用。链表和双向链表是两种常用的线性数据结构，在算法和程序设计中有着广泛的应用。我们通过使用 Python 来演示链表和双向链表的实现，并通过实例展示它们在不同场景下的应用。
腾讯云开发者
