很多初学数据结构的朋友，第一次被卡住的地方往往就是线性表。原因也很直接：教材一上来就给出抽象定义、ADT、存储结构、算法实现，概念一层套一层，课本翻了好几页，连“为什么要区分顺序表和链表”都没想明白。等真到了实验课，要求用C语言把线性表跑起来，又发现原来的代码漏洞百出，不是内存越界就是链表断掉。这篇就把这块硬骨头拆开，顺着“存储结构怎么选、C语言函数怎么写、踩过的坑怎么排”这条线，捋一遍线性表从逻辑结构到代码落地的完整过程。不管你是期末复习、考研408，还是补数据结构实验报告，照着这篇的思路去理解，会比死记硬背函数实现有效得多。

1. 线性表的逻辑结构与两种存储方案怎么选

1.1 线性表的定义和逻辑特点

线性表是n个数据元素构成的有限序列，最直白的理解就是一列排队的数据。里面的元素之间有“一对一”的相邻关系，除了第一个元素没有前驱、最后一个没有后继，其余每个元素都有而且仅有一个直接前驱和一个直接后继。比如一个数组A[10]= {2, 3, 5, 7, 11}，最后一个元素的索引比前一个元素刚好大1，这就是线性表在逻辑上“连续、有头有尾”的体现。

这个逻辑结构是所有操作的基础。不管是顺序表还是链表，都要实现同一套逻辑操作：初始化、插入、删除、查找、取元素、判空、销毁。为什么逻辑结构要和存储结构分开讨论？因为同一个逻辑结构可以用不同的物理存储方式来表达，就像同样一个通讯录，你可以写在纸上按顺序排好，也可以用卡片串联起来，谁放在谁前面，记录的是逻辑关系，而不是物理位置。

初学阶段容易有一个误区：把“数组”直接跟“顺序表”画等号。严格说，顺序表是用数组实现的线性表，数组是它的载体；而链式存储则是用指针把零散的内存块串起来。两者解决的是同一份数据“怎么存放、怎么访问”的问题，只是策略完全不同。

1.2 顺序存储和链式存储的核心差异

顺序存储的做法，是给线性表分配一块连续的存储单元，逻辑上相邻的元素，物理地址也相邻。C语言里最典型的实现就是数组。它的优势一眼能看出来：访问第i个元素可以靠首地址加上偏移量直接算出地址，时间复杂度O(1)，也就是随机存取；缺点是插入和删除往往要成片移动后续元素，时间复杂度O(n)，且存储空间需要预先分配，多了浪费、少了不够用。

链式存储的做法，是让每个节点除了保存数据，还保存下一个节点的地址。逻辑上相邻的元素，物理上可能隔得很远，但你顺着next指针总能找到下一个。它的优势是插入和删除只需要修改指针，不用搬运数据，只要已知插入或删除位置的前驱节点，操作就是O(1)；缺点是查找第i个节点必须从头开始挨个走，O(n)，而且每个节点还要额外多存一个指针，存在“指针域开销”。

这里我放一张表，方便直接对照记忆：

这张表在考研和期末考试里基本是必背的，但其实理解起来并不难。你把顺序表想象成一排影院座位，观众按票号坐在一起，找人只要知道号码直接走过去就行；如果有人临时补进来，那后面的人都要挪一下。链表则像是寻宝游戏，每个线索指向下一个藏宝点，你只能顺着线索一个个找下去，但中途想加一条线索、删一条线索，只需要把前后线索重新绑定就行，不需要移动其他人。

1.3 实际项目里怎么选

实验报告里通常会直接指定存储结构，但真实业务里，怎么选更多要问自己两个问题：第一，最频繁的操作是读还是写？第二，数据规模是基本固定还是经常变？

如果一个集合主要用于查找、遍历，比如城市列表、常量配置表，顺序表的随机访问优势非常明显，代码也简单，数据量大时缓存命中率还高，用顺序表。如果主要做高频插入、删除，比如一个待办队列、内存中的消息缓冲，链表的指针修改优势就体现出来了，用链表更合适。

