链表是一种线性数据结构，各个元素节点通过记录下一节点地址的引用（指针）连接，内存无需连续。由于保存了引用，在相同数据量下，链表比数组占用更多的内存空间。

image-20260602111735683

链表的节点结构

struct ListNode {
  int val;
  ListNode* next;
  ListNode(int x): val(x), next(nullptr) {}
}

链表常用操作

初始化链表

ListNode* n0 = new ListNode(1);
ListNode* n1 = new ListNode(2);
n0->next = n1;

通常将头节点作为链表的简称。

插入节点

链表中插入节点只需要改变当前节点和前一个节点的引用。

image-20260602142147098

void insert(ListNode* n0, ListNode* P) {
  ListNode* n1 = n0->next;
  n0->next = P;
  P->next = n1;
}

删除节点

删除节点只需要改变一个节点的引用。

image-20260602144516594

void remove(ListNode* n0) {
  if (n0->next == nullptr) {
    return;
  }
  
  ListNode* P = n0->next;
  ListNode* n1 = P->next;
  n0->next = n1;
  delete P;
}

访问节点

在链表中，程序需要从头节点出发访问目标节点。

ListNode* access(ListNode* head, int index) {
  for (int i = 0; i < index; ++i) {
    if (head == nullptr) {
      return nullptr;
    }
    head = head->next;
  }
  
  return head;
}

查找节点

int find(ListNode* head, int target) {
  int index = 0;
  while (head != nullptr) {
    if (head->val == target) return index;
    head = head->next;
    ++index;
  }
  
  return -1;
}

常见链表类型

image-20260602145834877

struct ListNode {
  int val;
  ListNode* next;
  ListNode* prev;
  ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}
}

链表应用

栈

队列

哈希表（解决哈希冲突）

图（邻接表）

红黑树

B树

浏览器历史

LRU算法

时间片轮转调度（环形链表）

数据缓冲区（环形链表）：在音频、视频播放器中，数据流被分成多个缓冲块放入环形链表中。

Q&A

Q: 可以直接使用 ListNode a(); 来定义新变量吗？

struct ListNode {
  int val;
  ListNode* next;
  ListNode(int x): val(x), next(nullptr) {}
}

A：不可以，在 C++ 中，一旦你自定义了任意一个构造函数，编译器就不会再自动生成默认的无参构造函数。即使你的结构体里有无参构造函数，ListNode a(); 这行代码在 C++ 中也不会被解析为“定义一个变量”，而是会被编译器当成声明了一个返回 ListNode 类型、名为 a、且没有参数的函数。

正确的定义方式

ListNode a(10); //栈上分配
ListNode* a = new ListNode(10); //堆上分配，使用完后记得 delete a;

struct ListNode {
  int val;
  ListNode* next;
  // 补充无参构造函数
  ListNode() : val(0), next(nullptr) {} 
  
  ListNode(int x): val(x), next(nullptr) {}
};
ListNode a; //

如果是用 ListNode() = default; 则会引入垃圾值问题。

Q：如何优雅地解决“垃圾值”问题？

A：对内置类型成员（int, double, 指针等），直接使用这个默认构造函数创建对象，其内置类型的成员变量将包含内存中的随机垃圾值（未定义行为）。

对自定义类型成员（如 std::string, 其他类等），它会调用该成员自己的默认构造函数来进行初始化。如果某个自定义类型的成员没有默认构造函数，编译就会直接报错。

推荐使用成员默认初始化方式。

struct ListNode {
    int val = 0;          // 默认初始化为 0
    ListNode* next = nullptr; // 默认初始化为空指针
};

int main() {
    ListNode a; // 此时 a.val 是 0，a.next 是 nullptr，非常安全
}

Q: 数组对比链表

A：

image-20260602145702425