第 3.0 章线性表

List

开场：从连续序列到可修改序列

播放器播放列表、浏览器历史记录、内存中的任务队列、文本编辑器的一行字符，都可以看成有前后顺序的一组元素。

关键问题不是“元素放在哪里”，而是：

怎样描述元素之间的前后关系
怎样按位置访问元素
怎样插入和删除元素
怎样比较不同实现的代价

学习目标

准确定义线性表 ADT
掌握顺序表的访问、查找、插入、删除
掌握单链表的节点、遍历、插入、删除
理解头结点、迭代器、双向链表、循环链表
使用链表解决 Josephus、多项式相加、倒数第 k 个结点
从时间、空间、局部性和边界条件多维比较顺序表与链表

路线图

线性表 ADT

线性表的数学定义

线性表是一个有限序列：

\[ L=(e_1,e_2,\ldots,e_n) \]

当 \(n=0\) 时，\(L\) 是空表。

当 \(n>0\) 时：

\(e_1\) 是第一个元素
\(e_n\) 是最后一个元素
\(e_i\) 直接前驱是 \(e_{i-1}\)
\(e_i\) 直接后继是 \(e_{i+1}\)

典型实例

线性表	元素	顺序含义
人员名单	人员记录	登记顺序或编号顺序
考试列表	exam1, exam2, exam3	时间顺序
星期	Mon, Tue, …, Sun	周期中的固定顺序
文本行	字符	字符出现顺序

线性表允许相同元素重复出现，因为位置也是信息的一部分。

工程连接：线性表在哪里出现

线性表是许多系统结构的底层形态。

Linux 链表常用于内核对象队列和等待队列

Redis 列表、压缩列表和 quicklist 体现顺序存储权衡

C++ STL vector 与 list 对应连续数组和链式节点

PostgreSQL 执行计划节点和临时结果常以序列方式处理

顺序表通常 cache locality 好；链表插入删除局部操作快，但指针跳转更容易产生 cache miss。

ADT 操作集合

操作	含义	常见返回
`Create()`	创建空表	表对象
`IsEmpty()`	判断是否为空	`bool`
`Length()`	返回元素个数	`int`
`Find(k)`	返回第 `k` 个元素	元素或失败
`Search(x)`	查找元素 `x` 的位置	下标或失败
`Delete(k)`	删除第 `k` 个元素	被删元素或失败
`Insert(k, x)`	在位置 `k` 处插入 `x`	成功或失败

顺序表：数组表示

顺序表的定位公式

若每个元素占用 sizeof(T) 字节，并且数组首地址是 base，则第 \(i\) 个物理单元的位置为：

\[ \operatorname{location}(i)=base+i\times sizeof(T) \]

因此，按下标访问是 \(O(1)\)。

查找元素仍然需要逐个比较，顺序查找最坏为 \(O(n)\)。

顺序查找的平均比较次数

在元素等概率出现在任意位置时，成功查找的平均比较次数为：

\[ ACN=\frac{1+2+\cdots+n}{n}=\frac{n+1}{2} \]

找不到元素时，需要比较全部 \(n\) 个元素。

顺序表插入与删除

删除移动次数

删除下标 \(i\) 的元素时，右侧元素需要左移。

若表长为 \(n\)，删除位置等概率，则平均移动次数为：

\[ \frac{(n-1)+(n-2)+\cdots+1+0}{n}=\frac{n-1}{2} \]

删除的时间复杂度是 \(O(n)\)。

插入移动次数

在下标 \(i\) 处插入时，需要从尾部开始右移。

若允许插入到 \(0,1,\ldots,n\) 共 \(n+1\) 个位置，平均移动次数为：

\[ \frac{n+(n-1)+\cdots+1+0}{n+1}=\frac{n}{2} \]

插入的时间复杂度是 \(O(n)\)。

顺序表的优点与限制

维度	结论
按下标访问	\(O(1)\)，非常快
顺序扫描	内存连续，缓存友好
中间插入	需要移动元素，\(O(n)\)
中间删除	需要移动元素，\(O(n)\)
容量变化	静态数组容量固定；动态数组扩容有额外代价

C++ 顺序表接口

template <class T>
class ArrayList {
 public:
  explicit ArrayList(int capacity = 16);

  bool empty() const;
  int size() const;
  const T& get(int index) const;
  int search(const T& value) const;
  void insert(int index, const T& value);
  T erase(int index);

 private:
  void ensureCapacity();

  std::vector<T> data_;
  int size_ = 0;
};

单链表节点

