玩转python: 掌握Python数据结构之链表

链表是计算机科学中最基础的数据结构之一，也是许多高级数据结构和算法的基础。本文将带你从零开始，逐步掌握链表的概念、实现和应用。通过丰富的案例和通俗易懂的解释，你将能够轻松理解并应用链表。

什么是链表？

链表是一种线性数据结构，由一系列节点（Node）组成。每个节点包含两个部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。链表中的节点通过指针连接在一起，形成一个链式结构。

与数组不同，链表的内存空间不需要连续分配。这意味着链表可以更灵活地利用内存空间，但也意味着访问链表中的元素需要从头节点开始逐个遍历。

链表的类型

链表有多种类型，常见的有：

1. 单链表（Singly Linked List）：每个节点只有一个指针，指向下一个节点。
2. 双链表（Doubly Linked List）：每个节点有两个指针，一个指向前一个节点，一个指向下一个节点。
3. 循环链表（Circular Linked List）：尾节点的指针指向头节点，形成一个环。

本文将重点介绍单链表，因为它是最基础且最常用的链表类型。

单链表的实现

在Python中，我们可以通过定义一个Node类和一个LinkedList类来实现单链表。

1. 定义节点类

首先，我们需要定义一个节点类Node，它包含数据域和指针域。

class Node:def __init__(self, data):self.data = data  # 数据域self.next = None  # 指针域，初始化为None

2. 定义链表类

接下来，我们定义一个链表类LinkedList，它包含对链表的各种操作，如插入、删除、遍历等。

class LinkedList:def __init__(self):self.head = None  # 头节点，初始化为None# 在链表末尾插入节点def append(self, data):new_node = Node(data)if self.head is None:  # 如果链表为空，新节点为头节点self.head = new_nodereturnlast_node = self.headwhile last_node.next:  # 遍历到链表末尾last_node = last_node.nextlast_node.next = new_node  # 将新节点插入到末尾# 在链表头部插入节点def prepend(self, data):new_node = Node(data)new_node.next = self.head  # 新节点的指针指向当前头节点self.head = new_node  # 更新头节点为新节点# 删除指定数据的节点def delete(self, data):current_node = self.headif current_node and current_node.data == data:  # 如果头节点就是要删除的节点self.head = current_node.nextcurrent_node = Nonereturnprev_node = Nonewhile current_node and current_node.data != data:  # 遍历查找要删除的节点prev_node = current_nodecurrent_node = current_node.nextif current_node is None:  # 如果没找到要删除的节点returnprev_node.next = current_node.next  # 跳过要删除的节点current_node = None# 打印链表def print_list(self):current_node = self.headwhile current_node:print(current_node.data, end=" -> ")current_node = current_node.nextprint("None")

3. 使用链表

现在，我们可以使用LinkedList类来创建和操作链表。

# 创建一个链表
llist = LinkedList()# 在链表末尾插入节点
llist.append(1)
llist.append(2)
llist.append(3)# 在链表头部插入节点
llist.prepend(0)# 打印链表
llist.print_list()  # 输出: 0 -> 1 -> 2 -> 3 -> None# 删除节点
llist.delete(2)# 打印链表
llist.print_list()  # 输出: 0 -> 1 -> 3 -> None

链表的应用案例

链表在实际应用中有很多用途，以下是几个常见的案例：

1. 实现队列

队列是一种先进先出（FIFO）的数据结构，链表可以很方便地实现队列。

class Queue:def __init__(self):self.linked_list = LinkedList()# 入队def enqueue(self, data):self.linked_list.append(data)# 出队def dequeue(self):if self.linked_list.head is None:return Nonedata = self.linked_list.head.dataself.linked_list.delete(data)return data# 打印队列def print_queue(self):self.linked_list.print_list()# 使用队列
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.print_queue()  # 输出: 1 -> 2 -> 3 -> None
print(queue.dequeue())  # 输出: 1
queue.print_queue()  # 输出: 2 -> 3 -> None

2. 实现栈

栈是一种后进先出（LIFO）的数据结构，链表也可以很方便地实现栈。

class Stack:def __init__(self):self.linked_list = LinkedList()# 入栈def push(self, data):self.linked_list.prepend(data)# 出栈def pop(self):if self.linked_list.head is None:return Nonedata = self.linked_list.head.dataself.linked_list.delete(data)return data# 打印栈def print_stack(self):self.linked_list.print_list()# 使用栈
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.print_stack()  # 输出: 3 -> 2 -> 1 -> None
print(stack.pop())  # 输出: 3
stack.print_stack()  # 输出: 2 -> 1 -> None

3. 反转链表

反转链表是一个经典的面试题，我们可以通过修改指针的方向来实现。

def reverse_linked_list(llist):prev_node = Nonecurrent_node = llist.headwhile current_node:next_node = current_node.next  # 保存下一个节点current_node.next = prev_node  # 反转指针prev_node = current_node  # 移动prev_nodecurrent_node = next_node  # 移动current_nodellist.head = prev_node  # 更新头节点# 反转链表
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.print_list()  # 输出: 1 -> 2 -> 3 -> None
reverse_linked_list(llist)
llist.print_list()  # 输出: 3 -> 2 -> 1 -> None

4. 链表实现LRU缓存

LRU（Least Recently Used）缓存是一种常见的缓存淘汰策略，它会优先淘汰最近最少使用的数据。链表可以很好地支持LRU缓存的实现。

案例：浏览器缓存

假设你正在浏览网页，浏览器会将你最近访问的网页缓存起来。当你访问一个新网页时，如果缓存已满，浏览器会淘汰最久未访问的网页缓存。这个过程可以用链表来实现。

