顺序表与链表：从底层原理到性能选型，手写实现与避坑指南

先别急着写代码，我先把话说在前头：顺序表和链表，这两个名字只要是学计算机的，基本都躲不掉。面试会问，考研要考，很多学校的课程设计里还要用它们各写一遍“图书信息管理系统”。我当年实习面试的时候，被面试官问过一个问题，“ArrayList和LinkedList在日常代码里到底怎么选”，当时我把两者的区别背得滚瓜烂熟，结果他一句话把我问住了：那如果现在让你手写一个顺序表的扩容，你会写成什么样的？那一瞬间我才发现，会背概念和真正理解底层差别是两回事。

这篇文章就是把顺序表和链表彻底掰开揉碎讲一次，不打算讲高深的理论，而是直接对着一行行代码拆，把为什么要这么写、踩过哪些坑、怎么排查，全部抖出来。适合正在学数据结构的学生、准备面试的求职者，还有那些用C语言写课设、拿Java写业务代码但一直不太清楚底层逻辑的人。看完你能自己实现一个像样子的顺序表和链表，也能在“选哪个”这个问题上说出个一二三来。

1. 线性表是什么：顺序表与链表的核心设计思路

先从最底层说起。顺序表和链表，本质上是同一种抽象数据结构——线性表——的两种物理存储实现。所谓线性表，就是元素之间存在一对一关系、逻辑上排成一条线的数据集合。这个“逻辑上排成一条线”很关键，因为它只规定了元素之间有前驱和后继，但并没有规定它们在内存里具体怎么摆。

1.1 顺序表：一块连续内存上的“抽屉柜”

顺序表，说白了就是“数组外加大动态管理”。它要求所有元素在内存里连续存放，就像一栋楼的信箱，一个格子挨着一个格子。因为连续，所以每个元素的位置可以直接算出来：第 i 个元素的地址等于首地址加上 i 乘元素大小。这就是“随机访问”的数学基础——我想找第 10 个元素，不用从头数，直接按公式定位，时间是 O(1)。

这个特性带来了一个非常明显的结果：顺序表最适合“按位置取值”的场景。你拿一个长度为十万的数组，想取中间某个位置的元素，一条指令就出来了。代价是什么？代价就是插入和删除很痛。你往中间插一个元素，后面的所有元素都得往后挪一位。我实测过一个一百万长度的顺序表，在头部插入元素，一次操作要搬移将近一百万个元素，哪怕每个元素只是搬一个 int，累加起来也是肉眼可见的卡顿。删除同理，得把后面的都往前补。

1.2 链表：一串散落在内存里的“珍珠项链”

链表不走连续路线，它的每一个节点单独存放，节点之间靠指针串起来。每个节点由两部分组成：数据域存数据，指针域存下一个节点的地址。你可以把它想象成寻宝游戏——手里只有一张纸条，上面写着第一个宝箱的位置，打开宝箱，里面才有第二个宝箱的线索，一环扣一环。

链表的第一个直接好处是插入删除不需要搬元素。只要我手里有某个节点的指针，在这个节点后面插一个新节点，只需要改两个指针的指向，时间复杂度是 O(1)。但代价也同样直接：查找很慢，因为不支持随机访问。我想找第 10 个节点，必须从头节点开始，一个节点一个节点地往后“跳”，平均要走 n/2 步，时间复杂度 O(n)。

这里就出现了一个特别容易误导新手的说法：“链表插入快，数组插入慢，所以链表比数组好。”这种说法是不完整的。链表插入快的前提是——你已经知道前驱节点的位置。如果只知道位置编号，比如“在第 5 个位置插入”，链表同样要从头开始遍历找到第 4 个节点，这一趟 O(n) 的查找已经把插入的 O(1) 优势抵消了。所以准确的说法应该是：链表擅长的是“已知前驱节点”的插入和删除，顺序表擅长的是“按位置取值”。这是整个选型问题的底层逻辑。

1.3 逻辑结构相同，物理存储不同，仅此而已