单链表的每个节点包含两个部分：

data：元素值
next：指向下一个节点

template <class T>
struct Node {
  T data;
  Node* next;

  Node(const T& value, Node* next_node = nullptr)
      : data(value), next(next_node) {}
};

单链表的基本图像

最后一个节点的 next 是 nullptr。

单链表插入

插入代码：已知前驱节点

template <class T>
void insertAfter(Node<T>* before, const T& value) {
  if (before == nullptr) {
    return;
  }
  Node<T>* node = new Node<T>(value, before->next);
  before->next = node;
}

先令新节点指向原后继，再令前驱指向新节点。顺序不能反。

单链表删除

删除代码：已知前驱节点

template <class T>
bool eraseAfter(Node<T>* before) {
  if (before == nullptr || before->next == nullptr) {
    return false;
  }
  Node<T>* victim = before->next;
  before->next = victim->next;
  delete victim;
  return true;
}

删除本身是 \(O(1)\)，但定位前驱通常需要 \(O(n)\)。

头结点

头结点是不存放有效数据的哨兵节点。

它的作用是统一边界情况：

空表：header->next == nullptr
首元素插入：等价于在 header 后插入
首元素删除：等价于删除 header 后的节点
迭代器起点：zeroth() 可以返回头结点位置

带头结点的链表类骨架

template <class T>
class LinkedList {
 public:
  LinkedList();
  ~LinkedList();

  bool empty() const;
  void clear();
  Node<T>* beforeBegin() const;
  Node<T>* begin() const;
  Node<T>* find(const T& value) const;
  Node<T>* findPrevious(const T& value) const;
  void insertAfter(Node<T>* position, const T& value);
  bool remove(const T& value);

 private:
  Node<T>* header_;
};

查找与前驱查找

template <class T>
Node<T>* LinkedList<T>::find(const T& value) const {
  Node<T>* current = header_->next;
  while (current != nullptr && current->data != value) {
    current = current->next;
  }
  return current;
}

template <class T>
Node<T>* LinkedList<T>::findPrevious(const T& value) const {
  Node<T>* current = header_;
  while (current->next != nullptr && current->next->data != value) {
    current = current->next;
  }
  return current;
}

find 返回目标节点，findPrevious 返回目标节点的前驱。

删除指定值

template <class T>
bool LinkedList<T>::remove(const T& value) {
  Node<T>* previous = findPrevious(value);
  if (previous->next == nullptr) {
    return false;
  }
  Node<T>* victim = previous->next;
  previous->next = victim->next;
  delete victim;
  return true;
}

查找前驱是 \(O(n)\)，指针重连是 \(O(1)\)。

双向链表与循环链表

双向链表删除

删除当前节点 p 时：

p->prev->next = p->next;
p->next->prev = p->prev;
delete p;

若有表头结点且是循环双向链表，首尾删除也可以使用同一套语句。

循环链表：Josephus 问题

Josephus 算法

std::vector<int> josephus(int n, int m) {
  std::list<int> circle;
  for (int i = 1; i <= n; ++i) {
    circle.push_back(i);
  }
  std::vector<int> order;
  auto it = circle.begin();
  while (circle.size() > 1) {
    for (int count = 1; count < m; ++count) {
      ++it;
      if (it == circle.end()) it = circle.begin();
    }
    order.push_back(*it);
    it = circle.erase(it);
    if (it == circle.end()) it = circle.begin();
  }
  order.push_back(circle.front());
  return order;
}

多项式 ADT

多项式可以用数组表示，也可以用链表表示。

数组适合最高次数不大且稠密的多项式：

\[ p(x)=3x^8-5x^3+3x-1 \]

链表适合最高次数很大但非零项很少的多项式：

\[ p(x)=10x^{1000}+5x^{14}+1 \]

多项式链表表示

每个节点保存一个非零项：

struct Term {
  int coefficient;
  int exponent;
  Term* next;
};

节点按指数从大到小排列，可以把多项式相加转化为两个有序链表的归并。

多项式相加

多项式相加代码

Term* addPolynomial(Term* a, Term* b) {
  Term dummy{0, 0, nullptr};
  Term* tail = &dummy;
  while (a != nullptr && b != nullptr) {
    if (a->exponent == b->exponent) {
      int coef = a->coefficient + b->coefficient;
      if (coef != 0) {
        tail->next = new Term{coef, a->exponent, nullptr};
        tail = tail->next;
      }
      a = a->next;
      b = b->next;
    } else if (a->exponent > b->exponent) {
      tail->next = new Term{a->coefficient, a->exponent, nullptr};
      tail = tail->next;
      a = a->next;
    } else {
      tail->next = new Term{b->coefficient, b->exponent, nullptr};
      tail = tail->next;
      b = b->next;
    }
  }
  tail->next = cloneList(a != nullptr ? a : b);
  return dummy.next;
}

