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. 数组 vs 链表选择指南
| 场景 | 推荐结构 | 原因 |
|---|---|---|
| 频繁随机访问 | 数组 | O(1) 访问 |
| 频繁插入删除 | 链表 | 无需移动元素 |
| 缓存敏感场景 | 数组 | 连续内存，CPU 缓存友好 |
| 实现 LRU Cache | 哈希 + 双链表 | 双向删除 O(1) |
| 已知最大容量 | 循环数组 | 避免动态分配开销 |
CPU 缓存角度：数组的缓存命中率远高于链表，即使某些操作理论复杂度略高，实际运行可能更快。
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。