class LRUCache:def __init__(self, capacity):self.capacity = capacity  # 缓存容量self.cache = {}  # 存储缓存数据self.linked_list = LinkedList()  # 使用链表记录访问顺序# 获取缓存数据def get(self, key):if key in self.cache:# 如果缓存中有该数据，将其移到链表头部（表示最近使用）self.linked_list.delete(key)self.linked_list.prepend(key)return self.cache[key]return -1  # 如果缓存中没有该数据，返回-1# 插入缓存数据def put(self, key, value):if key in self.cache:# 如果缓存中已有该数据，更新其值并移到链表头部self.linked_list.delete(key)elif len(self.cache) >= self.capacity:# 如果缓存已满，淘汰链表尾部的数据（最久未使用）last_key = self.linked_list.headwhile last_key.next:last_key = last_key.nextself.linked_list.delete(last_key.data)del self.cache[last_key.data]# 将新数据插入链表头部self.linked_list.prepend(key)self.cache[key] = value# 使用LRU缓存
cache = LRUCache(2)
cache.put(1, "网页1")
cache.put(2, "网页2")
print(cache.get(1))  # 输出: 网页1
cache.put(3, "网页3")  # 缓存已满，淘汰网页2
print(cache.get(2))  # 输出: -1（网页2已被淘汰）

通俗解释：

• 链表记录了数据的访问顺序，最近访问的数据在链表头部，最久未访问的数据在链表尾部。
• 当缓存满时，直接淘汰链表尾部的数据，确保缓存中始终保留最近使用的数据。

5. 链表实现多项式相加

多项式相加是数学中常见的操作，链表可以用来表示多项式，并实现相加功能。

案例：多项式计算

假设有两个多项式：

• 多项式A：3x^2 + 2x + 5
• 多项式B：4x^3 + 2x^2 + 1

我们可以用链表表示这两个多项式，并实现它们的相加。

class PolynomialTerm:def __init__(self, coefficient, exponent):self.coefficient = coefficient  # 系数self.exponent = exponent  # 指数self.next = None  # 指向下一个项的指针class Polynomial:def __init__(self):self.head = None  # 多项式的头节点# 添加项def add_term(self, coefficient, exponent):new_term = PolynomialTerm(coefficient, exponent)if self.head is None:self.head = new_termelse:current = self.headwhile current.next:current = current.nextcurrent.next = new_term# 打印多项式def print_polynomial(self):current = self.headwhile current:print(f"{current.coefficient}x^{current.exponent}", end=" + " if current.next else "\n")current = current.next# 多项式相加def add_polynomials(poly1, poly2):result = Polynomial()current1 = poly1.headcurrent2 = poly2.headwhile current1 and current2:if current1.exponent > current2.exponent:result.add_term(current1.coefficient, current1.exponent)current1 = current1.nextelif current1.exponent < current2.exponent:result.add_term(current2.coefficient, current2.exponent)current2 = current2.nextelse:result.add_term(current1.coefficient + current2.coefficient, current1.exponent)current1 = current1.nextcurrent2 = current2.next# 将剩余项加入结果while current1:result.add_term(current1.coefficient, current1.exponent)current1 = current1.nextwhile current2:result.add_term(current2.coefficient, current2.exponent)current2 = current2.nextreturn result# 创建多项式A：3x^2 + 2x + 5
polyA = Polynomial()
polyA.add_term(3, 2)
polyA.add_term(2, 1)
polyA.add_term(5, 0)# 创建多项式B：4x^3 + 2x^2 + 1
polyB = Polynomial()
polyB.add_term(4, 3)
polyB.add_term(2, 2)
polyB.add_term(1, 0)# 相加并打印结果
result = Polynomial.add_polynomials(polyA, polyB)
result.print_polynomial()  # 输出: 4x^3 + 5x^2 + 2x + 6

通俗解释：

• 每个链表节点表示多项式的一个项，包含系数和指数。
• 通过遍历两个链表，将相同指数的项相加，最终得到一个新的多项式。

6. 链表实现约瑟夫问题

约瑟夫问题是一个经典的数学问题，描述如下：n个人围成一圈，从第k个人开始报数，数到m的人出列，直到所有人出列。链表可以很好地模拟这个过程。

案例：游戏中的淘汰机制

假设你和朋友们围成一圈玩“数到3就淘汰”的游戏，链表可以模拟这个过程。

def josephus(n, k, m):# 创建循环链表class Node:def __init__(self, data):self.data = dataself.next = Nonehead = Node(1)prev = headfor i in range(2, n + 1):new_node = Node(i)prev.next = new_nodeprev = new_nodeprev.next = head  # 形成环# 找到第k个人current = headfor _ in range(k - 1):current = current.next# 开始报数并淘汰while current.next != current:# 报数到m-1for _ in range(m - 1):current = current.next# 淘汰第m个人print(f"淘汰：{current.next.data}")current.next = current.next.nextcurrent = current.nextprint(f"最后剩下：{current.data}")# 使用约瑟夫问题
josephus(5, 1, 3)  # 输出: 淘汰：3 -> 淘汰：1 -> 淘汰：5 -> 淘汰：2 -> 最后剩下：4

通俗解释：

• 链表模拟了一个圆圈，每个人是一个节点，节点的指针指向下一个人。
• 从第k个人开始报数，数到m的人被淘汰（从链表中移除），直到最后剩下一个人。

---

总结

通过以上案例，我们可以看到链表在实际问题中的广泛应用。无论是缓存管理、数学计算还是游戏模拟，链表都能提供高效的解决方案。希望这些案例能帮助你更好地理解链表的应用场景，并激发你进一步探索数据结构的兴趣！