重庆网站seo案例_展馆门户网站建设_公众号推广平台_免费注册域名网站

Python数据结构实战：链表的构建与操作

一、链表（LinkedList）基础

1. 定义与特性

链表是一种动态数据结构，其特点如下：

• 元素（节点）通过指针连接，内存空间非连续
• 插入/删除时间复杂度为 O(1)（已知位置时）
• 访问元素时间复杂度为 O(n)
• 无需预先分配内存空间

---

2. 单链表 vs 双链表

类型	结构	特点
单链表	节点含 data 和 next 指针	单向遍历，内存占用更小
双链表	节点含 data, prev, next	双向遍历，支持反向操作

---

二、单链表实现

1. 节点类定义

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

---

2. 链表类框架

class LinkedList:def __init__(self):self.head = None  # 头节点def is_empty(self):return self.head is Nonedef __len__(self):count = 0current = self.headwhile current:count += 1current = current.nextreturn countdef __str__(self):values = []current = self.headwhile current:values.append(str(current.data))current = current.nextreturn " -> ".join(values)

---

3. 核心操作实现

插入操作

# 头部插入
def insert_at_head(self, data):new_node = Node(data)new_node.next = self.headself.head = new_node# 尾部插入
def append(self, data):new_node = Node(data)if self.is_empty():self.head = new_nodereturncurrent = self.headwhile current.next:current = current.nextcurrent.next = new_node# 指定位置插入
def insert_at(self, index, data):if index < 0 or index > len(self):raise IndexError("索引超出范围")if index == 0:self.insert_at_head(data)returnnew_node = Node(data)current = self.headfor _ in range(index-1):current = current.nextnew_node.next = current.nextcurrent.next = new_node

---

删除操作

# 删除头部
def delete_head(self):if self.is_empty():raise Exception("空链表")self.head = self.head.next# 删除尾部
def delete_tail(self):if self.is_empty():returnif self.head.next is None:self.head = Nonereturncurrent = self.headwhile current.next.next:current = current.nextcurrent.next = None# 按值删除
def delete_by_value(self, value):if self.is_empty():returnif self.head.data == value:self.delete_head()returncurrent = self.headwhile current.next:if current.next.data == value:current.next = current.next.nextreturncurrent = current.next

---

三、双链表实现（扩展）

class DNode:def __init__(self, data):self.data = dataself.prev = Noneself.next = Noneclass DoublyLinkedList:def __init__(self):self.head = Noneself.tail = None# 实现类似单链表的操作方法（需维护prev指针）# ...

---

四、每日挑战：反转单链表

1. 迭代法实现

def reverse(self):prev = Nonecurrent = self.headwhile current:next_node = current.nextcurrent.next = prevprev = currentcurrent = next_nodeself.head = prev

2. 递归法实现

def reverse_recursive(self, node):if node is None or node.next is None:return nodenew_head = self.reverse_recursive(node.next)node.next.next = nodenode.next = Nonereturn new_head

---

五、性能对比

操作	数组	单链表	双链表
随机访问	O(1)	O(n)	O(n)
头部插入	O(n)	O(1)	O(1)
尾部插入	O(1)	O(n)	O(1)
中间插入	O(n)	O(n)	O(n)
内存占用	连续	非连续	非连续

---

六、应用场景

1. 实现栈/队列
2. 音乐播放列表
3. 浏览器历史记录
4. 内存管理系统
5. 图算法中的邻接表

---

实战建议：

1. 使用纸笔绘制节点变化过程
2. 添加异常处理完善代码
3. 编写单元测试验证边界条件
4. 尝试实现其他变种（循环链表）