在 Data Structures and Algorithms 中，**链表（Linked List）**是一种基础且非常重要的线性数据结构。与数组不同，链表通过 节点之间的指针连接 来组织数据，适合频繁插入和删除的场景。下面从 结构入门 → 分类 → 双向链表实现系统讲解。
一、什么是链表（Linked List）
链表由 节点（Node） 组成，每个节点包含两部分：
数据(data) + 指针(next)
示意结构：
[ data | next ] → [ data | next ] → [ data | next ] → null
特点：
| 特点 | 说明 |
|---|---|
| 非连续存储 | 不像数组那样连续 |
| 插入删除快 | O(1) |
| 查找慢 | O(n) |
二、链表与数组的区别
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存 | 连续 | 不连续 |
| 查找 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
适用场景：
- 数组：频繁查询
- 链表：频繁插入删除
三、链表的分类
链表根据结构可以分为：
链表
├── 单向链表
├── 双向链表
├── 循环链表
└── 双向循环链表
四、单向链表（Singly Linked List）
结构：
head → node1 → node2 → node3 → null
节点结构：
class Node:
def __init__(self, data):
self.data = data
self.next = None
优点：
- 结构简单
- 内存开销小
缺点：
- 只能单向遍历
五、双向链表（Doubly Linked List）
双向链表每个节点包含：
prev ← node → next
结构示意：
null ← node1 ↔ node2 ↔ node3 → null
节点结构：
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
优点：
- 可以 双向遍历
- 删除节点更方便
缺点：
- 多一个指针
- 占用更多内存
六、循环链表（Circular Linked List）
循环链表特点：
尾节点 → 指向头节点
结构：
head → node1 → node2 → node3
↑ ↓
└───────────────←────────┘
应用：
- 操作系统调度
- 约瑟夫问题
七、双向链表初始化实现（Python）
下面实现一个完整 双向链表结构。
1 定义节点
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
2 定义链表类
class DoublyLinkedList:
def __init__(self):
self.head = None
3 头插法
def insert_head(self, data):
new_node = Node(data)
if self.head:
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
示意：
new → head → node2 → node3
4 尾插法
def insert_tail(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
new_node.prev = temp
5 遍历链表
def display(self):
temp = self.head
while temp:
print(temp.data, end=" <-> ")
temp = temp.next
print("None")
输出示例：
1 <-> 2 <-> 3 <-> None
八、完整示例
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert_head(self, data):
new_node = Node(data)
if self.head:
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
def insert_tail(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
new_node.prev = temp
def display(self):
temp = self.head
while temp:
print(temp.data, end=" <-> ")
temp = temp.next
print("None")
测试：
dll = DoublyLinkedList()
dll.insert_head(2)
dll.insert_head(1)
dll.insert_tail(3)
dll.display()
输出：
1 <-> 2 <-> 3 <-> None
九、链表时间复杂度
| 操作 | 时间复杂度 |
|---|---|
| 访问 | O(n) |
| 插入 | O(1) |
| 删除 | O(1) |
| 查找 | O(n) |
十、链表经典算法题
链表是面试重点结构，常见题包括：
- 反转链表
- 合并两个有序链表
- 链表是否有环
- 找链表中间节点
- 删除倒数第 N 个节点
这些题在很多算法平台都会出现，例如：
- LeetCode
总结
链表结构可以总结为：
链表
├ 单向链表
├ 双向链表
├ 循环链表
└ 双向循环链表
核心特点：
- 动态结构
- 插入删除效率高
- 访问效率低
双向链表则通过 prev + next 提供更灵活的操作。
如果你愿意，我可以继续给你整理一份 链表算法最全总结（20道必会题 + Python实现），很多算法面试基本都会考到。
