1. 数组（Array）
1.1 内存布局
数组是连续内存存储的线性结构，通过基地址 + 偏移量直接计算元素位置。
索引: 0 1 2 3 4
内存: [A0] [A1] [A2] [A3] [A4]
↑ 基地址
A[i] 地址 = 基地址 + i × 元素大小
1.2 时间复杂度分析
| 操作 | 时间 | 说明 |
|---|---|---|
| 随机访问 | O(1) | 直接计算地址 |
| 尾部插入 | O(1)/O(n) | 有空间时 O(1)，扩容时 O(n) |
| 中间插入 | O(n) | 需要移动后续元素 |
| 删除 | O(n) | 需要移动后续元素 |
| 查找 | O(n) | 无序数组遍历；有序数组可二分 O(log n) |
class DynamicArray:
"""动态数组实现（类似 Python list / Java ArrayList）"""
def __init__(self):
self._capacity = 4
self._size = 0
self._data = [None] * self._capacity
def append(self, val):
if self._size == self._capacity:
self._resize(self._capacity * 2)
self._data[self._size] = val
self._size += 1
def _resize(self, new_cap):
new_data = [None] * new_cap
for i in range(self._size):
new_data[i] = self._data[i]
self._data = new_data
self._capacity = new_cap
def insert(self, index, val):
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] = val
self._size += 1
def delete(self, index):
for i in range(index, self._size - 1):
self._data[i] = self._data[i + 1]
self._size -= 1
# 缩容：size < capacity/4 时减半
if self._size < self._capacity // 4 and self._capacity > 4:
self._resize(self._capacity // 2)
均摊分析：动态数组扩容是 O(n)，但 n 次插入总时间是 O(n)，所以单次均摊 O(1)。
2. 链表（Linked List）
2.1 内存布局
链表通过指针连接分散的节点，无需连续内存。
单链表: [数据|next] → [数据|next] → [数据|next] → NULL
双链表: NULL ← [prev|数据|next] ↔ [prev|数据|next] → NULL
2.2 时间复杂度对比
| 操作 | 数组 | 链表（已知前驱） | 链表（未知前驱） |
|---|---|---|---|
| 随机访问 | O(1) | O(n) | O(n) |
| 头部插入 | O(n) | O(1) | O(1) |
| 尾部插入 | O(1)* | O(1) | O(n) |
| 中间插入 | O(n) | O(1) | O(n) |
| 删除 | O(n) | O(1) | O(n) |
class ListNode:
"""单链表节点"""
def __init__(self, val=0):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.dummy = ListNode() # 哨兵节点简化边界处理
self.tail = self.dummy
self.size = 0
def append(self, val):
self.tail.next = ListNode(val)
self.tail = self.tail.next
self.size += 1
def prepend(self, val):
new_node = ListNode(val)
new_node.next = self.dummy.next
self.dummy.next = new_node
if self.tail == self.dummy:
self.tail = new_node
self.size += 1
def delete(self, val):
prev = self.dummy
curr = self.dummy.next
while curr:
if curr.val == val:
prev.next = curr.next
if curr == self.tail:
self.tail = prev
self.size -= 1
return True
prev, curr = curr, curr.next
return False
def reverse(self):
"""链表翻转：迭代法 O(n)"""
prev = None
curr = self.dummy.next
self.tail = curr # 原头变新尾
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
self.dummy.next = prev
2.3 链表经典问题
# 快慢指针找中点
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 判断环
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# 合并两个有序链表
def merge(l1, l2):
dummy = ListNode()
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
3. 栈（Stack）
后进先出（LIFO） 结构。
class Stack:
"""基于动态数组的栈"""
def __init__(self):
self._data = []
def push(self, x):
self._data.append(x)
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self._data.pop()
def peek(self):
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def size(self):
return len(self._data)
# 应用场景：括号匹配
def is_valid(s: str) -> bool:
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in pairs.values():
stack.append(ch)
elif ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
return len(stack) == 0
4. 队列（Queue）
先进先出（FIFO） 结构。
4.1 普通队列
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, x):
self._data.append(x)
def dequeue(self):
return self._data.popleft()
def peek(self):
return self._data[0]
def is_empty(self):
return len(self._data) == 0
4.2 循环队列
class CircularQueue:
"""固定容量循环队列，避免频繁扩容"""
def __init__(self, k: int):
self._cap = k + 1 # 多一个空位区分满和空
self._data = [None] * self._cap
self._head = self._tail = 0
def enqueue(self, x):
if self.is_full():
raise IndexError("Queue is full")
self._data[self._tail] = x
self._tail = (self._tail + 1) % self._cap
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")
val = self._data[self._head]
self._head = (self._head + 1) % self._cap
return val
def is_empty(self):
return self._head == self._tail
def is_full(self):
return (self._tail + 1) % self._cap == self._head
4.3 单调队列（滑动窗口最大值）
from collections import deque
def max_sliding_window(nums, k):
"""O(n) 解法，单调递减双端队列"""
q = deque() # 存储索引，对应值单调递减
result = []
for i, num in enumerate(nums):
# 移除窗口外的元素
while q and q[0] <= i - k:
q.popleft()
# 保持单调递减
while q and nums[q[-1]] <= num:
q.pop()
q.append(i)
if i >= k - 1:
result.append(nums[q[0]])
return result
5. 双端队列与 LRU 缓存实战
双端队列（Deque）是队列和栈的通用抽象，支持在两端 O(1) 插入和删除。Python 的 collections.deque 底层是双向链表实现。
from collections import deque
d = deque()
d.append(1) # 右侧入队
d.appendleft(2) # 左侧入队
d.pop() # 右侧出队
d.popleft() # 左侧出队
LRU 缓存实现（链表 + 哈希表）
**LRU（Least Recently Used）**缓存是操作系统和数据库的核心组件，也是经典面试题。其设计目标是：缓存满时淘汰最久未使用的数据。
数据结构选择：
- 哈希表：O(1) 查找 key 是否存在
- 双向链表：O(1) 移动节点到队首（最新使用）和淘汰队尾（最久未使用）
class LRUCache:
"""LRU 缓存：哈希表 + 双向链表"""
class Node:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # key -> Node
# 伪头尾节点简化边界处理
self.head = self.Node()
self.tail = self.Node()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._move_to_head(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.val = value
self._move_to_head(node)
else:
node = self.Node(key, value)
self.cache[key] = node
self._add_to_head(node)
if len(self.cache) > self.capacity:
removed = self._remove_tail()
del self.cache[removed.key]
def _add_to_head(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _move_to_head(self, node):
self._remove_node(node)
self._add_to_head(node)
def _remove_tail(self):
node = self.tail.prev
self._remove_node(node)
return node
为什么不用数组实现 LRU？
| 操作 | 数组 | 链表 + 哈希表 |
|---|---|---|
| get | O(1) | O(1) |
| put（缓存中已存在） | O(n) 移动元素 | O(1) 调整指针 |
| put（新插入） | O(n) 插入队首 | O(1) |
| put（缓存满） | O(n) 删除队尾 | O(1) |
数组的连续存储特性使得"移动到队首"操作需要 O(n) 的元素搬移，而链表的指针操作天然 O(1)。
6. 数组 vs 链表选择指南
| 场景 | 推荐结构 | 原因 |
|---|---|---|
| 频繁随机访问 | 数组 | O(1) 访问 |
| 频繁插入删除 | 链表 | 无需移动元素 |
| 缓存敏感场景 | 数组 | 连续内存，CPU 缓存友好 |
| 实现 LRU Cache | 哈希 + 双链表 | 双向删除 O(1) |
| 已知最大容量 | 循环数组 | 避免动态分配开销 |
CPU 缓存角度：数组的缓存命中率远高于链表，即使某些操作理论复杂度略高，实际运行可能更快。
实际性能对比
在 64 位系统中，缓存行（Cache Line）通常为 64 字节。假设存储 int64（8 字节）：
数组缓存友好：
基地址 + 0: [0, 1, 2, 3, 4, 5, 6, 7] ← 一次缓存行加载 8 个元素
基地址 + 64: [8, 9, 10, 11, 12, 13, 14, 15]
链表缓存不友好：
[数据: 0 | next: 0x7f...] → 跳转到 0x7f...
[数据: 1 | next: 0x3a...] → 跳转到 0x3a...
[数据: 2 | next: 0xe1...] → 跳转到 0xe1...
↑ 每个节点可能分布在不同内存页，缓存预加载失效
预取器（Prefetcher）效应：现代 CPU 的硬件预取器能检测数组的顺序访问模式，自动将后续数据加载到缓存。对于链表的随机指针跳转，预取器无法预测，导致频繁的缓存未命中（Cache Miss）。
经验法则：当数据量 < 1000 时，数组和链表的性能差异不大；当数据量 > 10000 且以遍历为主时，数组通常快 3-10 倍。
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。