另外还要考虑空间管理。顺序表如果动态扩容，通常按照“倍增”策略，比如容量从4翻到8、16，均摊下来插入成本依然可以看作O(1)，但一次性扩容时要申请新空间、拷数据、释放旧空间，这个开销不能忽略。链表不存在这种“搬家成本”，每个节点用的时候临时malloc，缺点是频繁malloc/free会产生内存碎片，节点分散又牺牲了局部性，在高性能场景下往往还不如顺序表。

我自己做算法题时，默认优先用顺序表，除非题目明确考链表操作。因为顺序表实现起来简单、不容易出指针错误，调试成本低。但在写真正的内核队列、LRU缓存这类组件时，链表又几乎是不可替代的，因为你要在中间频繁摘除节点。

2. 顺序表的C语言函数实现：从结构体到扩容一篇讲透

2.1 结构体定义与初始化

顺序表用C语言实现，第一件事就是定义结构体。很多初学者只用数组和一个长度变量，比如int arr[100]; int len;，这样不是不行，但没法封装成表类型，多个函数传参时很容易散乱。更规范的做法是定义结构体，把数据区、当前长度、容量都绑在一起。

#include <stdio.h> #include <stdlib.h> #define INIT_CAPACITY 4 typedef struct { int *data; int length; int capacity; } SeqList;

data指针指向动态分配的数组首地址，length记录当前元素个数，capacity记录当前容量。为什么需要一个capacity？因为动态顺序表满的时候需要扩容，知道容量才能判断“是否满了”。如果不考虑扩容，静态数组 + length也能实现，但长度受限，实验课评分通常不喜欢这种“阉割版”写法。

初始化函数建议这样写：

void SeqList_Init(SeqList *list) { list->data = (int *)malloc(INIT_CAPACITY * sizeof(int)); if (list->data == NULL) { printf("内存分配失败\n"); exit(1); } list->length = 0; list->capacity = INIT_CAPACITY; }

很多教材会省略malloc失败检查，实际项目里不能省。malloc返回NULL是可能发生的，尤其是申请大块内存或系统内存紧张时。严格规范的习惯，是在每次malloc后都判断一下，虽然啰嗦，但能在开发期尽早暴露问题。

2.2 插入、删除、查找的完整实现

顺序表插入的核心是“从后往前移动元素”，这一点特别容易写反。如果你从前往后移，后面的元素还没移动就被前面的覆盖了，数据就串了。所以必须倒着来。

