【数据结构与算法】链表超全分类！从结构入门到双向链表初始化实现

在 Data Structures and Algorithms 中，**链表（Linked List）**是一种基础且非常重要的线性数据结构。与数组不同，链表通过节点之间的指针连接来组织数据，适合频繁插入和删除的场景。下面从结构入门 → 分类 → 双向链表实现系统讲解。

一、什么是链表（Linked List）

链表由节点（Node）组成，每个节点包含两部分：

数据(data) + 指针(next)

示意结构：

[ data | next ] → [ data | next ] → [ data | next ] → null

特点：

二、链表与数组的区别

适用场景：

• 数组：频繁查询
• 链表：频繁插入删除

三、链表的分类

链表根据结构可以分为：

链表 ├── 单向链表 ├── 双向链表 ├── 循环链表 └── 双向循环链表

四、单向链表（Singly Linked List）

结构：

head → node1 → node2 → node3 → null

节点结构：

classNode:def__init__(self,data):self.data=data self.next=None

优点：

• 结构简单
• 内存开销小

缺点：

• 只能单向遍历

五、双向链表（Doubly Linked List）

双向链表每个节点包含：

prev ← node → next

结构示意：

null ← node1 ↔ node2 ↔ node3 → null

节点结构：

classNode:def__init__(self,data):self.data=data self.prev=Noneself.next=None

优点：

• 可以双向遍历
• 删除节点更方便

缺点：

• 多一个指针
• 占用更多内存

六、循环链表（Circular Linked List）

循环链表特点：

尾节点 → 指向头节点

结构：

head → node1 → node2 → node3 ↑ ↓ └───────────────←────────┘

应用：

• 操作系统调度
• 约瑟夫问题

七、双向链表初始化实现（Python）

下面实现一个完整双向链表结构。

1 定义节点

classNode:def__init__(self,data):self.data=data self.prev=Noneself.next=None

2 定义链表类

classDoublyLinkedList:def__init__(self):self.head=None

3 头插法

definsert_head(self,data):new_node=Node(data)ifself.head:self.head.prev=new_node new_node.next=self.head self.head=new_node

示意：

new → head → node2 → node3

4 尾插法

definsert_tail(self,data):new_node=Node(data)ifnotself.head:self.head=new_nodereturntemp=self.headwhiletemp.next:temp=temp.nexttemp.next=new_node new_node.prev=temp

5 遍历链表

defdisplay(self):temp=self.headwhiletemp:print(temp.data,end=" <-> ")temp=temp.nextprint("None")

输出示例：

1 <-> 2 <-> 3 <-> None

八、完整示例

classNode:def__init__(self,data):self.data=data self.prev=Noneself.next=NoneclassDoublyLinkedList:def__init__(self):self.head=Nonedefinsert_head(self,data):new_node=Node(data)ifself.head:self.head.prev=new_node new_node.next=self.head self.head=new_nodedefinsert_tail(self,data):new_node=Node(data)ifnotself.head:self.head=new_nodereturntemp=self.headwhiletemp.next:temp=temp.nexttemp.next=new_node new_node.prev=tempdefdisplay(self):temp=self.headwhiletemp:print(temp.data,end=" <-> ")temp=temp.nextprint("None")

测试：

dll=DoublyLinkedList()dll.insert_head(2)dll.insert_head(1)dll.insert_tail(3)dll.display()

输出：

1 <-> 2 <-> 3 <-> None

九、链表时间复杂度

十、链表经典算法题

链表是面试重点结构，常见题包括：

1. 反转链表
2. 合并两个有序链表
3. 链表是否有环
4. 找链表中间节点
5. 删除倒数第 N 个节点

这些题在很多算法平台都会出现，例如：

• LeetCode

总结

链表结构可以总结为：

链表 ├ 单向链表 ├ 双向链表 ├ 循环链表 └ 双向循环链表

核心特点：

• 动态结构
• 插入删除效率高
• 访问效率低

双向链表则通过prev + next提供更灵活的操作。

如果你愿意，我可以继续给你整理一份链表算法最全总结（20道必会题 + Python实现），很多算法面试基本都会考到。