多项式相加复杂度

设两个多项式分别有 \(m\) 项和 \(n\) 项。

每一步至少推进 a 或 b 中的一个指针，因此总步数不超过 \(m+n\)。

\[ T(m,n)=O(m+n) \]

最坏情况是两个多项式指数交错，例如：

\[ A=a_5x^5+a_3x^3+a_1x+a_0 \]

\[ B=b_4x^4+b_2x^2+b_0 \]

习题：倒数第 k 个结点

倒数第 k 个结点代码

template <class T>
bool kthFromEnd(Node<T>* header, int k, T& answer) {
  if (k <= 0) return false;
  Node<T>* fast = header->next;
  Node<T>* slow = header->next;
  for (int i = 0; i < k; ++i) {
    if (fast == nullptr) return false;
    fast = fast->next;
  }
  while (fast != nullptr) {
    fast = fast->next;
    slow = slow->next;
  }
  answer = slow->data;
  return true;
}

只扫描一遍链表，时间 \(O(n)\)，额外空间 \(O(1)\)。

游标链表

游标链表的分配与释放

int alloc() {
  int p = cursorSpace[0].next;
  if (p == 0) {
    throw std::bad_alloc();
  }
  cursorSpace[0].next = cursorSpace[p].next;
  return p;
}

void freeNode(int p) {
  cursorSpace[p].element = T{};
  cursorSpace[p].next = cursorSpace[0].next;
  cursorSpace[0].next = p;
}

数组下标承担指针角色，cursorSpace[0] 管理空闲链表。

链表应用：桶排序

顺序表与链表的多维比较

维度	顺序表	单链表
按下标访问	\(O(1)\)	\(O(n)\)
查找某值	\(O(n)\)	\(O(n)\)
已知位置后插入	平均移动 \(n/2\)	改两条指针，\(O(1)\)
已知前驱后删除	平均移动 \((n-1)/2\)	改一条指针，\(O(1)\)
空间局部性	好	较差
额外空间	少	每个节点多一个或多个指针
扩容	动态数组可能整体搬迁	单个节点动态分配

选择结构的判断方法

场景	更合适的结构	原因
频繁按下标访问	顺序表	\(O(1)\) 定位
频繁中间插入删除且位置已知	链表	不需要移动大量元素
需要缓存友好扫描	顺序表	连续内存
容量变化剧烈且不需要随机访问	链表	节点按需分配
需要从当前节点访问前驱	双向链表	有 `prev` 指针
需要循环报数或轮转	循环链表	末尾自然回到开头

本节小结

线性表是有限、有序的元素序列
ADT 描述操作契约，不绑定具体实现
顺序表的核心优势是随机访问和缓存局部性
顺序表中间插入删除需要移动元素
链表的核心优势是指针重连
链表需要额外指针空间，并且按位置访问慢
头结点可以统一边界条件
双向链表、循环链表和游标链表分别解决不同工程约束

练习 1：顺序表删除移动次数

长度为 \(8\) 的顺序表删除下标 \(2\) 的元素。

答案：

右侧下标 \(3,4,5,6,7\) 的元素左移，共移动 \(5\) 次。

若删除位置等概率，平均移动次数为：

\[ \frac{7+6+5+4+3+2+1+0}{8}=3.5 \]

练习 2：单链表删除

已知 before 指向待删除节点的前驱，删除 before->next。

答案：

Node<T>* victim = before->next;
before->next = victim->next;
delete victim;

先保存待删除节点，再绕过它，最后释放。

练习 3：多项式相加

给定：

\[ A(x)=2x^{100}+3x^{14}+2x^8+1 \]

\[ B(x)=-2x^{100}+8x^{14}-3x^{10}+10x^6-x \]

答案：

\[ A(x)+B(x)=11x^{14}-3x^{10}+2x^8+10x^6-x+1 \]

练习 4：反转单链表

template <class T>
Node<T>* reverse(Node<T>* head) {
  Node<T>* prev = nullptr;
  Node<T>* cur = head;
  while (cur != nullptr) {
    Node<T>* next = cur->next;
    cur->next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

每个节点的指针只修改一次，时间 \(O(n)\)，额外空间 \(O(1)\)。

第 3.0 章 线性表