int SeqList_Insert(SeqList *list, int pos, int value) { // pos 从 0 开始，合法范围是 [0, length] if (pos < 0 || pos > list->length) { printf("插入位置非法\n"); return 0; } if (list->length >= list->capacity) { SeqList_Resize(list); // 扩容 } for (int i = list->length; i > pos; i--) { list->data[i] = list->data[i - 1]; } list->data[pos] = value; list->length++; return 1; }

为什么能被插入的位置是[0, length]？因为表满时可以在末尾追加，length位置相当于表尾。如果定义一个“不符合逻辑”的位置，比如length+1，那么移动时就会越界。一旦越界，C语言不会报错，但会静默破坏相邻内存，这种bug在实验报告里最难查。

删除是插入的逆向操作，从前往后移动覆盖：

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

要注意删除时不需要把最后一个位置“清零”，只要length减一，逻辑上那个元素就不存在了。下一次插入元素到这个位置，会被新值直接覆盖。很多新手在删除后多写一句list->data[list->length] = 0;，看似严谨，其实多此一举。

按值查找的常规写法是遍历，返回第一个匹配的索引：

int SeqList_Find(SeqList *list, int value) { for (int i = 0; i < list->length; i++) { if (list->data[i] == value) { return i; } } return -1; }

这个函数没什么难度，但注意返回-1表示找不到时，调用方要和合法索引0区分开。有的同学用返回0表示失败，如果表里有0号元素，就会出现歧义。

2.3 动态扩容策略与复杂度

扩容函数是动态顺序表能不能体现“动态”的关键。常规做法是申请一块更大的空间，把旧数据搬过去，释放旧空间，再更新data和capacity。

void SeqList_Resize(SeqList *list) { int newCapacity = list->capacity * 2; int *newData = (int *)malloc(newCapacity * sizeof(int)); if (newData == NULL) { printf("扩容失败\n"); exit(1); } for (int i = 0; i < list->length; i++) { newData[i] = list->data[i]; } free(list->data); list->data = newData; list->capacity = newCapacity; }

这里用倍增策略而不是“每次只扩大一点”，是为了摊还复杂度。假设初始容量是4，每次插入到满就扩容，代价依次是4、8、16……总共拷贝的次数是4+8+16+...，如果达到n后总拷贝次数大约是2n-4，均摊到每次n插入，O(1)。如果每次只多扩1个单位，那么每次扩容都要拷全部数据，复杂度会变成O(n²)，真实业务里一定扛不住。

扩容后同样要记得free旧空间，否则会内存泄漏。在实验报告里，如果运行多次初始化、多次插入，内存不断上涨，很可能就是这里漏了free。另外，扩容的“倍数”不一定是2，1.5倍、黄金分割倍也都常见，目的是让频繁扩容时不至于空间浪费太严重。对于考试，记“均摊O(1)”就够用。

3. 单链表的C语言函数实现：节点、指针和头结点

3.1 节点设计与头结点的价值

链表的基本单位是节点，每个节点存数据和下一个节点的地址。定义很直接：

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

注意这里的next类型是struct Node *，不能用typedef后的别名定义自己，这是一个容易让人绕晕的细节。写成上面这样，函数里可以用Node创建指针，编译器能理解Node就是struct Node的别名。

很多教材和实验模板会引入头结点，也就是在第一个数据节点之前额外加一个空节点。头结点不是必需的，但加上它能带来两个明显好处：第一，在表头插入和删除时，不需要单独处理“首节点”的特殊情况，统一通过头结点操作；第二，空表和非空表的判断标准统一了，空表就是head->next == NULL，而不会出现head == NULL这种需要额外判断的情况。

Node *head = (Node *)malloc(sizeof(Node)); head->next = NULL;

这里的head就是头结点，它的data字段通常闲置不用。如果面试官问“头结点和头指针有什么区别”，头指针是链表入口的地址，必须存在，但可以指向第一个节点，也可以指向头结点；头结点是可有可无的辅助节点。C语言版课程设计里，习惯上用带头结点的写法，代码更统一。

3.2 头插法与尾插法

建链表常用的方式有两种：头插法和尾插法。头插法是把新节点插到最前面，也就是挂在头结点后面；尾插法是用一个尾指针，每次把新节点接到链尾。

头插法代码：

Node *CreateListByHead(int arr[], int n) { Node *head = (Node *)malloc(sizeof(Node)); head->next = NULL; for (int i = 0; i < n; i++) { Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = arr[i]; newNode->next = head->next; head->next = newNode; } return head; }

头插法建出的链表，数据和原数组顺序是反的。因为每次新节点都站在最前面，后插入的反而排在前面。尾插法则保持顺序：

Node *CreateListByTail(int arr[], int n) { Node *head = (Node *)malloc(sizeof(Node)); Node *tail = head; tail->next = NULL; for (int i = 0; i < n; i++) { Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = arr[i]; newNode->next = NULL; tail->next = newNode; tail = newNode; } return head; }

尾插法里tail始终指向最后一个节点。每次先把新节点挂在tail->next，然后让tail后移。尾插法比头插法逻辑上更好理解，也容易配合“遍历时不打乱原顺序”的需求，所以实验报告除非题目要求头插，通常我建议用尾插。

这里有一个常考的小陷阱：头插法的十字连接顺序是“先让新节点指向旧头结点的下一个，再让头结点指向新节点”。如果把顺序写成head->next = newNode; newNode->next = head->next;，那第二步中head->next已经被改掉了，新节点指向了自己，链表直接断掉。这个顺序错误几乎是链表新手必踩的坑。

3.3 删除、反转、销毁等实战函数

删除指定值的节点，关键是要保存前驱节点。用current指针遍历，用prev指针记录当前节点的前一个。找到待删除节点后，让prev->next指向current->next，然后free(current)。没有前驱指针的删除，在单链表里只能靠“把下一个节点的值拷贝到当前节点，再删除下一个节点”这种偷梁换柱技巧，虽然可行但不是常规操作。

void List_DeleteValue(Node *head, int value) { Node *prev = head; Node *cur = head->next; while (cur != NULL) { if (cur->data == value) { prev->next = cur->next; free(cur); cur = prev->next; } else { prev = cur; cur = cur->next; } } }

注意上面这个实现可以连续删除所有值等于value的节点，因为删除后cur被更新为prev->next，避免了指针悬空。很多初学者会在free之后继续用cur->next，这就是典型的use-after-free，运行到后面结果不可预测。

链表反转是另一个必考函数。迭代反转的思路是三个指针：pre、cur、next。初始pre为NULL，cur为head->next（第一个数据节点），每次把cur->next指向pre，然后三个指针同步后移，最后让head->next指向原来的尾节点。

void List_Reverse(Node *head) { Node *pre = NULL; Node *cur = head->next; while (cur != NULL) { Node *next = cur->next; cur->next = pre; pre = cur; cur = next; } head->next = pre; }

这里的关键是提前保存next，否则cur->next被改掉后，就找不到原来的下一个节点了。反转后head->next要指向pre，也就是原链表的最后一个节点。如果你在C语言实验课上写反转，这个函数建议背得滚瓜烂熟，因为它能同时考察你对指针修改、循环条件的理解。

销毁链表时，不能直接free(head)，否则头结点之后的所有节点全部泄漏。要一点一点摘节点：

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

这个循环里同样必须在free之前保存next。处理完后再把head置为NULL，防止悬空。很多同学在销毁后还会尝试去访问链表，这是非常危险的，因为那块内存可能已经被系统回收。

4. 双链表和循环链表：额外一道关卡

4.1 双链表结构与插入删除差异

如果业务里需要频繁找前驱，单链表就不够用了，因为你只能从头再遍历。双链表每个节点增加一个prior指针，指向直接前驱，这样前后都能走。结构体定义：

typedef struct DNode { int data; struct DNode *prior; struct DNode *next; } DNode;

双链表的插入和删除虽然要同时维护两个方向的指针，但逻辑上反而比单链表更对称。比如在节点p之后插入新节点s，需要四步：

s->next = p->next; s->prior = p; if (p->next != NULL) { p->next->prior = s; } p->next = s;

为什么在p->next修改前要判断p->next是否为空？因为如果p本身是尾节点，p->next就是NULL，访问p->next->prior会解引用空指针。这个边界条件在单链表里基本不会考虑，双链表必须考虑。

删除节点p的操作则是：

p->prior->next = p->next; if (p->next != NULL) { p->next->prior = p->prior; } free(p);

不判断p->next时，删尾节点也会出问题。双链表写起来比单链表繁琐，但好在每个操作都能“前后呼应”，调试时只要画图，把prior和next的连接关系理清楚，基本不会错。

4.2 循环链表的边界处理

循环链表有两种：单向循环和双向循环。单向循环就是把单链表的尾节点next重新指向头结点，形成一个环。好处是从任意一个节点出发，都能遍历整张表；坏处是循环条件从cur != NULL变成了cur != head，一旦条件写错，很容易陷入死循环。

双向循环链表则让头结点的prior指向尾节点，尾节点的next指向头结点。这种情况下，判空条件很简单：head->next == head，同时head->prior == head，空表自己形成一个环。往表头插、往表尾插，代码可以高度统一，因为头结点即扮演头又扮演尾。

英国著名的约瑟夫环问题，用循环链表实现时，正好考察这种环形遍历。每次报数到m就删除当前节点，继续从下一个开始。这个题的删节点函数，和普通链表删除完全一样，只是指针在环里打转时，切记不要写while (p != NULL)，那样会永远不停止。

4.3 实际应用场景与“用得上吗”

很多学生学到这里会问，双链表、循环链表除了考试还有什么用？实际上应用很广。操作系统里的进程队列，很多用双向链表组织，因为调度器需要频繁向前、向后调整优先级；浏览器的前进后退页面列表，就是双链表；链表环的判断、约瑟夫环，又是面试必考题。循环链表适合解决“固定窗口循环覆盖”的场景，比如计时器环形队列。

学这部分的重点是不要死记函数，而是画图。把每个节点当成一个盒子，prior和next当成箭头，箭头有方向。插入删除时，你只需要弄清楚“让哪根箭头指向谁”，代码就是箭头的翻译。C语言的指针本质上就是箭头，理解了这一步，双链表就不再神秘。

5. 常见问题与排查技巧实录

5.1 传参错误，链表为什么没建起来

很多C语言新手写链表时，函数是这样开始的：

void CreateList(Node *head) { head = (Node *)malloc(sizeof(Node)); head->next = NULL; }

然后在main里调用CreateList(head)，完了输出head->next，程序直接段错误。原因很简单：C语言函数传参是值传递，函数内部的head是一个副本，你在函数里让这个副本指向新内存，并不会改动外部的head。外部head仍然是NULL。

正确的做法有两种：一是返回新指针，二是传入二级指针。返回指针更常用：

Node *CreateList() { Node *head = (Node *)malloc(sizeof(Node)); head->next = NULL; return head; }

如果函数需要修改外部指针本身，比如初始化时给head赋值，就要传Node **head，函数里用*head = (Node *)malloc(...)。这个点也是很多实验课面试题的考点。记住一句话：只要你想在函数内部改变外部传来的指针，就必须传二级指针或者返回新指针，否则改动无效。

5.2 内存泄漏与野指针

内存泄漏在C语言里不会直接影响运行结果，但会影响程序稳定性。常见原因是malloc了节点但删除后没free，或者销毁链表时漏掉某个分支。排查方法很简单，用工具。Linux下用valgrind跑一遍，它会清楚告诉你“definitely lost: X bytes”。Windows下可以用Application Verifier或者写测试时观察内存占用。

野指针的常见来源是释放后继续使用。free(p)之后，p指向的内存已经归还系统，里面的内容可能被改写。再访问p->data，读到的是垃圾数据，极端情况下程序崩溃。正确习惯是free的同时，立刻把对应指针置为NULL，避免后续误用。

malloc、free、free之后再置NULL，这三个动作最好写在一起。虽然多写一行看起来啰嗦，但调试时能省你好几个小时。

5.3 位置参数和循环边界到底怎么定

顺序表的插入位置、链表遍历的终止条件，都是容易出边界bug的地方。顺序表插入位置的范围是[0, length]，删除位置是[0, length-1]，写错一个等号，轻则越界，重则读脏数据。

链表的遍历条件要看是否有头结点。有头结点遍历数据节点时，用cur = head->next，循环条件cur != NULL。如果是带头结点的单向循环链表，循环条件要改成cur != head。如果不带头结点，删除链表第一个节点时要单独处理。每一种结构的循环边界都不一样，建议在代码旁边画一个最小用例，比如3个节点，把每一步指针变化写在草稿上，跑一遍就清楚了。

另外，位置语义一定要统一。有的教科书从1开始计位置，有的从0开始。写实验报告时，建议默认从0开始，并在注释里写明。这不仅是给老师看，也是防止自己写插入函数时搞混。

5.4 调试链表崩溃的快速定位法

链表出了问题，先不要急着加printf，先回答三个问题：崩溃发生在访问哪个节点？这个节点的地址是什么？是否存在空指针被解引用？如果看得晕，有一个土办法：写一个遍历函数，完整打印链表中每个节点的地址和值。打印到第几个节点崩溃，就能缩小范围到那个节点上。

如果链表“看起来没问题”但函数没有效果，比如反转后还是原顺序，多半是修改指针后又读旧指针，或者循环条件多走少走。这种情况下，把反向过程每一步的pre、cur、next都打印出来，对照正确顺序检查。

我自己调试链表时，习惯在每次修改指针后停顿几秒，手动在草稿纸上画一次箭头指向。代码可以骗人，图纸不会。尤其是最后一次做实验报告时，前面的函数都积压在一起，一个节点泄漏可能拖垮整个程序，提前打印好节点地址，真的能救命。

最后再分享一个我在实际写顺序表和链表时的习惯：不管用哪种结构，先把“初始化、销毁、遍历打印”三个函数写好，跑通一遍，再做业务逻辑。这三个函数是最基础的脚手架，有了它们，后续调插入、删除时能立刻看到数据变化。如果没有遍历打印函数，你会在黑乎乎的终端里猜链表状态，那才是最难熬的。学数据结构，最好的方式不是背代码，而是把每个函数当成一块积木，先搭好底座，再一层一层往上垒。这样到期末实验课或者考研前复习，你会发现线性表这部分就是最扎实的一块地基。