理解这两者最简单的方法，就是记住一句话：线性表是抽象的规则，顺序表和链表是两种具体的实现方案。同一个线性表的需求，比如“图书信息管理系统”，既可以用顺序表做，也可以用链表做。差异只体现在操作效率和内存占用上：顺序表空间连续、内存密度高、没有额外指针开销；链表每个节点多花一个指针的空间，但内存分配可以按需进行，不会因为频繁扩容造成空间浪费。

我在后面几节里会分别给出两种实现的核心代码，并且用“图书信息管理”这个场景把两种方案都走一遍。你会发现，同一个业务逻辑，用不同结构写出来的代码风格差异很大，但最终效果都能跑。这就是数据结构的魅力——解决问题的方式不止一种，关键是想清楚代价。

2. 手写顺序表：数组、扩容与图书信息管理实战

顺序表实现起来比链表简单，但正因为简单，很多人会忽略一些关键细节。我在网上看到不少代码，要么没有扩容，要么扩容写死了只加一个容量，要么没有判满。这些都是在真实项目里会炸雷的地方。下面用 C 语言和 Java 各讲一遍，逻辑完全等价，语言只是表达方式不同。

2.1 C 语言顺序表：结构体、动态数组、判满与扩容

C 语言没有面向对象机制，习惯上先用结构体描述“顺序表”这个类型。举个例子，我要实现一个图书信息顺序表：

#define MAX_SIZE 100 // 初始容量 typedef struct { int id; // 图书编号 char title[50]; // 书名 char author[20]; // 作者 double price; // 价格 } Book; typedef struct { Book *data; // 动态数组指针 int length; // 当前元素个数 int capacity; // 当前容量 } SeqList;

一定要用动态数组指针，不要直接写死一个 Book data[MAX_SIZE]。写死的问题在于容量固定，如果图书数量超过 100，程序直接崩溃或者溢出。动态数组的好处是可以扩容：满了就重新申请一块更大的内存，把原数据搬过去，再释放旧内存。

扩容逻辑我建议写成独立函数，不要塞在主逻辑里：

