第16讲：链表

《计算机程序设计》

苏醒

计算机学院计算机研究所编译系统研究室

课前准备

• 在WSL Ubuntu中建立一个专门的目录用于课上练习，如~/course

$ mkdir ~/course

• 打开VSCode并连接到WSL，打开此目录并新建文件，如~/course/main.cpp
• 编辑main.cpp，随堂编程练习的代码请直接在此文件中编辑

main.cpp

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
  // ============= begin =============

  // =============  end  =============
  return 0;
}

温故

考考你

阅读程序，判断输出结果是什么？

quiz.cpp

#include <iostream>
enum Type { INVALID = 0, SHORT, INT, DOUBLE };
struct Data {
  Type type;
  union {
    short s;
    int i;
    double d;
  } value;
};
int main() {
  Data i = {INT, {.i = 0x00010002}};
  Data s = i;
  s.type = SHORT;
  std::cout << s.type << ' ' << s.value.s << std::endl;
  return 0;
}

学习目标

• 学习内容
  • 链表概念
  • 单向链表
  • 双向链表

学习目标

• 理解链表的概念、节点定义、内存布局
• 掌握链表操作的实现方法

一、链表

引入：数组的优势与局限性

考考你

我们学习过多种数组，包括静态长度数组、动态长度数组、以及动态内存分配数组空间等，请分析数组在数据管理与访问中的优劣势

数组

int n;
cin >> n;
int ii[100];                // 静态长度数组
double dd[n];               // 动态长度数组
float *pff = new float[n];  // 动态分配数组空间

优势

• 空间紧凑不浪费
• 随机访问能力

局限性

• 长度固定不能动态增长
• 插入、删除元素开销大

1.1 链表的概念

什么是链表？

链表

1.1 链表的概念

• 链表是一种线性数据结构
  • 由多个结点串联构成
  • 链表结点在内存中不一定连续，相邻结点通过指针连接

链表结点定义

struct Node {
  int data;        // 数据域
  Node *next;      // 指针域
};

考考你

在上述结构体中，data成员与next成员分别表示什么？

1.2 链表结点

明察秋毫

链表结点是一种自引用结构，即结构定义中包含了指向本结构的指针（指向其他结点）

链表结点定义

struct Node {
  int data;        // 数据域
  Node *next;      // 指针域
};

• 数据域：存储数据，根据应用需求可设计不同的数据成员
• 指针域：指向相邻结点，链表环环相扣之关键
  • 若指针域为nullptr，说明达到了链表尾部

考考你

与数组相比，链表的存储组织有何种不同，能够提供哪些优势，又有哪些不足？

1.3 单向链表与双向链表

考考你

采用下面的链表结点结构，若给定一个链表结点，能否找到它的后继结点与前驱结点？

链表结点定义

struct Node {
  int data;        // 数据域
  Node *next;      // 指针域
};

• 若链表结点中只包含一个指针域，则称为单向链表
• 若链表结点中同时包含指向前驱结点与后继结点的指针，则称为双向链表

双向链表结点定义

struct Node {
  int data;        // 数据域
  Node *prev;      // 前驱结点
  Node *next;      // 后继结点
};

单向链表

双向链表

1.4 链表操作

• 链表主要支持以下操作
  • 遍历链表
  • 在链表中查找节点（给定位置、给定值）
  • 在链表中插入节点（头部、尾部、给定位置）
  • 在链表中删除节点（头部、尾部、给定位置、给定值）
  • 建立链表（连续插入结点）
  • 清空链表（连续删除结点）

二、单向链表

单向链表

考考你

单向链表结点定义如下，问，使用何种数据结构引用一个单向链表？即，使用何种类型表示一个链表？

链表结点定义

struct Node {
  int data;        // 数据域
  Node *next;      // 指针域
};

明察秋毫

• 掌握了链表头（第一个结点），就掌握了整个链表！
  • 因此，只需一个链表头指针（Node *head）即可引用链表
  • 有时，再附加一个链表尾结点指针（Node *tail）

2.1 遍历链表

• 遍历所有链表结点打印结点数据

遍历链表

void printList(Node *head, Node *tail) {
  Node *p = head;
  while (p != nullptr) {
    cout << p->data << " ";
    p = p->next;
  }
}

遍历链表

遍历链表

遍历链表

遍历链表

Try it!

将while循环改为for循环，遍历链表的框架会更加清楚，试一试

遍历链表

void printList(Node *head, Node *tail) {
  for (Node *p = head; p != nullptr; p = p->next) {
    cout << p->data << " ";
  }
}

