数据结构-线性结构
一句话概括
线性结构是元素之间只存在「一对一」前驱后继关系的数据组织方式:数组用连续内存换取随机访问的 ,链表用离散节点换取插入删除的 ,栈和队列是给操作加上纪律(LIFO / FIFO)的数组或链表,字符串是不可变的字符线性表,跳表则在链表上叠索引把查找加速到 。
读完本文你将能:手写动态数组扩容、单/双链表、循环队列、单调栈与 KMP,并说清「为什么下标从 0 开始」「循环队列为什么要空一格」这类面试级问题。
一、抽象数据类型(Abstract Data Type, ADT)
抽象数据类型是「数据 + 允许的操作」的数学描述,它只规定能做什么,不规定怎么实现。
- 逻辑结构:数据元素之间的关系。线性结构是「一对一」,树是「一对多」,图是「多对多」。
- 物理结构(存储结构):数据在内存里怎么放。只有两种基本方式——顺序存储(连续内存)与链式存储(指针串起来)。
- ADT 与实现的分离:同一个 ADT 可以有多种实现。栈的 ADT 规定
push / pop / top / empty四个操作,用数组实现叫顺序栈,用链表实现叫链式栈,调用方代码完全不用改。
分清这三层,复杂度分析才有意义
说「链表插入是 」时,指的是已经拿到插入位置的前驱节点指针这一前提;如果还要先查找位置,整体就是 。所有复杂度结论都必须带上「在什么前提下」。
from abc import ABC, abstractmethod
class Stack(ABC):
"""栈的 ADT:只暴露契约,不暴露实现。
接口里没有 list/dict 这些实现细节,因此底层换成链表实现时
(见第三节的链式栈)调用方零改动——这正是 ADT 的价值。
"""
@abstractmethod
def push(self, item): ...
@abstractmethod
def pop(self): ...
@abstractmethod
def peek(self): ...
@abstractmethod
def is_empty(self) -> bool: ...
二、数组(Array)
2.1 内存布局与随机访问 的原理
数组在内存中是一段连续的空间,每个元素占用 size 字节。若首元素地址为 base,则第 个元素的地址为:
这个公式是一次乘法加一次加法,与 无关,也与 无关,所以按索引访问是 。CPU 的缓存行(Cache Line) 通常 64 字节,连续布局让数组拥有极佳的空间局部性(Spatial Locality),顺序遍历时硬件预取器能提前把数据搬进缓存,实测往往比链表快数倍。
2.2 为什么下标从 0 开始
历史原因来自 C 语言,但真正的理由是让地址计算少一次减法。
- 下标从 0 开始:
- 下标从 1 开始:,多一次减法
对 1970 年代的编译器,每次寻址都省一条指令是有价值的优化。此外从 0 开始还能让半开区间 自洽:区间长度正好是 ,不用 ±1 修正,这就是现代语言切片语法的数学基础。
常见坑:越界与「差一错误」
Python 的
lst[10]越界会抛IndexError,是安全的;C/C++ 的越界是未定义行为(Undefined Behavior),可能读到别的变量甚至被利用来做漏洞攻击。写循环时优先用半开区间range(lo, hi),能显著减少差一错误。
三、动态数组(Dynamic Array)
静态数组容量固定,动态数组封装了「容量不够就申请更大的块并搬过去」的逻辑。
3.1 扩容策略与均摊分析
设扩容因子为 。连续插入 个元素,第 次触发扩容时搬运 个元素。总搬运量是等比数列:
总代价 分摊到 次插入上,每次均摊(Amortized) 。若扩容因子是 1(每次只加 1),总搬运量退化为 ,均摊 ——这就是必须按倍数扩容的原因。
- CPython 的
list:采用 ~1.125 倍( 附近)的温和增长,因为 Python 内存分配器希望减少大块内存浪费。 - C# 的
List<T>:容量不足时直接翻倍(Capacity * 2),从 4 开始,追求更少的复制次数。 - C++ 的
std::vector:通常是 GCC 2 倍、MSVC 1.5 倍(1.5 倍的好处是历史释放的块可以被复用)。
class DynamicArray:
"""极简动态数组:演示扩容与均摊代价。
关键设计:size 与 capacity 分离。size 是逻辑长度,capacity 是物理容量,
只有 size == capacity 时才真正向操作系统申请新内存。
"""
def __init__(self, capacity=1):
self._capacity = max(1, capacity)
self._data = [None] * self._capacity
self._size = 0
self._copies = 0 # 统计搬运次数,用来验证均摊 O(1)
def __len__(self):
return self._size
def __getitem__(self, i):
if not -self._size <= i < self._size:
raise IndexError("index out of range")
return self._data[i % self._size]
def _resize(self, new_capacity):
"""按倍数扩容:只有倍数扩容才能得到均摊 O(1)。"""
new_data = [None] * new_capacity
for i in range(self._size):
new_data[i] = self._data[i]
self._copies += self._size # 记录这次搬运的成本
self._data = new_data
self._capacity = new_capacity
def append(self, value):
if self._size == self._capacity:
self._resize(self._capacity * 2) # 翻倍扩容
self._data[self._size] = value
self._size += 1
def insert(self, index, value):
"""中间插入必须把后面所有元素整体后移,所以是 O(n)。"""
if index < 0:
index += self._size
if not 0 <= index <= self._size:
raise IndexError("index out of range")
if self._size == self._capacity:
self._resize(self._capacity * 2)
for i in range(self._size, index, -1): # 必须从后往前搬,否则会覆盖
self._data[i] = self._data[i - 1]
self._data[index] = value
self._size += 1
def remove_at(self, index):
"""删除同理:后面元素整体前移,O(n)。"""
if not 0 <= index < self._size:
raise IndexError("index out of range")
value = self._data[index]
for i in range(index, self._size - 1):
self._data[i] = self._data[i + 1]
self._size -= 1
self._data[self._size] = None # 断开引用,避免对象无法回收
return value
if __name__ == "__main__":
arr = DynamicArray()
for i in range(1000):
arr.append(i)
print("逻辑长度:", len(arr))
print("总搬运次数:", arr._copies) # 约 2n 量级而非 n^2 量级
print("均摊搬运次数:", arr._copies / len(arr))
arr.insert(0, -1)
print("头部插入后首元素:", arr[0], "长度:", len(arr))
真实语言内置的复杂度(Python 文档「TimeComplexity」页面有完整表格):
| 操作 | list(动态数组) | 说明 |
|---|---|---|
| 尾部 append / pop | 均摊 | 偶尔触发扩容 |
| 按下标读写 | 地址计算 | |
| 中间 insert / remove | 需要搬移后续元素 | |
查找某值 in | 只能线性扫描 | |
切片 lst[a:b] | 复制一份新列表 |
四、链表(Linked List)
4.1 单链表:指针操作图解式描述
节点结构:[data | next],节点在内存里随意散落,靠 next 串联。
在节点 p 之后插入 s,必须先接后断(顺序反了就丢失后半段):
插入前: p ──► q
① s.next = p.next (s 先指向 q,保住后半段)
② p.next = s (p 再指向 s)
插入后: p ──► s ──► q
错误写法: p.next = s; s.next = p.next ← s.next 会指向自己,链表断裂
删除 p 的后继节点 q:p.next = q.next,在支持 GC 的语言里 q 会被自动回收;C/C++ 必须手动 free/delete,否则内存泄漏。
头节点(dummy head)技巧:给链表加一个不存数据的哨兵头,能让「在头部插入/删除第一个节点」和「在中间操作」的代码完全统一,不用写 if head is None 的特判。
class ListNode:
__slots__ = ("val", "next") # __slots__ 省内存:百万节点时差别明显
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class SinglyLinkedList:
"""带哨兵头节点的单链表,所有插入删除逻辑因此无需特判空表。"""
def __init__(self):
self._dummy = ListNode() # 哨兵:永不删除,简化边界
self._size = 0
def __len__(self):
return self._size
def push_front(self, val):
self._dummy.next = ListNode(val, self._dummy.next)
self._size += 1
def push_back(self, val):
node = self._dummy
while node.next: # 链表没有尾指针,尾插要知道尾巴 -> O(n)
node = node.next
node.next = ListNode(val)
self._size += 1
def _node_at(self, index):
"""返回第 index 个节点的前驱,便于删除/插入。"""
if not 0 <= index < self._size:
raise IndexError("index out of range")
prev = self._dummy
for _ in range(index):
prev = prev.next
return prev
def get(self, index):
return self._node_at(index).next.val
def insert(self, index, val):
prev = self._dummy
for _ in range(index): # 允许 index == size,即尾插
prev = prev.next
prev.next = ListNode(val, prev.next)
self._size += 1
def remove_at(self, index):
prev = self._node_at(index)
target = prev.next
prev.next = target.next # 跨过被删节点
target.next = None # 断开引用,帮助 GC
self._size -= 1
return target.val
def reverse(self):
"""原地反转:三指针迭代,时间 O(n),空间 O(1)。"""
prev, cur = None, self._dummy.next
while cur:
nxt = cur.next # 先存后继,否则改完指针就找不到了
cur.next = prev
prev, cur = cur, nxt
self._dummy.next = prev
def to_list(self):
out, node = [], self._dummy.next
while node:
out.append(node.val)
node = node.next
return out
if __name__ == "__main__":
ll = SinglyLinkedList()
for v in [3, 1, 4, 1, 5]:
ll.push_back(v)
print(ll.to_list()) # [3, 1, 4, 1, 5]
ll.insert(0, 9)
print(ll.to_list()) # [9, 3, 1, 4, 1, 5]
ll.remove_at(0)
ll.reverse()
print(ll.to_list()) # [5, 1, 4, 1, 3]
4.2 双链表与循环链表
- 双链表(Doubly Linked List):节点多一个
prev指针。好处是已知节点本身即可 删除(单链表必须知道前驱);代价是每个节点多一个指针的内存,且插入删除要维护 4 条指针(顺序:s.prev = p; s.next = p.next; p.next.prev = s; p.next = s,最后一步必须放最后)。 - 循环链表(Circular Linked List):尾节点的
next指回头节点。适合环形轮询场景(时间片轮转调度、约瑟夫环)。判尾条件从node.next is None变成node.next is head,遍历时务必注意不要写成死循环。
4.3 数组与链表对比
| 维度 | 数组 / 动态数组 | 链表 |
|---|---|---|
| 内存布局 | 连续 | 离散,每节点额外存指针 |
| 随机访问 | ||
| 头部插入/删除 | ||
| 尾部插入/删除 | 均摊 | (持尾指针时) |
| 已知位置插入删除 | (搬移) | (改指针) |
| 按值查找 | ||
| 空间开销 | 低,可能有预留空位 | 每节点多 1~2 个指针 |
| 缓存友好度 | 高(局部性好) | 低(指针跳转易缓存未命中) |
| 扩容 | 需要整体搬迁 | 天然动态,无搬迁 |
| 典型实现 | list、List<T>、vector | LinkedList<T>、std::list |
工程实践中的反直觉结论
由于 CPU 缓存的存在,小规模数据下数组几乎总是比链表快,即使理论复杂度对链表更有利。
LinkedList<T>在 .NET 与 Java 中实际使用率极低;Linux 内核则偏爱侵入式链表。选型时先问「是否会频繁在已知节点处插入删除」,否则默认用数组。
五、栈(Stack)
栈是后进先出(Last In First Out, LIFO)的线性表,只在栈顶(top)操作。
5.1 顺序栈与链式栈
class ArrayStack:
"""顺序栈:用 Python list 当底层存储,全部操作 O(1)。"""
def __init__(self):
self._data = []
def push(self, item):
self._data.append(item) # 尾部即栈顶
def pop(self):
if not self._data:
raise IndexError("pop from empty stack")
return self._data.pop()
def peek(self):
if not self._data:
raise IndexError("peek from empty stack")
return self._data[-1]
def is_empty(self):
return not self._data
def __len__(self):
return len(self._data)
class LinkedStack:
"""链式栈:以链表头为栈顶,push/pop 都是 O(1),无需考虑扩容。"""
def __init__(self):
self._top = None
self._size = 0
def push(self, item):
self._top = ListNode(item, self._top)
def pop(self):
if self._top is None:
raise IndexError("pop from empty stack")
node = self._top
self._top = node.next
node.next = None
self._size -= 1
return node.val
def peek(self):
return self._top.val if self._top else None
def is_empty(self):
return self._top is None
5.2 应用一:括号匹配
遇到左括号入栈,遇到右括号则检查栈顶是否为对应左括号,最后栈必须为空。
def is_balanced(s: str) -> bool:
"""判断括号串是否合法:时间 O(n),空间 O(n)。"""
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
# 栈空说明右括号多余;栈顶不匹配说明类型交叉错误
if not stack or stack.pop() != pairs[ch]:
return False
return not stack # 栈非空说明左括号多余
assert is_balanced("{[()]}") is True
assert is_balanced("([)]") is False # 交叉嵌套必须判错
assert is_balanced("(((") is False
print("括号匹配测试通过")
5.3 应用二:表达式求值
计算机难以直接处理中缀表达式(要考虑优先级与结合性),经典做法有两步:
- 中缀转后缀(逆波兰表达式):用调度场算法(Shunting-yard),操作数直接输出,运算符与栈顶比较优先级后决定入栈或弹出。
- 后缀求值:从左到右扫描,遇操作数入栈,遇运算符弹出两个数计算后压回,最后栈中唯一值即结果。
def infix_to_postfix(expr: str) -> list:
"""中缀转后缀:支持 + - * / 与括号,数字可多位。"""
prec = {"+": 1, "-": 1, "*": 2, "/": 2}
out, ops = [], []
num = ""
for ch in expr + " ": # 末尾补空格,冲出最后一个数字
if ch.isdigit() or ch == ".":
num += ch
continue
if num:
out.append(float(num)); num = ""
if ch in " \t":
continue
if ch == "(":
ops.append(ch)
elif ch == ")":
while ops and ops[-1] != "(":
out.append(ops.pop())
ops.pop() # 弹出左括号,它不进入后缀式
elif ch in prec:
# 栈顶优先级 >= 当前,说明栈顶可以先算,先弹出
while ops and ops[-1] != "(" and prec[ops[-1]] >= prec[ch]:
out.append(ops.pop())
ops.append(ch)
while ops:
out.append(ops.pop())
return out
def eval_postfix(tokens: list) -> float:
"""后缀表达式求值:单次扫描,栈的典型用法。"""
stack = []
for tok in tokens:
if isinstance(tok, float):
stack.append(tok)
else:
b, a = stack.pop(), stack.pop() # 注意顺序:先弹出的是右操作数
stack.append({"+": a + b, "-": a - b,
"*": a * b, "/": a / b}[tok])
return stack[0]
print(infix_to_postfix("3+4*2")) # [3.0, 4.0, 2.0, '*', '+']
print(eval_postfix(infix_to_postfix("3+4*2"))) # 11.0
print(eval_postfix(infix_to_postfix("(1+2)*3"))) # 9.0
5.4 应用三:函数调用栈与单调栈
函数调用栈:每次函数调用都在栈上压入一个栈帧(Stack Frame),保存返回地址、局部变量、参数。递归太深会耗尽栈空间,Python 默认递归限制 1000 层(sys.setrecursionlimit 可调,但调大后仍可能触发 C 栈溢出而崩溃)。
单调栈:栈内元素保持单调,用来求「下一个更大元素」这类问题,均摊 。
def next_greater(nums):
"""每个元素右边第一个更大的值,不存在记 -1。单调递减栈,O(n)。"""
res = [-1] * len(nums)
stack = [] # 存下标,保证 nums[stack] 单调递减
for i, v in enumerate(nums):
# 当前值比栈顶大 -> 栈顶元素找到了答案,弹出
while stack and nums[stack[-1]] < v:
res[stack.pop()] = v
stack.append(i)
return res
print(next_greater([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
六、队列(Queue)
队列是先进先出(First In First Out, FIFO)的线性表,队尾入、队头出。
6.1 循环队列的判空与判满
用普通数组做队列会出现「假溢出」:出队后前面空出位置却无法复用。解决办法是让下标循环:index = (index + 1) % capacity。
代价是 front == rear 既可能是空也可能是满。两种经典处理:
- 牺牲一个单元(最常用):约定
front指向队头元素,rear指向下一个空位。 - 队空条件:
front == rear - 队满条件:
(rear + 1) % capacity == front - 元素个数:
(rear - front + capacity) % capacity - 加标记位 / 计数器:额外维护
size,判空判满直接看计数器,不浪费空间。
| 状态 | 元素个数 | front 与 rear 关系 | 是否有元素在 front |
|---|---|---|---|
| 队空 | 0 | front == rear | 无可用元素 |
| 队满(牺牲单元法) | capacity−1 | (rear+1) % c == front | 有 |
| 一般情况 | (rear-front+c) % c | 无固定关系 | 有 |
class CircularQueue:
"""循环队列:牺牲一个存储单元来区分空与满。"""
def __init__(self, capacity=8):
self._cap = capacity + 1 # 多开一格给「判满」用
self._data = [None] * self._cap
self._front = 0 # 指向队头元素
self._rear = 0 # 指向下一个空位
def is_empty(self):
return self._front == self._rear
def is_full(self):
return (self._rear + 1) % self._cap == self._front
def enqueue(self, item):
if self.is_full():
raise OverflowError("queue is full")
self._data[self._rear] = item
self._rear = (self._rear + 1) % self._cap # 环形推进
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue from empty queue")
item = self._data[self._front]
self._data[self._front] = None # 断开引用
self._front = (self._front + 1) % self._cap
return item
def __len__(self):
return (self._rear - self._front + self._cap) % self._cap
if __name__ == "__main__":
q = CircularQueue(capacity=4)
for i in range(3):
q.enqueue(i)
print("满了吗:", q.is_full(), "长度:", len(q))
print(q.dequeue(), q.dequeue())
q.enqueue(9); q.enqueue(10)
print("出队序列继续:", [q.dequeue() for _ in range(len(q))])
6.2 双端队列(Deque)
双端队列(Double-Ended Queue, Deque) 允许两端插入删除,是栈与队列的超集。collections.deque 底层是分块的指针数组(block 的链表),两端操作 ,随机访问 但常数较小。典型应用:滑动窗口最大值(配合单调队列)。
from collections import deque
def sliding_window_max(nums, k):
"""单调队列求滑动窗口最大值:每个下标最多进出队一次,O(n)。"""
dq = deque() # 存下标,对应值单调递减
res = []
for i, v in enumerate(nums):
while dq and nums[dq[-1]] <= v:
dq.pop() # 队尾比新元素小的都不可能再成为最大值
dq.append(i)
if dq[0] <= i - k:
dq.popleft() # 队头滑出窗口
if i >= k - 1:
res.append(nums[dq[0]])
return res
print(sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]
6.3 优先队列(Priority Queue)概念引出
优先队列出队的不是最早进来的,而是优先级最高的。它已经不是严格意义的 FIFO 队列,而是抽象容器。高效实现是二叉堆(Binary Heap),插入与弹出均为 ,取最值为 。堆的完整内容见 数据结构-树与堆。
import heapq
class PriorityQueue:
"""最小优先队列:用 heapq 实现,附带递增序号保证同优先级 FIFO。"""
def __init__(self):
self._heap = []
self._counter = 0
def push(self, item, priority):
# 元组比较:先比 priority,再比 counter,避免 item 不可比较时报错
heapq.heappush(self._heap, (priority, self._counter, item))
self._counter += 1
def pop(self):
if not self._heap:
raise IndexError("pop from empty priority queue")
return heapq.heappop(self._heap)[2]
def peek(self):
return self._heap[0][2]
def __len__(self):
return len(self._heap)
pq = PriorityQueue()
pq.push("写代码", 3); pq.push("改 bug", 1); pq.push("喝咖啡", 2)
print([pq.pop() for _ in range(3)]) # ['改 bug', '喝咖啡', '写代码']
七、字符串(String)
字符串是字符的线性表,但有两个特殊之处:不可变(Immutable) 与 模式匹配。
7.1 不可变性及其代价
Python 的 str、C# 的 string、Java 的 String 都是不可变的。好处:可安全共享、可作字典键(哈希值可缓存)、线程安全。代价:每次「修改」都创建新对象。
# 反例一:循环内反复拼接字符串
# 语义上每次都可能新建对象,跨实现(如部分解释器)会退化成 O(n^2)
def bad_join(items):
s = ""
for it in items:
s += it
return s
# 正确做法:先收集到 list,最后一次性 join,复杂度 O(总长度)
def good_join(items):
return "".join(items)
不可变 ≠ 一定慢,但一定要知道谁在做复制
Python 3.11+ 对
str +=有原地扩容特化,简单循环拼接未必慢;但切片s[1:]永远是 复制,s in t是 朴素匹配(CPython 实际用 Two-Way 算法优化到接近 )。不要只凭直觉猜性能,要查官方文档或实测。
7.2 朴素匹配与 KMP
朴素匹配(Brute Force):主串每个位置都尝试匹配模式串,最坏 (如主串 aaaaaaab、模式 aaab)。
KMP(Knuth-Morris-Pratt) 的核心思想:利用已匹配的信息,主串指针永不回退。当失配时,模式串回退到 next[j],而主串指针不动,因此是 。
next 数组(前缀函数)定义:next[j] 表示模式串 p[0..j] 中最长的既是真前缀又是真后缀的子串长度(很多教材用 next[0] = -1 的版本,下面代码用「长度版」,更直观且是现代主流写法)。
构造过程(递推):设已知 next[j] = k,求 next[j+1]:
- 若
p[j] == p[k],则next[j+1] = k + 1(前缀后缀都延长一个字符)。 - 若不等,令
k = next[k-1]继续比较(退到更短的前缀)。 - 若
k退到 0 仍不等,则next[j+1] = 0。
例题:模式串 p = "ababaca"
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 字符 | a | b | a | b | a | c | a |
next[j] | 0 | 0 | 1 | 2 | 3 | 0 | 1 |
推导要点:next[3]=2 因为 "abab" 的最长相等真前后缀是 "ab";next[5]=0 因为 "ababac" 前缀 a/ab 都无法与后缀 c/ac 匹配。
def build_next(pattern: str) -> list:
"""构造前缀函数:next[i] = p[0..i] 的最长相等真前后缀长度。时间 O(m)。"""
n = len(pattern)
nxt = [0] * n
k = 0 # k 是当前候选的前缀长度
for i in range(1, n):
while k > 0 and pattern[i] != pattern[k]:
k = nxt[k - 1] # 失配:退到次长的相等前后缀
if pattern[i] == pattern[k]:
k += 1 # 匹配成功,前缀长度 +1
nxt[i] = k
return nxt
def kmp_search(text: str, pattern: str) -> list:
"""返回 pattern 在 text 中所有出现的起始下标。时间 O(n + m)。"""
if not pattern:
return []
nxt = build_next(pattern)
res = []
k = 0 # k 表示当前已匹配的模式串字符数
for i, ch in enumerate(text):
while k > 0 and ch != pattern[k]:
k = nxt[k - 1] # 主串指针 i 不回退,只回退模式串
if ch == pattern[k]:
k += 1
if k == len(pattern):
res.append(i - k + 1)
k = nxt[k - 1] # 继续找下一次出现(允许重叠)
return res
assert build_next("ababaca") == [0, 0, 1, 2, 3, 0, 1]
assert kmp_search("ababababaca", "ababaca") == [4]
assert kmp_search("aaaaa", "aa") == [0, 1, 2, 3]
print("KMP 测试通过")
为什么 KMP 是线性的
主串指针
i单调递增永不回退( 次),模式串指针k每次while循环至少减 1,而k总共只增加了不超过 次,因此while的总执行次数不超过 。这是势能法(Potential Method) 均摊分析的典型例子。
八、跳表(Skip List)
跳表在有序链表上叠加多级索引:第 1 级索引每 2 个节点取一个,第 2 级每 4 个取一个……查找时从最高层开始,向右走不动就往下一层,期望查找长度 。每个节点以概率 (常取 1/2)决定是否向上生长,因此不需要旋转就能维持平衡。
| 对比项 | 跳表 | 平衡树(AVL/红黑树) |
|---|---|---|
| 查找/插入/删除 | 期望 | 最坏 |
| 实现难度 | 简单(无旋转) | 复杂(旋转/染色) |
| 范围查询 | 天然支持(底层有序链表) | 需中序遍历或线索化 |
| 并发友好度 | 高(局部加锁即可) | 低(旋转会牵动大片结构) |
| 典型应用 | Redis 有序集合(ZSet) | std::map、TreeMap |
为什么 Redis 用跳表而不是红黑树
Redis 作者 antirez 的解释大意是:跳表实现更简单、范围查询(
ZRANGE)更直观、并发控制更容易调试,且实测性能与平衡树相当。工程选型常常不是选理论最优,而是选可维护性与场景匹配度。
| 结构 | 访问 | 查找 | 头部插入 | 尾部插入 | 空间 |
|---|---|---|---|---|---|
| 数组 | 均摊 | 紧凑 | |||
| 单链表 | / 带尾指针 | 每节点 +1 指针 | |||
| 双链表 | 带尾指针 | 每节点 +2 指针 | |||
| 栈 | 仅栈顶 | 同底层 | |||
| 队列 | 仅队头 | 同底层 | |||
| 跳表 | 期望 | 期望 | 期望 | 期望 | 期望 2 指针/节点 |
九、注意事项与常见坑
线性结构高频踩坑清单
1. 链表改指针必须先接后断:
p.next = s; s.next = p.next会让s.next指向自己,形成自环。2. 删除链表节点后要断开引用:Python 里
node.next = None,否则被删节点仍被引用,GC 无法回收。3. 循环队列必须牺牲一格或加计数:
front == rear无法同时表示空与满,这是设计约束不是 bug。4. 循环队列取长度用
(rear - front + cap) % cap:直接相减在rear < front时是负数。5. 栈溢出:递归深度默认 1000 左右,深递归应改写成显式栈迭代。
6. 翻转链表的
while里忘记暂存next:cur.next = prev之后就再也找不到原后继了。7. 切片/
s[1:]是复制:在循环里对长字符串反复切片会退化成 。8.
lst.insert(0, x)是 :需要队头入队请用collections.deque。9. KMP 的
next有两套约定:next[0] = -1版与「长度」版数值不同,看代码前先确认定义,否则会误判为写错。10. 字符串不可变不等于哈希可缓存全部场景:超长字符串首次
hash()是 ,之后才命中缓存。
十、练习题
练习 1:设计一个 获取最小值的栈
在支持
push / pop / top的栈上增加get_min(),要求三个操作都是 。提示:用辅助栈同步保存「当前最小值」,或用「差值法」只存一个栈。
练习 2:判断链表是否有环并找出环入口
用快慢指针(Floyd 判圈算法)先判断有无环,再证明「相遇点到环入口的距离 = 头节点到环入口的距离」,据此找出入口。要求空间 。
练习 3:用两个栈实现一个队列
只允许使用栈的
push / pop / peek / empty操作,实现队列的enqueue / dequeue,并分析均摊复杂度(答案:每个元素最多被搬两次,均摊 )。
练习 4:手写
next数组并解释失配回退对模式串
"aabaabaaa"手算完整的next数组,并用它模拟在主串"aabaabaabaabaaa"上的匹配过程,写出每次失配时k的变化。
练习 5:实现 LRU 缓存
设计一个容量为 的最近最少使用缓存,
get与put均要求 。提示:哈希表 + 双向链表,哈希表定位节点,双向链表维护使用顺序(这正是 数据结构-哈希表 与双向链表的组合应用)。
十一、常见问题 FAQ
Q1:既然链表插入是 ,为什么实际项目里几乎都用数组?
因为「插入 」的前提是已经持有那个位置的节点引用。业务代码的典型流程是「先查找,再插入」,查找是 ,总成本反而高于数组的 搬移(搬移是连续内存的顺序拷贝,速度极快且缓存友好)。只有当数据结构本身长期持有节点引用(如 LRU 的哈希表指向链表节点)时,链表的优势才真正体现。
Q2:Python 的
list扩容倍数到底是 1.125 还是 2?CPython 用的是温和增长,具体公式在
Objects/listobject.c的list_resize中:新容量约为newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6),即约 1.125 倍加常数,并在四次扩容后容量大致翻倍。因此社区常说「约 1.125 倍增长」。C#List<T>与 JavaArrayList则是明确的 2 倍与 1.5 倍。具体数值以官方源码为准。
Q3:为什么循环队列常选择牺牲一个单元而不是加计数器?
牺牲一格实现最简单,不需要额外状态,只需一个取模表达式;代价是容量为 时最多存 个元素。加计数器省空间但每次入队出队都要维护
size,在并发场景还可能需要原子操作。二者都正确,属于工程取舍。
Q4:KMP 在实际工程中重要吗?
手写 KMP 的主要价值是理解「利用已匹配信息避免回退」的思想,它也是 AC 自动机、Z 函数、后缀数组等字符串算法的基石。但工程中直接用语言内置能力更稳妥:Python 的
str.find使用 Two-Way 算法(最坏 ),C# 的string.IndexOf也有优化实现。理解了原理,才知道什么时候不该自己造轮子。
相关笔记
- 数据结构-树与堆:跳表与平衡树的对照、优先队列的堆实现、Trie 对字符串检索的加速
- 数据结构-哈希表:LRU 缓存中哈希表与双向链表的配合、哈希表与线性结构的选型
- 算法-复杂度分析:均摊分析、势能法、主定理,本文多处结论的数学基础
- Python-02-内置数据结构:
list、deque、heapq的工程用法与坑 - 算法-查找与分治:二分查找、双指针与本文的链表/字符串技巧互补
- 00-索引:全库导航
参考来源
- Python 官方文档《内置类型》,字符串不可变性与序列语义:https://docs.python.org/3/library/stdtypes.html
- Python 官方文档《collections —— 容器数据类型》,
deque的复杂度说明:https://docs.python.org/3/library/collections.html - CPython 源码
Objects/listobject.c,list_resize扩容策略:https://github.com/python/cpython/blob/main/Objects/listobject.c - CPython Wiki《TimeComplexity》,
list/deque各操作复杂度表:https://wiki.python.org/moin/TimeComplexity - VisuAlgo 可视化教学,链表、栈、队列动态演示:https://visualgo.net/en/list
- OI Wiki《前缀函数与 KMP 算法》,
next数组定义与复杂度证明:https://oi-wiki.org/string/kmp/ - Microsoft Learn《List<T> 类》,C# 动态数组容量增长说明:https://learn.microsoft.com/zh-cn/dotnet/api/system.collections.generic.list-1
- 严蔚敏《数据结构(C 语言版)》,线性表、栈与队列的经典定义与循环队列判满条件