单链表、链式栈、链式队列核心知识点汇总

userId_undefined
MC不老，陪你到老！
时间刺客空间掌握者时空双修者贪心·贪心尝试者模拟·模拟练习生枚举·枚举小能手

2026-07-26 13:02:03

发布于：广东

19阅读
0回复
0点赞

C++ 单链表、链式栈、链式队列核心知识点汇总

全部基于手动动态节点（new/delete），不使用 STL list/stack/queue，适配CSP-J竞赛考点
统一节点基础范式：

struct Node{
    int data;
    Node *next;
    Node(int x):data(x),next(nullptr){}
};

一、单链表（基础链式结构）

1. 基本概念

  1. 由若干节点组成，每个节点 = 数据域 + 指针域
  2. 依靠指针串联，内存不连续；没有随机访问，只能从头遍历
  3. 分类：单链表、双向链表、循环单链表、带头结点/不带头结点链表

竞赛常用：带头结点单链表（统一空链表、头部插入删除逻辑，减少特判）

2. 核心操作复杂度

  • 头部插入/删除：\(O(1)\)
  • 尾部插入（无尾指针）：\(O(n)\)；有尾指针 \(O(1)\)
  • 根据值/位置查找：\(O(n)\)
  • 随机访问：不支持

3. 高频操作考点

  1. 头插法建表：新节点插在头结点后，逆序
  2. 尾插法建表：遍历找到表尾，顺序存储
  3. 指定位置插入节点
  4. 删除：按位置删除、按数值删除（删除所有相同值结点）
  5. 链表遍历、求长度、查找元素
  6. 链表原地反转（必考）
  7. 快慢指针：查找倒数第k个结点、寻找链表中点
  8. 判断链表是否有环、寻找环入口
  9. 两个有序链表合并、链表相交问题
  10. 有序链表去重、链表区间反转
  11. 内存释放：遍历逐个delete，防止内存泄漏

4. 优缺点

✅ 优点：动态分配内存，无需预先开辟空间；插入删除不需要移动大量元素
❌ 缺点：不能随机访问；额外占用指针空间；遍历耗时

5. 易错点

  • 操作时保存后继指针，防止断链
  • 空链表边界判断
  • 删除结点记得释放内存
  • 区分「带头结点」和「不带头结点」代码差异

二、链式栈（链表实现栈）

1. 基本概念

栈：后进先出 LIFO
链式栈：利用链表模拟栈，一般把链表头部作为栈顶

原因：头部插入删除 \(O(1)\)，如果选尾部做栈顶每次需要遍历到尾部，效率低
只需要一个指针 top 指向栈顶节点，不需要尾指针。

2. 核心操作

  1. push(x) 入栈：新建节点，插在top前面，更新top
  2. pop() 出栈：取出top节点，top后移，释放原栈顶
  3. getTop()：读取栈顶数据（不弹出）
  4. isEmpty()：判空 top == nullptr

3. 复杂度

所有操作：\(O(1)\)

4. 经典应用（CSP高频）

  1. 括号匹配 ()[]{}
  2. 进制转换（十进制→二/八/十六进制）
  3. 表达式处理：中缀表达式转后缀、后缀表达式求值
  4. 字符串逆序
  5. 递归迭代模拟、回溯
  6. 单调栈：寻找下一个更大/更小元素、最大矩形
  7. 最小栈设计（辅助栈保存最小值）

5. 链式栈 vs 顺序栈（数组栈）

✅ 链式栈：无容量上限，动态分配；不会栈溢出
❌ 链式栈：每个节点额外消耗指针；频繁new/delete开销

易错点

  • 空栈时禁止pop、取栈顶，必须先判空
  • 出栈顺序不要搞反
  • 清空栈需要循环pop释放所有节点

三、链式队列（你说的「链式列表」，竞赛标准名称）

1. 基本概念

队列：先进先出 FIFO
链式队列，维护两个指针：

  • front：队头（出队一端）
  • rear：队尾（入队一端）

2. 核心操作

  1. enqueue(x) 入队：新节点接到rear后面，更新rear
  2. dequeue() 出队：取出front节点，front后移
  3. getFront() 获取队首元素
  4. isEmpty() 判空 front == nullptr

特殊情况：队列只剩最后一个元素时，出队后需要把rear置空

3. 复杂度

入队、出队：\(O(1)\)

4. 经典应用（CSP高频）

  1. BFS广度优先搜索（迷宫、图遍历、二叉树层序遍历）
  2. 排队模拟、约瑟夫环问题
  3. 拓扑排序
  4. 单调队列：滑动窗口最值
  5. 两个队列实现栈；两个栈实现队列

5. 易错点

  1. 出队至队列为空时，rear指针必须置空，否则出现野指针
  2. 不能直接通过front==rear判断空满（链式队列无假溢出问题，和循环数组队列区分开）
  3. 先判空再执行出队、取队首

四、三者对比速记

结构 规则 核心指针 适用场景
单链表 无固定顺序，自由增删 head头指针 通用动态存储、各类链表算法
链式栈 LIFO后进先出 top栈顶指针 表达式、括号匹配、单调栈、回溯
链式队列 FIFO先进先出 front队头、rear队尾 BFS、层次遍历、滑动窗口、排队模拟

五、CSP必背区分考点

  1. 如果题目要求每次取最晚加入的数据 → 栈
  2. 如果题目要求按加入先后顺序依次取出 → 队列
  3. 如果需要任意位置插入、删除、查找 → 链表

打个广告：点此进入

链表，链式栈，链式列表题目

userId_undefined
去预览
0/2000

全部评论 6

热门讨论