w wyl123ly 的博客
MD

数据结构-线性结构

35 KB 2026.10.11 原文件

数据结构-线性结构

一句话概括

线性结构是元素之间只存在「一对一」前驱后继关系的数据组织方式:数组用连续内存换取随机访问的 ,链表用离散节点换取插入删除的 ,栈和队列是给操作加上纪律(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>、vectorLinkedList<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 应用二:表达式求值

计算机难以直接处理中缀表达式(要考虑优先级与结合性),经典做法有两步:

  1. 中缀转后缀(逆波兰表达式):用调度场算法(Shunting-yard),操作数直接输出,运算符与栈顶比较优先级后决定入栈或弹出。
  2. 后缀求值:从左到右扫描,遇操作数入栈,遇运算符弹出两个数计算后压回,最后栈中唯一值即结果。

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
队空0front == 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]:

  1. 若 p[j] == p[k],则 next[j+1] = k + 1(前缀后缀都延长一个字符)。
  2. 若不等,令 k = next[k-1] 继续比较(退到更短的前缀)。
  3. 若 k 退到 0 仍不等,则 next[j+1] = 0。

例题:模式串 p = "ababaca"

下标 0123456
字符ababaca
next[j]0012301

推导要点: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> 与 Java ArrayList 则是明确的 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 语言版)》,线性表、栈与队列的经典定义与循环队列判满条件