2.1 遍历链表

考考你

请编写代码，计算链表的长度

计算链表长度

int length(Node *head, Node *tail) {
  int count = 0;



  return count;
}

计算链表长度

int length(Node *head, Node *tail) {
  int count = 0;
  for (Node *p = head; p != nullptr; p = p->next) {
    ++count;
  }
  return count;
}

2.2 查找结点

• 查找结点有两种方式
  • 按序查找：给定结点在链表中的索引
  • 按值查找：给定结点的数据值

思路

有两种可行的循环策略：（1）以索引为迭代变量，循环index次；（2）以结点为迭代变量，直到索引index为止。

按序查找结点，策略（1）

Node *getNodeAt(Node *head, Node *tail, int index) {
  Node *p = head;
  for (int i = 0; i < index; ++i) {
    if (p == nullptr)
      return nullptr;
    p = p->next;
  }
  return p;
}

按序查找结点，策略（2）

Node *getNodeAt(Node *head, Node *tail, int index) {







}

按序查找结点，策略（2）

Node *getNodeAt(Node *head, Node *tail, int index) {
  int i = 0;
  for (Node *p = head; p != nullptr; p = p->next) {
    if (i == index)
      return p;
    ++i;
  }
  return nullptr;
}

2.2 查找结点

• 查找结点有两种方式
  • 按序查找：给定结点在链表中的索引
  • 按值查找：给定结点的数据值

提示

可能存在多个匹配，需要返回第一个匹配的结点

按值查找结点

Node* getNodeWith(Node *head, Node *tail, int value) {





}

按值查找结点

Node* getNodeWith(Node *head, Node *tail, int value) {
  for (Node *p = head; p != nullptr; p = p->next) {
    if (p->data == value)
      return p;
  }
  return nullptr;
}

2.3 插入结点

• 插入结点有三种方式
  • 在尾部之后插入
  • 在头部之前插入
  • 插入到指定位置

思路

无论在哪个位置插入，都需要完成以下操作

• 创建新结点
• 找到插入位置前一个结点（为什么？）

在尾部之后插入结点

Node *insertTail(Node *&head, Node *&tail, int value) {










}

在尾部之后插入结点

Node *insertTail(Node *&head, Node *&tail, int value) {
  Node *p = new Node;
  p->data = value;
  if (tail == nullptr) { // 空链表
    head = p;
    tail = p;
  } else {
    tail->next = p;
    tail = p;
  }
  return p;
}

2.3 插入结点

• 插入结点有三种方式
  • 在尾部之后插入
  • 在头部之前插入
  • 插入到指定位置

教员箴言

涉及修改链表的操作，务必注意空链表这一特殊情况的处理！

在头部之前插入结点

Node *insertHead(Node *&head, Node *&tail, int value) {








}

在头部之前插入结点

Node *insertHead(Node *&head, Node *&tail, int value) {
  Node *p = new Node;
  p->data = value;
  p->next = head;
  head = p;
  if (tail == nullptr) { // 空链表
    tail = p;
  }
  return p;
}

2.3 插入结点

• 插入结点有三种方式
  • 在尾部之后插入
  • 在头部之前插入
  • 插入到指定位置

提示

利用已经完成的按序查找结点函数getNodeAt()

考考你

可否交换第8行与第9行代码的位置？

在指定位置插入结点

Node *insertAt(Node *&head, Node *&tail, int index, int value) {











}

在指定位置插入结点

Node *insertAt(Node *&head, Node *&tail, int index, int value) {
  if (index == 0)
    return insertHead(head, tail, value);
  Node *pre = getNodeAt(head, tail, index - 1);
  if (pre) { // 如果 pre==tail，会发生什么？
    Node *p = new Node;
    p->data = value;
    p->next = pre->next;
    pre->next = p;
    return p;
  }
  return insertTail(head, tail, value);
}

在指定位置插入结点

Node *insertAt(Node *&head, Node *&tail, int index, int value) {
  if (index == 0)
    return insertHead(head, tail, value);
  Node *pre = getNodeAt(head, tail, index - 1);
  if (pre and pre != tail) { // 如果插入位置是尾部，交给第11行处理
    Node *p = new Node;
    p->data = value;
    p->next = pre->next;
    pre->next = p;
    return p;
  }
  return insertTail(head, tail, value);
}

2.4 删除结点

• 同插入结点类似，删除结点有三种方式
  • 删除头结点
  • 删除尾结点
  • 删除指定位置结点

删除头结点

Node *removeHead(Node *&head, Node *&tail) {







}

