链表

链表

单链表、双向链表、循环链表的结构与基本操作。

概念

链表用一组结点存元素，每个结点除数据域外还有指针域，按逻辑顺序把结点串起来。单链表每个结点只有一个后继指针；双向链表多一个前驱指针；尾结点指向头结点则成循环链表。与数组相比，链表不必连续占用内存，插入、删除已知位置时不必搬动大量元素，但不能像数组那样用下标随机访问。CSP-J 初赛常考「链表相对数组的特点」以及头插、后继插入等指针操作顺序；与 cspj.cpp.pointer 相邻——链表操作本质是指针赋值，与 cspj.ds.stack-and-queue 的区别在于链表是链式线性结构，栈队列是受限的访问顺序。

CSP-J 常考

• cspj-r1-2019 第 6 题：链表不具有随机访问任一元素的特点（四选一找「错误说法」）。
• cspj-r1-2020 第 7 题：同上形态，考查链表与数组访问方式的差异。
• cspj-r1-2022 第 4 题：数组大小固定、链表可动态调整——链表与数组的结构差异。
• cspj-r1-2022 第 11 题：双向循环链表在结点 p 之后插入结点 s，四段指针赋值语句选正确顺序。
• cspj-r1-2023 第 4 题：给定 head，在链表头部插入 data=42 的新结点，选正确 C++ 代码片段。

struct Node { int data; Node* next; };

// 在 head 前插入新结点（头插法）
Node* insertFront(Node* head, int x) {
    Node* p = new Node{x, head};
    return p;          // 新结点成为头指针
}

易错点

• 头插时忘记 head = newNode，只改了 next 却丢了新头指针。
• 双向链表插入时要同时改前驱、后继四个方向的指针，顺序写错会断链。
• 把「不必事先估计存储空间」理解成「不占空间」——链表仍要逐个结点分配内存。
• 删除结点时若还有别的指针指向它，应先改链再 delete，否则野指针。