void ensureCapacity(SeqList *list, int minCapacity) { if (minCapacity <= list->capacity) { return; } int newCapacity = list->capacity + (list->capacity >> 1); // 扩容1.5倍 if (newCapacity < minCapacity) { newCapacity = minCapacity; } Book *newData = (Book *)malloc(sizeof(Book) * newCapacity); if (newData == NULL) { printf("内存分配失败\n"); exit(EXIT_FAILURE); } for (int i = 0; i < list->length; i++) { newData[i] = list->data[i]; // 逐元素拷贝 } free(list->data); list->data = newData; list->capacity = newCapacity; }

扩容倍数选 1.5 而不是固定加 10，是有讲究的。如果每次只加一个固定值，那么插入 N 个元素的整体代价是 O(N^2)，因为每次扩容都要搬一次全部数据。如果按倍数扩容，总搬移次数会收敛到 O(N)，均摊下来每次插入就是 O(1)。Java 的 ArrayList 就是从 10 开始，每次扩容到 1.5 倍；C++ 的 vector 常见做法是扩到 2 倍。倍数也不是越大越好，太大浪费内存，太小频繁搬移，1.5 到 2 倍之间是工程里的常见折中。

有一个实现细节必须提醒：C 语言里结构体直接赋值属于浅拷贝，像 Book 这种纯数据字段没问题，但如果结构体里有指针字段，浅拷贝会让新旧两块内存里的指针指向同一块地址，释放时会造成 double free。图书信息这个场景里都是定长字符串，所以逐元素赋值可行。如果你的结构体包含动态字符串或嵌套指针，建议写成深拷贝函数。

2.2 顺序表的基本操作：插入、删除与按位查找

插入操作的核心是先判满、再判位置、再搬移。我见过一堆代码漏了判位置，或者判断条件写成i > length而不是i > length。正确写法是插入位置的合法范围是 1 到 length+1（假设 1 为起始下标），对应数组下标是 0 到 length。

int seqListInsert(SeqList *list, int pos, Book book) { if (pos < 1 || pos > list->length + 1) { printf("插入位置非法\n"); return 0; } ensureCapacity(list, list->length + 1); // 从最后一个元素开始往后搬，防止覆盖 for (int j = list->length; j >= pos; j--) { list->data[j] = list->data[j - 1]; } list->data[pos - 1] = book; list->length++; return 1; }

循环方向必须从后往前，这是新手最容易写错的地方。如果从前往后搬，后一个元素还没来得及搬走就被前一个覆盖了，数据会全部错位。删除操作反过来，从前往后补位：

int seqListDelete(SeqList *list, int pos, Book *deleted) { if (pos < 1 || pos > list->length) { printf("删除位置非法\n"); return 0; } if (deleted != NULL) { *deleted = list->data[pos - 1]; } for (int j = pos; j < list->length; j++) { list->data[j - 1] = list->data[j]; } list->length--; return 1; }

注意删除后我并没有清空末尾那个元素的残留数据，这是刻意为之。length 已经减一，后面再插入元素会直接覆盖它，清不清空不影响逻辑。但我见过一种“强迫症”写法，把末尾元素 memset 成 0，这在某些调试工具下确实能让内存看上去干净，但完全没必要，还会白白浪费时间。

2.3 Java 版本：ArrayList 的底层逻辑与手写 val

热词里有“java顺序表代码”，说明很多人想搞清楚 ArrayList 底层到底干了什么。其实 Java 的 ArrayList 就是一个封装良好的动态顺序表：内部是 Object[] 数组，size 记录元素个数，ensureCapacityInternal 负责扩容。不同之处在于 Java 扩容时会调用 System.arraycopy 这个 native 方法来做批量搬移，效率比手写循环高很多。

面试官喜欢问的一个点是：ArrayList 默认构造函数创建出来的对象，底层数组其实是空数组，只有在第一次 add 元素时才真正创建容量为 10 的数组。这叫懒加载，目的是省内存。如果你写一个手写版，我建议也这样设计，代码量不大但细节拉满。

public class MyArrayList<T> { private Object[] data; private int size; private static final int DEFAULT_CAPACITY = 10; public MyArrayList() { data = new Object[0]; size = 0; } public void add(T item) { ensureCapacity(size + 1); data[size++] = item; } private void ensureCapacity(int minCapacity) { if (data.length >= minCapacity) { return; } int newCapacity = data.length == 0 ? DEFAULT_CAPACITY : data.length + (data.length >> 1); if (newCapacity < minCapacity) { newCapacity = minCapacity; } Object[] newData = new Object[newCapacity]; for (int i = 0; i < size; i++) { newData[i] = data[i]; } data = newData; } }

为什么扩容用 1.5 倍而不是 2 倍？Java 官方给出的源码就是oldCapacity + (oldCapacity >> 1)，右移一位相当于除以 2。1.5 倍的好处是扩容后留下的“空洞”更小，内存利用率更高，同时仍然保证均摊 O(1) 的插入成本。如果你自己设计动态数组，建议直接抄这个策略。

2.4 图书信息顺序表：一个能把课设分数拉高的完整套路

“图书信息顺序表c语言”是课设里出现频率极高的题目。结构通常是：每本书有编号、书名、作者、价格，需要实现增删改查、按编号排序、按书名查找等功能。我把自己做完这个题目的经验给你梳理一下。

功能设计上，我建议分四层：菜单层、操作层、存储层、数据层。菜单层只负责打印选项和接收输入；操作层把业务逻辑组织成函数；存储层就是上一节的结构体和增删改查；数据层可以做一个从文件初始化顺序表的功能。分层的核心价值在于，出问题的时候能快速定位是输入解析的锅、还是业务逻辑的锅、还是存储结构的锅，不用一杆子捅到底。

一个容易拿分的小技巧是：初始化时支持从 CSV 文件批量导入图书，而不是每次都在控制台手动录入。这个功能听起来简单，但能把“学好数据结构”从口号变成可见的工程能力。核心代码就是把文件打开，逐行解析字段，不断调用插入函数。注意解析字符串时要去掉换行符，否则书名末尾会带一个\n，打印的时候看不出，但比对时永远相等不了。

查找功能建议做两个：按编号查找用顺序遍历，同时可以顺便演示顺序表的随机访问优势——如果编号刚好是数组下标或者排序后有序，可以直接二分。我在课设里实测过，十万条记录的顺序表，二分查找比顺序查找快了不止一个数量级。

3. 单链表、循环链表、双链表：三种形态的构建与操作细节

链表不是只有一种长相。根据指针的分布方式，常见的有单链表、循环单链表、双链表。很多人教材背得很溜，到了自己写代码就开始蒙——原因很简单：不能亲手构建这三种结构，就没有形成空间想象能力。下面逐一拆解。

3.1 带头结点和不带头结点的单链表：先搞清边界条件

单链表是最基础的形态，每个节点只有一个 next 指针，指向后继节点，最后一个节点 next 指向 NULL。区别“带头结点”和“不带头结点”，核心看的是：链表是否有一个辅助的、不存数据的头结点。

带头结点的链表长这样：

typedef struct Node { Book data; struct Node *next; } Node; typedef struct { Node *head; // 指向头结点，头结点不含数据 int length; } LinkedList;

头结点的 next 指向真正的第一个数据节点。这样做的好处是：空表时 head->next 为 NULL，插入删除的代码逻辑完全统一，不需要单独讨论“删除第一个节点”的特殊情况。因为不管删除的是第几个节点，你操作的都是“当前节点的前一个节点的 next 指针”，而头结点永远存在，总能作为那个“前一个节点”。

不带头结点的链表则完全相反：head 直接指向第一个数据节点。空表时 head 为 NULL。这种情况下，头插、尾插、删除首节点都必须单独写分支。比如删除首节点，你要先拿一个临时指针记住当前 head，再把 head 更新为 head->next，最后释放临时指针。这个操作和删除非首节点完全不同，得写两套逻辑。

不带头结点的链表还涉及一个 C 语言经典问题：在函数里修改 head 本身，必须传二级指针，或者返回新 head。我的习惯是写不带返回值，直接用Node **head做参数，这样语义更明确——你是要修改调用者手里的那个头指针。改成*head = (*head)->next之后，调用方看到的就是新节点。如果用 Java/Python 写，没有这种指针语法，类属性本身可以变，边界条件会容易处理一些，但概念上还是要注意。

3.2 指定位置插入单链表的正确姿势与热词解读

“在指定位置插入建立单链表”这个热词，其实是两道题混在一起了：一是在链表的指定位置插入一个新节点，二是通过不断在尾部插入建立一整条链表。我先说第一种，同时也是面试手写的高频题。

int insertAtPos(Node *head, int pos, Book data) { if (head == NULL || pos < 1) { return 0; } Node *cur = head; // 从头结点开始 int i = 0; // 找到第 pos-1 个节点，也就是待插入位置的前驱 while (cur != NULL && i < pos - 1) { cur = cur->next; i++; } if (cur == NULL) { return 0; // 前驱节点不存在，插入位置非法 } Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = data; newNode->next = cur->next; cur->next = newNode; return 1; }

这里最关键的顺序是：先把新节点的 next 指向后一个节点，再把前驱节点的 next 指向新节点。这个顺序绝对不能反过来。如果先执行cur->next = newNode，原来 cur 后面的节点就彻底丢失了，链表从中间断开。这个错误特别隐蔽，因为编译不报错、运行时也经常能打印出看似正常的前半段数据，只有遍历到后半段才发现数据凭空消失。

第二种“建立单链表”的常用方法是尾插法：维护一个 tail 指针记录当前链表最后一个节点，每次新节点直接接在 tail 后面，然后移动 tail。尾插法保持了数据在链表中的顺序，适合从文件中批量读入数据构建链表。与之相对的是头插法，新节点总是插在第一个位置，读入的数据顺序会被反转——这在某些场景下是特性，但在图书管理这种需要保持顺序的场景就是雷。

3.3 循环单链表：遍历结束条件变了，死循环风险也来了

循环单链表的特点是最后一个节点的 next 不是 NULL，而是指回头结点。这样整个链表形成一个环。好处是任何位置开始都能遍历完整条链，约瑟夫环这类问题也因此很自然地用循环链表实现。

判断遍历结束的条件不能再是cur == NULL，而必须是cur->next != head（或cur != head，取决于起始位置）。我踩过最经典的坑是把头结点的判断丢了，结果while (cur != NULL)直接变成死循环——因为链表里永远不会有 NULL。解决办法有两种：先保存头结点地址，Node *start = head; while (cur->next != start)；或者用 do-while 结构保证先执行一次再判断，这个在空表的时候也可以安全退出。

约瑟夫环实现起来其实就是：从循环链表的某个位置开始，每数到第 m 个节点就删除它，然后从下一个节点重新计数。删除节点的代码和普通单链表删除一模一样，但要格外注意当链表只剩下一个节点时，它的 next 指向自己，此时不能删除它，那是游戏结束条件。我见过很多人在这一步提前 free，最后打印结果时访问了野指针，程序直接崩掉。

3.4 双链表：四个指针关系，慢动作拆解

双链表每个节点有 two 个指针：prior（前驱）和 next（后继）。好处是既可以前任方向遍历，也可以后任方向遍历。删除一个节点时，不需要像单链表那样先找前驱，因为当前节点的 prior 直接指向前驱。代价是每个节点多一个指针，内存开销更大，插入和删除操作要维护的指针关系翻倍。

双链表插入节点时，假设要在节点 p 的后面插入新节点 s，经典操作口诀是四步：

s->prior = p; s->next = p->next; p->next->prior = s; p->next = s;

代码看着就四行，但三个 p 打底的操作里混着一个 p->next，容易写串。我习惯先处理新节点和后面节点的关系，再处理新节点和前面节点的关系。这样即使后面两步写错，也不至于把链表拆成两段。删除节点 p 时是两步：

p->prior->next = p->next; p->next->prior = p->prior;

如果 p 是最后一个节点，p->next可能是 NULL，那么p->next->prior就是对空指针解引用，直接段错误。正确的写法是先判断if (p->next != NULL)再处理。这种边界条件很容易在测试数据“恰好不涉及尾部节点”的时候蒙混过关，一上真数据就炸，属实经典。

3.5 C++ 和 Python 的链表：换语言，不换灵魂

C++ 写链表，基本代码和 C 语言一致，但可以用struct Node { Book data; Node *next; Node(const Book& b, Node* n = nullptr) : data(b), next(n) {} };这种带构造函数的写法，创建节点时一步到位。内存管理上不再用 malloc/free，改用 new/delete，逻辑不变。

Python 写链表也很直白，用类表示节点：

class Node: def __init__(self, data=0, next_node=None): self.data = data self.next = next_node def reverse_linked_list(head): prev = None cur = head while cur is not None: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev

Python 里head是可变对象的引用，函数内部改了链表关系，调用方看到的就是改完的结果，没有 C 里那种二级指针问题。不过 Python 的默认引用共享也带来一个坑：如果你不小心把两个变量指向同一个节点，它们其实是同一个对象，改一个就是改两个，这个和 C 里指针的内存关系是同一个道理。

4. 顺序表还是链表，到底怎么选？性能对比与场景选型

很多人在学了两种结构之后反而更纠结：数组有随机访问效率，链表有插入删除灵活性，那到底怎么选？我的答案是：先看操作模式，再看内存约束，最后看实现复杂度。

4.1 时间复杂度对比：光背结论不是懂

核心对比如下表格，建议保存：

注意最后一行：如果元素本身很小（比如只存一个 int），链表额外花的那个 next 指针空间占比非常大，几乎相当于翻倍的内存占用。如果元素本身很大（比如 Book 结构体有 100 字节），那份 next 指针开销就无足轻重了。很多嵌入式场景不许用链表，内存空间吃紧是一个真实原因。

4.2 真实场景选型：业务操作模式决定一切

业务里如果操作以“按索引访问”为主，选顺序表基本没错。比如排行榜数据，你经常要取第 3 名、第 10 名；再比如 Excel 的一列数据，用户要跳到第 5000 行——这些都是 RandomAccess 的典型场景。Java 的 LinkedList 在 get(5000) 上耗时几乎是 ArrayList 的百倍，这一点性能差异在真实业务里直接能感知到。

如果业务以“从两端的固定位置插入删除”为主，比如消息队列、浏览器的前进后退记录，用链表或者双端队列更合适。注意这里说的是“从两端”，因为你总是知道头尾节点的指针，插入删除是 O(1)；如果业务是“随机从任意位置插入”，链表并不占优势，因为查找位置本身已经 O(n) 了。

“ArrayList 和 LinkedList 怎么选”这个问题，答案要从三个维度看：读多改少选顺序表，头尾增删频繁选链表，内存吃紧优先顺序表。如果还拿不定，我的经验准则是——默认用顺序表。现代 CPU 对连续内存的缓存友好度极高，顺序表遍历时后续元素会被预取到高速缓存，链表节点散落各处则每次都触发缓存未命中。短链表看不出差别，十万级元素的时候，顺序表遍历比链表快出几个量级都很正常。

4.3 中间插入的代价对比：用“搬移数量”而不是“感觉”

有读者可能会问，都知道顺序表插入是 O(n)，但这个 O(n) 到底意味着多少工作量？我算给你看：一个长度 N 的顺序表，在位置 i 插入，平均需要搬移 N/2 个元素。假设每个元素是 8 字节，N 等于一百万，一次插入就要搬移约 4 MB 数据。如果同时有十万次插入，总搬移量就是 400 GB，这已经不是“慢一点”而是“工程事故”了。

链表在这种极端插入场景下能扛住吗？能，前提是插入位置必须明确。比如逐条解析文件并动态构建有序链表时，如果数据本身接近有序，每次插入可以快速定位到相近位置，总代价可控。如果数据完全随机，每次插入都要从头遍历，最终复杂度仍然很高。所以“用链表优化插入”不是一个白名单，需要配合对访问模式的精准掌握。

5. 链表高频操作拆解：指定位置插入、逆置、清空销毁

热词里有一串“链表插入”“单链表的基本操作”“链表的清空”“逆置链表”，这些都是笔试和课设常客。下面把高频操作按步骤拆到位。

5.1 单链表逆置：迭代法三指针，还是头插法重建

逆置链表是一个让人又爱又恨的操作，思路说难不难，写起来却很容易绕。先讲最稳的迭代三指针法。

Node *reverseList(Node *head) { Node *prev = NULL; Node *cur = head; Node *nxt = NULL; while (cur != NULL) { nxt = cur->next; // 先保存后继，否则一会就丢了 cur->next = prev; // 反转指针 prev = cur; // 前驱前移 cur = nxt; // 当前节点前移 } return prev; // prev 最后指向原链表的尾节点，即新链表头 }

三句话解释：nxt 保存后继，防止“反转之后迷路”；cur->next 指向前驱，把方向掉头；然后三指针整体后移一步，周而复始。我在现场面试时看到不少同学写到这里会卡住，就是因为没有意识到 nxt 的保存是必须的——一旦执行了cur->next = prev，原链表的后续部分就断了，没有 nxt 就再也找不回来了。

另一种思路是头插法重建：从原链表的第一个节点开始，逐个摘下来，头插到新链表里。每摘一个节点，新链表就多一个节点头部，遍历完全部节点，原链表就逆置完成。实现上跟前插操作很像，利用了一个特性：头插的顺序和读取顺序相反。

Python 版本的逆置我在上面贴过，本质完全一样。无论用什么语言，逆置的核心只有一件事——把每个节点都当作独立的箱子，箱子不动，动的是里面的线索标签。

5.2 单链表的清空和销毁：千万别只把自己的指针置空

“单链表的清空”是一个极容易做错的操作。很多新手写成head->next = NULL就完了，这在内存上什么都没做——原来那串节点还躺在堆里，变成无法访问的内存泄漏。正确的清空是释放掉链表的所有数据节点，只保留头结点（或者连头结点也不要）。

void clearList(Node *head) { if (head == NULL) { return; } Node *cur = head->next; while (cur != NULL) { Node *temp = cur->next; // 先保存后继 free(cur); // 释放当前节点 cur = temp; } head->next = NULL; }

为什么要先把 temp 保存好再 free？因为 free 之后，原节点的 next 指针已经是未定义值（或者旧的地址），再去访问它就是访问野指针，程序随时可能崩。这个模式叫“先保存后继再销毁当前”，是链表内存管理的通用心法。

销毁整条链表比清空更进一步，需要把头结点也 free 掉：

void destroyList(Node **head) { Node *cur = *head; while (cur != NULL) { Node *temp = cur; cur = cur->next; free(temp); } *head = NULL; }

如果不把*head = NULL，调用者手里的头指针会成为一个悬空指针，以后再访问就是 undefined behavior。这几乎是网上代码里出错率最高的一行。

5.3 链表的遍历：迭代器思想与访问模式的差别

链表遍历本身不复杂，但不同链表形态的遍历写法值得统一梳理一下：

• 单链表：while (cur != NULL)，顺着 next 一路走；
• 循环单链表：while (cur->next != head)或 do-while，防止死循环；
• 双链表：既可以向前也可以向后，常见的场景是从尾部向前遍历撤销操作，比如编辑器的撤销栈；
• 双向循环链表：任何位置都能向两个方向绕一整圈，实现 LRU 缓存时很有用。

实际工程里，链表遍历经常会和“修改节点值”“统计节点数”“按条件删除”等操作结合。说一个容易踩的坑：遍历过程中如果要删除当前节点，常规的cur = cur->next在删除后仍然能工作吗？要看实现。单链表删除当前节点需要前驱指针，如果直接 free 当前节点，下一步你就无法访问 cur 的位置了。正确做法是先保存 next，删除当前，再让 cur 指向 next。这和清空链表时“先保存后继再销毁”是同一个心法在不同场景的复现。

6. 避坑指南：几个让我 debug 到怀疑人生的经典问题

教书的人讲语法，实战的人讲坑。我把亲自踩过、也在网上看到高频出现的几个链表/顺序表问题汇总成一个速查表，每一个背后都有一个深夜 debug 的故事。

还有一个很多人容易忽略的问题：链表节点本身是通过malloc或new在堆上分配的，释放逻辑必须用free或delete，不要混用。C 语言里 malloc 的内存用 free 释放，C++ 的 new 用 delete 释放，用错属于未定义行为。我见过一次诡异崩溃，最后定位就是混用了 malloc 和 delete。

另一个经验是关于“带头结点”的。很多教材为了展示“不带头结点的难度”，会故意设计一些不带头结点的题目，比如“不带头结点的单链表翻转”。实际工程中，带头结点几乎总是更省心。它像是一个哨兵，永远站在链表的第一个位置，让空表和非空表的逻辑完全统一。如果你自己能设计接口，我强烈建议默认带头结点，把注意力留给真正的逻辑问题，而不是跟边界条件搏斗。

关于双链表还有一个细节想多说一句：写双链表调试时，打印一部分节点后如果出现地址回跳，别急着怀疑算法，先检查p->prior和p->next是否被互相污染了。双链表的指针关系脆弱，一旦某个节点的新增/删除少改了一条链，就可能出现“回环”或“断裂”，打印结果会非常诡异。我的调试习惯是写一个printListForward和一个printListBackward，在每次操作后各打一遍，如果两个方向打印到的节点数量不一致，问题几乎立刻暴露。

顺序表这边的坑更多集中在扩容策略和数据搬移上。图书信息顺序表里如果用固定数组实现，一旦开始批量录入就把数组写满，容易越界。我建议把上一节里的ensureCapacity函数当成标配，不管题目有没有要求都要写上。哪怕是简单课设，这一行代码能帮你少掉一半因“容量不够”引发的重启程序经历。

再分享一个小技巧：无论顺序表还是链表，新增或删除后，写一个调试辅助函数把整个结构打印出来。顺序表直接循环数组下标；单链表从头开始遍历；循环链表设一个计数上限，防止死循环。打完发现数据应该是什么样、实际是什么样，往往一眼就能定位问题在哪。很多同学 debug 半天不动手打印，全靠脑子想象节点在内存里的样子，效率极低。

说了这么多，其实最核心的体会就一句话：顺序表和链表不背不会出真知，只有亲手写了、跑挂了、修好了，才能把这些细节刻进直觉里。你可以在小项目里先各写一遍，用同一个“图书信息管理”需求分别用顺序表和链表实现，对比总耗时、内存占用和代码量。跑完一遍之后，之前那些“怎么选”“为什么要这样写”的疑问自然就都有了答案。