删除头结点

Node *removeHead(Node *&head, Node *&tail) {
  if (not head)
    return nullptr;
  Node *p = head;
  if (head == tail) // 只有一个结点
    tail = nullptr;
  head = head->next;
  return p;
}

2.4 删除结点

• 同插入结点类似，删除结点有三种方式
  • 删除头结点
  • 删除尾结点
  • 删除指定位置结点

删除尾结点

Node *removeTail(Node *&head, Node *&tail) {










}

删除尾结点

Node *removeTail(Node *&head, Node *&tail) {
  if (head == tail) { // 只有一个结点，或空链表
    Node *p = head;
    head = tail = nullptr;
    return p;
  }
  for (Node *p = head; p->next != tail; p = p->next) {}
  Node *oldTail = Tail;
  tail = p;
  tail->next = nullptr;
  return oldTail;
}

2.4 删除结点

• 同插入结点类似，删除结点有三种方式
  • 删除头结点
  • 删除尾结点
  • 删除指定位置结点

删除指定位置结点

Node *removeAt(Node *&head, Node *&tail, index index) {










}

删除指定位置结点

Node *removeAt(Node *&head, Node *&tail, int index) {
  if (index == 0)
    return removeHead(head, tail);
  Node *pre = getNodeAt(head, tail, index - 1);
  if (not pre)
    return nullptr;
  Node *p = pre->next;
  if (p == tail)
    return removeTail(head, tail);
  pre->next = p->next;
  return p;
}

2.5 建立链表

• 从空链表开始，依次增加多个结点，按照顺序分为
  • 建立正向链表：新结点追加到链表尾部
  • 建立反向链表：新结点追加到链表头部

建立正向链表

void createList(Node *&head, Node *&tail, int *values, int len) {













}

建立正向链表

void createList(Node *&head, Node *&tail, int *values, int len) {
  head = tail = nullptr;
  for (int i = 0; i < len; ++i) {
    Node *node = new Node;
    node->value = values[i];
    node->next = nullptr;
    if (head == nullptr) {
      head = node;
      tail = node;
    } else {
      tail->next = node;
      tail = node;
    }
  }
}

2.5 建立链表

• 从空链表开始，依次增加多个结点，按照顺序分为
  • 建立正向链表：新结点追加到链表尾部
  • 建立反向链表：新结点追加到链表头部

建立反向链表

void createReverseList(Node *&head, Node *&tail, int *values, int len) {










}

建立反向链表

void createReverseList(Node *&head, Node *&tail, int *values, int len) {
  head = tail = nullptr;
  for (int i = 0; i < len; ++i) {
    Node *node = new Node;
    node->value = values[i];
    node->next = head;
    head = node;
    if (tail == nullptr) {
      tail = node;
    }
  }
}

考考你

如果链表仅使用head指针维护（不维护tail指针），上述两种链表建立方式，哪种更高效？

2.6 清空链表

• 依次删除每个结点，直到链表为空

清空链表

void clearList(Node *&head, Node *&tail) {
  while (head) {
    Node *p = head;
    head = head->next;
    delete p;
  }
  tail = nullptr;
}

单向链表小结

明察秋毫

• 当对单向链表执行修改操作（插入、删除）时，需要注意的特殊情况包括
  • 链表为空
  • 链表仅有一个结点
  • 处理的节点位置为链表头或链表尾

考考你

• 使用head与tail指针维护链表，如何判定空链表与单一节点链表？若只使用head维护链表呢？

判定链表状态

// 使用head与tail指针
head == nullptr; // 链表为空
tail == nullptr; // 链表为空
head->next == nullptr; // 链表仅有一个结点
head == tail; // 空链表或者单结点链表

// 只使用head指针
head == nullptr; // 链表为空
head->next == nullptr; // 链表仅有一个结点

三、双向链表

3.1 双向链表

• 双向链表结点维护指向前驱与后继结点的双向指针
  • 支持高效的逆向遍历
  • 维护工作比单向链表稍多

双向链表结点定义

struct Node {
  int data;        // 数据域
  Node *prev;      // 前驱结点
  Node *next;      // 后继结点
};

双向链表

明察秋毫

双向链表的引用与维护必须同时使用head与tail指针

3.2 双向链表插入结点

考考你

补充完成双向链表的节点插入函数

双向链表插入结点

Node *insertAt(Node *&head, Node *&tail, int index, int value) {
  Node *p = new Node;
  p->data = value;
  





  






  return p;
}

双向链表插入结点

