Menu
CoddyTech
开始学习

链表

最后更新

链表把一个序列存成一串节点，每个节点保存一个值和一个指向下一个节点的指针。和数组不同，这些节点在内存中并不连续，要沿着 next 指针才能遍历整个链表。点击上方的“播放”，观看节点如何连接到头部和尾部，如何沿着链条查找一个值，以及如何通过改接一个指针删除节点。

在头部插入或删除是 O(1)，因为只需让 head 指向新的位置。到达中间或尾部的某个位置则是 O(n)，因为必须先一路走过去。两端操作便宜、不能随机访问，这一取舍正是链表和数组的区别所在。

时间复杂度

操作复杂度说明
在头部插入O(1)改变 head 的指向
在尾部插入O(n)先走到末尾（有尾指针时为 O(1)）
查找O(n)沿着 next 指针前进
删除头节点O(1)让 head 越过它
按下标访问O(n)不支持随机访问

链表与数组对比

方面链表数组
内存分散的节点 + 指针连续的内存块
随机访问O(n)O(1)
在开头插入/删除O(1)O(n)（需要移动元素）
缓存友好性差好

实例演示

建立链表 [10, 20]，在开头加入 5，再删除 20：

步骤结构操作
开始head -> null空链表
在头部插入 10head -> 10 -> null让 head 指向一个新节点，新节点的 next 是原来的 head（null）
在尾部插入 20head -> 10 -> 20 -> null走到节点 10，把它的 next 设为新节点 20
在头部插入 5head -> 5 -> 10 -> 20 -> null新节点 5 指向原来的头节点 10；head 现在指向 5
删除 20head -> 5 -> 10 -> null走到 10，把它的 next 从 20 改为 null；节点 20 被断开

什么时候用链表

适合使用不适合使用
在两端（或已持有的节点处）插入、删除的次数远多于按下标访问你需要按位置快速随机访问（O(1) 下标访问）
数据量变化频繁，你不想承担扩容和复制的开销你在跑紧凑的循环，缓存局部性决定性能
你在实现队列、栈或邻接表内存紧张：每个元素都要多付出一个指针的空间
你需要稳定的节点引用，不受其他位置插入的影响你主要是读取、很少修改，这时数组更简单也更快

Linked List 代码

简洁、可运行的 Linked List 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。

Linked List 的 Python 代码

Python
1class Node:2    def __init__(self, value):3        self.value = value4        self.next = None5
6
7class LinkedList:8    def __init__(self):9        self.head = None10
11    def append(self, value):12        node = Node(value)13        if self.head is None:14            self.head = node15            return16        current = self.head17        while current.next:18            current = current.next19        current.next = node20
21    def find(self, value):22        current = self.head23        while current:24            if current.value == value:25                return True26            current = current.next27        return False28
29    def delete(self, value):30        # Re-link the previous node around the match31        current, prev = self.head, None32        while current:33            if current.value == value:34                if prev is None:35                    self.head = current.next36                else:37                    prev.next = current.next38                return True39            prev, current = current, current.next40        return False41
42    def __str__(self):43        values, current = [], self.head44        while current:45            values.append(str(current.value))46            current = current.next47        return " -> ".join(values) + " -> None"48
49
50lst = LinkedList()51for value in [3, 7, 1, 9]:52    lst.append(value)53
54print("List:    ", lst)55print("find(7): ", lst.find(7))56lst.delete(1)57print("After delete(1):", lst)
在 Python 在线编辑器中运行这段代码

链表常见问题

链表和数组有什么区别？
数组把元素存放在一整块连续内存中，随机访问是 O(1)，但插入和删除要移动元素，需要 O(n)。链表的节点可以分散在内存的任意位置，用指针相连，在已知位置插入和删除是 O(1)，但访问需要 O(n)，因为必须沿着链条走过去。
什么时候应该用链表？

当你经常在两端（或在已持有引用的节点处）插入或删除，又很少需要随机访问时，链表最能发挥优势，例如队列、栈、邻接表和 LRU 缓存。如果你需要按下标快速访问，数组或动态数组通常更好。

链表的时间复杂度是多少？
在头部插入或删除是 O(1)。查找，或者在没有尾指针时到达尾部，是 O(n)，因为要逐个跟随 next 指针。链表不支持 O(1) 的随机访问，按下标访问是 O(n)。
单链表和双向链表有什么区别？
单链表的每个节点只保存一个 next 指针，所以只能单向遍历，删除节点时还需要拿到它的前驱节点。双向链表多了一个 prev 指针，可以反向遍历，也能以 O(1) 删除已持有的节点，代价是每个节点多一个指针，每次插入和删除都要多维护一些信息。
既然在头部插入是 O(1)，为什么在尾部插入是 O(n)？
在头部插入只需要改接 head 指针，是常数时间的工作。到达尾部则要从头开始沿着 next 指针一直走到末尾，需要 O(n)。额外维护一个 tail 指针，就能让尾部插入也变成 O(1)，所以实际使用的链表往往会同时记录两端。
链表在任何位置插入都是 O(1) 吗？
不是，这是一个常见误解。只有当你已经拿到要在其后插入的那个节点的指针时，插入本身才是 O(1)。按值或下标找到这个位置仍然要花 O(n)，因为你必须沿着链条走过去。

相关资源

更多可视化

Coddy 编程语言插图

在 Coddy 掌握算法

开始