Node *insertAt(Node *&head, Node *&tail, int index, int value) {
  Node *p = new Node;
  p->data = value;
  Node *pre = nullptr, *post = head;
  for (int i = 0; i < index; ++i) {
    if (post == nullptr)
      break;
    pre = post;
    post = post->next;
  }






  return p;
}

双向链表插入结点

Node *insertAt(Node *&head, Node *&tail, int index, int value) {
  Node *p = new Node;
  p->data = value;
  Node *pre = nullptr, *post = head;
  for (int i = 0; i < index; ++i) {
    if (post == nullptr)
      break;
    pre = post;
    post = post->next;
  }
  p->prev = pre;
  p->next = post;
  if (pre) pre->next = p;
  if (post) post->prev = p;
  if (pre == nullptr) head = p;
  if (post == nullptr) tail = p;
  return p;
}

3.3 双向链表删除结点

考考你

补充完成双向链表的节点删除函数

双向链表删除结点

Node *removeAt(Node *&head, Node *&tail, int index) {
  














}

双向链表删除结点

Node *removeAt(Node *&head, Node *&tail, int index) {
  Node *p = head;
  for (int i = 0; i < index; ++i) {
    if (p == nullptr)
      break;
    p = p->next;
  }









}

双向链表删除结点

Node *removeAt(Node *&head, Node *&tail, int index) {
  Node *p = head;
  for (int i = 0; i < index; ++i) {
    if (p == nullptr)
      break;
    p = p->next;
  }
  if (p) {
    Node *pre = p->prev;
    Node *post = p->next;
    if (pre) pre->next = post;
    if (post) post->prev = pre;
    if (pre == nullptr) head = post;
    if (post == nullptr) tail = pre;
  }
  return p;
}

3.4 链表小结

思考

编写链表处理函数，如何正确维护链表的状态？

教员箴言

• 在执行每一个操作前
  • 考虑空链表、单结点链表、头尾结点等特殊情况
• 在执行每一个操作后
  • 确保头指针、尾指针、链条得到妥善更新（同样考虑特殊情况）

练习

考考你

借鉴双向链表结点的插入与删除实现方法（利用prev与post结点），重写单向链表的插入与删除函数（不再区别头部、尾部与中间结点）

在指定位置插入结点

Node *insertAt(Node *&head, Node *&tail, int index, int value) {
  Node *p = new Node;
  p->data = value;
  Node *prev = nullptr, *post = head;
  for (int i = 0; i < index; ++i) {
    if (post == nullptr)
      break;
    prev = post;
    post = post->next;
  }




  return p;
}

在指定位置插入结点

Node *insertAt(Node *&head, Node *&tail, int index, int value) {
  Node *p = new Node;
  p->data = value;
  Node *prev = nullptr, *post = head;
  for (int i = 0; i < index; ++i) {
    if (post == nullptr)
      break;
    prev = post;
    post = post->next;
  }
  p->next = post;
  if (pre) pre->next = p;
  if (pre == nullptr) head = p;
  if (post == nullptr) tail = p;
  return p;
}

练习

考考你

借鉴双向链表结点的插入与删除实现方法（利用prev与post结点），重写单向链表的插入与删除函数（不再区别头部、尾部与中间结点）

删除指定位置结点

Node *removeAt(Node *&head, Node *&tail, int index) {
  Node *prev = nullptr, *p = head;
  for (int i = 0; i < index; ++i) {
    if (p == nullptr)
      break;
    prev = p;
    p = p->next;
  }






  return p;
}

删除指定位置结点

Node *removeAt(Node *&head, Node *&tail, int index) {
  Node *prev = nullptr, *p = head;
  for (int i = 0; i < index; ++i) {
    if (p == nullptr)
      break;
    prev = p;
    p = p->next;
  }
  if (p) {
    Node *post = p->next;
    if (prev) pre->next = post;
    if (prev == nullptr) head = post;
    if (post == nullptr) tail = prev;
  }
  return p;
}

总结

本节内容

---
config:
  look: handDrawn
  themeVariables:
    fontSize: 20px
---
mindmap
链表
  链表概念
    内存布局
    结点定义
    单向与双向链表
    链表操作    
  单向链表操作
    遍历
    查找
    插入
    删除
    建立
    清空
    枚举变量的取值
  双向链表操作
    插入
    删除

学习目标

• 理解链表的概念、节点定义、内存布局
• 掌握链表操作的实现方法

课后作业

• 实训
  • C&C++线性表实训（截止时间2025.04.30）
• 下次课预告
  • 综合应用2：Python风格列表

计算机程序设计