C语言数据结构入门：从零手写链表、栈与队列

单纯背语法是最亏的学习方式。C语言的语法本来就不复杂，真正拉开差距的，是你能不能把“数据怎么组织、怎么访问、怎么增删”这件事想明白，而链表、栈、队列这三块，恰好就是数据结构里最基础也最能“看见”内存行为的内容。这篇内容是我自己从零手写这三类结构时攒下的完整思路，包括源码细节、设计取舍、调试点和常见坑，适合刚学完指针、准备往数据结构与算法方向迈一步的C语言初学者，也适合想回头把基础补扎实的开发者。

1. 为什么用C语言学数据结构与算法

1.1 数据结构到底解决什么问题

很多初学者有个误区，觉得“数据结构”是一堆抽象名词，链表、树、图好像离实际开发很远。其实数据结构解决的是个非常朴素的问题：数据在内存里怎么摆，才能让增删改查又快又省。

我习惯用一个生活类比来解释。你去图书馆借书，如果全馆的书按编号整整齐齐摆在一排排书架上，那查找很快，但你要是往中间插入一本新书，后面所有书都得往右挪一位，这就是顺序存储的代价。反过来，如果每本书上只写着一句话“我后面那本书在第三排第二个位置”，你顺着线索一本本找过去，插入就很简单，改个线索就行，代价是查找慢、得从头走。前者像数组，后者像链表。

栈和队列也一样，它们不是新的存储方式，而是“使用规则”。规则一旦定下来，很多复杂问题会简化。比如程序里的函数调用，天然就是一个“后调用的先返回”的过程，也就是栈；而操作系统里的任务调度、打印任务排队，天然就是“先来的先处理”，也就是队列。你把这些抽象结构落到C语言里，能亲眼看到每个节点的地址、每个指针的指向，再学什么二叉树、哈希表都会顺很多。

1.2 C语言为什么适合干这件事

选C语言学数据结构，不是因为它最简单，恰恰是因为它“不帮你兜底”。

数组越界、指针乱指、内存没释放，在Java、Python里往往会被运行时拦住或者被垃圾回收抹平，你根本感知不到底层发生了什么。但在C语言里，每个节点都是你手动malloc出来的，每段内存都是你手动释放的，指针指向错了就是段错误，内存没释放就是泄漏。正是这种“不友好”，逼着你去理解结构本身的原理。

而且C语言里对“值传递”的体现非常纯粹，函数传参到底传的是副本还是地址，直接影响你能不能修改链表。这个问题在学数据结构时一定会反复碰到，搞懂了，后面看C++的引用、看Java的对象传参都不会再含糊。可以说，把链表、栈、队列用C语言亲手写一遍，你收获的不止是几个算法模板，而是对程序运行机制的底层感觉。

2. 链表：从指针到动态存储

2.1 链表节点的设计与内存逻辑

链表的核心单位叫节点（Node）。一个节点至少包含两部分：数据域，用来存具体内容；指针域，用来存下一个节点的地址。

typedef struct Node { int data; // 数据域 struct Node *next; // 指针域，指向下一个节点 } Node;

注意这里有个很多人第一次看会懵的点：struct Node内部包含了指向自己类型的指针。这在逻辑上是成立的，因为指针占用的内存大小是固定的（64位系统里是8字节），它存的是“另一个节点的地址”，而不是“另一个节点本身”，所以不存在无穷嵌套的问题。

从内存布局来看，链表的各个节点是东一个西一个的，不要求连续。每个节点在用之前都要通过malloc在堆上申请内存，malloc返回的是void*，我们要把它强制转换成Node*，然后才能填数据。

我一直觉得，链表是对“地址”这个概念最好的练习场。你定义Node *head，它本身只是一个指针变量，当它指向第一个节点时，head->data才能读到数据。如果你把head理解成“一串钥匙的第一把”，那head->next就是下一把钥匙，顺着摸过去，就能走完一整串节点。

2.2 单链表核心操作：创建、插入、删除、遍历

单链表是链表的入门形态，所有操作都是围绕指针的重新指向来完成的。

先看创建节点：

Node *createNode(int val) { Node *newNode = (Node *)malloc(sizeof(Node)); if (newNode == NULL) { printf("内存分配失败\n"); exit(1); } newNode->data = val; newNode->next = NULL; return newNode; }

malloc完之后立刻检查是否为空，这个习惯我从第一次写链表就开始养成了。虽然平时内存分配失败的概率不高，但一旦发生，程序后面往NULL地址写数据就是灾难性的段错误。

头插法是最能体现“改指针”的操作：

void insertAtHead(Node **head, int val) { Node *newNode = createNode(val); newNode->next = *head; // 新节点的next指向当前头节点 *head = newNode; // 让head指向新节点 }

这里函数参数用了Node **head，也就是头指针的指针。为什么不能直接用Node *head？因为C语言函数的参数是值传递，你传进去的head只是一个副本，在函数里改成新节点地址，外面根本感知不到。只有传“指针的指针”，才能通过解引用*head = newNode实打实修改外层的头指针变量。这个点我见过无数人踩坑，后面第6部分会专门再讲。

删除操作要更小心。删除某个节点时，必须先把它的前驱节点找到，让前驱的next跨过待删节点，指向待删节点的后一个，然后才能 free。顺序不能反，否则前驱节点就断链了。

void deleteNode(Node **head, int val) { Node *prev = NULL; Node *cur = *head; while (cur != NULL && cur->data != val) { prev = cur; cur = cur->next; } if (cur == NULL) { printf("没有找到该节点\n"); return; } if (prev == NULL) { *head = cur->next; // 删除的是头节点 } else { prev->next = cur->next; } free(cur); }

遍历操作就简单了，从头开始，每到一个节点就输出，然后p = p->next继续走，直到p == NULL结束。需要注意，千万不要在循环里把 p 往前退，链表没有回头路，这也是它跟双向链表最大的差别。

2.3 双向链表与循环链表：变体的应用场景

单链表的缺点是只能单向走。你想删除某个节点，必须从头找到它的前驱，时间复杂度是O(n)。双向链表（Doubly Linked List）每个节点多一个prev指针，直接指向前驱，删除节点时自己就能找到前后，O(1)搞定。

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

代价是每个节点多占一个指针的空间，而且插入和删除时要同时维护两个方向的指针关系，代码复杂度比单链表明显上去一截。实际工程里GNU C库的某些容器、浏览器的前进后退历史、文本编辑器的撤销列表都用到了双向链表。

循环链表是另一个变体，它把尾节点的next指向头节点，形成环。最经典的例子是约瑟夫环问题：一群人围成一圈报数，数到某个数的人出列，然后从下一个人继续报数，直到全部出列。用循环链表做这个题非常自然，因为转圈就是链表的遍历方向。操作系统里的时间片轮转调度，本质上也是把所有进程放进一个循环队列或循环链表，一个接一个轮流获得CPU。

从学习路径来说，我建议先把单链表写到纯熟再碰变体。单链表是所有链表操作的骨架，后面的双向、循环只是在这个骨架上加了反向指针、改了边界条件而已。

3. 栈：后进先出的那些“叠盘子”逻辑

3.1 栈的结构特征与生活映射

栈是一种操作受限的线性表，限制了只能在一端插入和删除，这端叫栈顶，另一端叫栈底。这种限制带来一个非常明确的行为特征：后进先出，Last In First Out，简称LIFO。

你想象餐厅里叠盘子，后放的盘子一定在最上面，要取的时候一定先取最上面的。栈的操作只有两个基本动作：push（入栈，相当于往上放盘子），pop（出栈，相当于从顶上取盘子）。还有一个peek操作，只看栈顶元素不弹出。

栈在生活中太常见了。浏览器的后退按钮就是栈：你访问页面A、B、C，后退时先回到B再回到A，正好是逆序。文本编辑器的撤销操作也是栈，每次撤销撤销的是最近一次修改。而表达式求值，比如“2 + 3 * 4”，编译器里处理运算符优先级时也是用栈来存储中间结果的。

为什么限制操作反而有用？因为现实问题里大量逻辑就是“最近发生的先处理”，栈把它抽象出来之后，你就不需要每次自己设计一堆变量记录历史顺序，直接用栈就行。

3.2 顺序栈的实现与细节

栈的底层存储可以用数组，这叫顺序栈。入门阶段推荐先用数组，因为逻辑清晰，实现快速。

#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; // 栈顶下标，-1表示空栈 } Stack; void initStack(Stack *s) { s->top = -1; } int isFull(Stack *s) { return s->top == MAX_SIZE - 1; } int isEmpty(Stack *s) { return s->top == -1; } void push(Stack *s, int val) { if (isFull(s)) { printf("栈已满\n"); return; } s->data[++s->top] = val; // 先移动下标，再写数据 } int pop(Stack *s) { if (isEmpty(s)) { printf("栈为空\n"); return -1; } return s->data[s->top--]; // 先取数据，再移动下标 }

重点体会top的移动时机。入栈是++top，因为新元素要放到当前栈顶的上一个空位；出栈是top--，因为栈顶元素取走后，顶指针要下移。很多初学者写成s->data[top++] = val，看起来像是给栈顶赋值了，但第一次赋值会写到下标0，第二次写到下标1，恰好能用，可等到有元素出栈再入栈时，位置就会错乱。所以养成习惯，把push的++top和pop的top--一起记忆。

当容量不够时，顺序栈需要扩容。C语言里可以用realloc把数组扩大，常见策略是翻倍扩容。不过初始学习阶段先把固定容量版本跑通，再考虑扩容也不迟。

3.3 链式栈与函数调用栈

顺序栈的空间可能不够，链式栈就没有这个问题。链式栈就是用链表来存储元素，栈顶就是链表的头节点，入栈用头插，出栈删头节点，时间复杂度都是O(1)。

typedef struct StackNode { int data; struct StackNode *next; } StackNode; void pushLinked(StackNode **top, int val) { StackNode *newNode = createNode(val); newNode->next = *top; // 新节点指向旧栈顶 *top = newNode; // 新节点成为栈顶 } int popLinked(StackNode **top) { if (*top == NULL) return -1; StackNode *temp = *top; int val = temp->data; *top = (*top)->next; free(temp); return val; }

但我想说的是，栈这个思想在C语言里还有一层更底层的体现：函数调用栈。每次函数调用，系统都会在栈上分配一块“栈帧”，里面保存局部变量、函数参数和返回地址。当函数返回，这块栈帧就被销毁。递归为什么会把栈撑爆？因为每递归一层就新建一个栈帧，递归太深，栈空间被占满，就出现Stack Overflow。

理解了函数调用栈，你就能明白为什么递归可以解决那些嵌套结构问题：因为系统栈替你完成了“后调用先返回”的自动管理。而你自己写栈来模拟递归，本质上是把这个过程从系统栈搬到了显式数据结构里，灵活性更高，但也更难。

4. 队列：先进先出与环形空间的智慧

4.1 队列的应用场景与存储选型

队列是另一种受限线性表，它只允许在队尾插入，在队头删除，特征是先进先出，First In First Out，简称FIFO。

你排过队买奶茶就懂队列的含义：先来的先买，后来的排后面，不允许插队。操作系统里的打印任务队列、键盘输入缓冲、消息推送的顺序保证，都是队列思想的实际应用。现在后端开发里常说的“消息队列”，像RabbitMQ、Kafka这些中间件，表面上看是网络通信和持久化的问题，但它们的消费顺序、异步削峰等基本理念，底层都对FIFO结构有依赖。

队列的存储也分两种：顺序队列和链式队列。顺序队列用数组实现，操作简单但有个著名的坑叫“假溢出”；链式队列用链表实现，实现稍复杂但空间更灵活。初学者我建议两种都写，因为假溢出问题本身就是学习队列时最有价值的一个知识点。

4.2 顺序队列的“假溢出”与循环队列

先看最简单的顺序队列设计：一个数组，一个front指向队头，一个rear指向队尾。

入队时rear++，出队时front++。这个模型有个问题：如果反复入队出队，front和rear不断后移，最终rear到达数组末尾时，数组前段明明有很多空位，却没法再入队了。这就叫“假溢出”。

解决办法是循环队列，把数组的最前面和最后面“接起来”，逻辑上做成一个环。当rear走到数组末尾，下一个位置绕回下标0。在C语言里，取模运算%天然支持这个绕回。

#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int front; // 队头下标 int rear; // 队尾下标（指向最后一个元素的下一个位置） } Queue; void initQueue(Queue *q) { q->front = 0; q->rear = 0; } int isEmpty(Queue *q) { return q->front == q->rear; } int isFull(Queue *q) { return (q->rear + 1) % MAX_SIZE == q->front; } void enQueue(Queue *q, int val) { if (isFull(q)) { printf("队列已满\n"); return; } q->data[q->rear] = val; q->rear = (q->rear + 1) % MAX_SIZE; } int deQueue(Queue *q) { if (isEmpty(q)) { printf("队列为空\n"); return -1; } int val = q->data[q->front]; q->front = (q->front + 1) % MAX_SIZE; return val; }

注意循环队列的判断空和判断满条件。判空是front == rear，判满用(rear + 1) % MAX_SIZE == front。为什么判满不是rear + 1 == front？因为你不知道rear是否已经绕回0了，必须取模。而且这种判满方式牺牲了一个元素空间，即数组中永远有一个位置不存数据，这是为了区分“空”和“满”——因为如果不牺牲一个位置，空和满时都是front == rear，就没法区分了。

如果你不想浪费那一个空间，可以再加一个count字段记录元素个数，入队加1，出队减1，判断就变成count == 0或count == MAX_SIZE。这个方案在工程上也很常见。

4.3 链式队列与阻塞队列思想

链式队列是链表的另一个应用。它需要两个指针，一个head指向队头（用于出队），一个tail指向队尾（用于入队）。

typedef struct QNode { int data; struct QNode *next; } QNode; typedef struct { QNode *front; QNode *rear; } LinkedQueue; void initLinkedQueue(LinkedQueue *q) { q->front = NULL; q->rear = NULL; } void enLinkedQueue(LinkedQueue *q, int val) { QNode *newNode = createNode(val); if (q->rear == NULL) { q->front = newNode; q->rear = newNode; } else { q->rear->next = newNode; q->rear = newNode; } } int deLinkedQueue(LinkedQueue *q) { if (q->front == NULL) return -1; QNode *temp = q->front; int val = temp->data; q->front = q->front->next; if (q->front == NULL) { q->rear = NULL; } free(temp); return val; }

出队时如果队列变成空，一定要把rear也置成NULL，否则rear指向的是一个已经被free的节点，这就是野指针隐患。很多初学者只更新front，忘了处理rear，等下次入队时再去访问q->rear->next，直接段错误。

你在网上经常听到“阻塞队列”，这个词在C语言的入门数据结构里不会重点展开，因为阻塞涉及多线程的同步机制。但换个角度理解，阻塞队列的底层依然是“先进先出”规则，只不过当队列空时，消费者线程被挂起等待，当队列满时，生产者线程被挂起等待。线程池的任务队列、生产者消费者模型，核心都是“队列结构 + 等待唤醒机制”。

5. 实操过程：手写一份链表、栈、队列的完整代码

5.1 工程结构与测试环境准备

我一直觉得，学习数据结构最好的方式不是看教程，而是自己在一个文件里把这些结构从头写一遍，然后用测试代码逼着它们跑起来。我建议的步骤是：先写链表，因为栈和队列都可以用链表复用；然后写栈，抽象出push和pop；最后写队列，重点盯住循环队列的取模逻辑。

环境不需要复杂，任何支持C99标准的环境都行。我平时用的是Linux下的gcc，命令非常简单：

gcc -o demo main.c -Wall && ./demo

-Wall这个参数一定要加，它会把所有的警告提示打开。很多问题不是运行时崩溃，而是编译时期就有迹象——比如类型不匹配、变量未使用，这些警告能帮你提前发现问题。

为了演示方便，我用单文件结构，里面包含所有结构体的定义和函数实现，再把测试逻辑写在main函数里。虽然工程上要头文件和源文件分离，但学习阶段单文件更容易观察全貌。

5.2 完整代码与关键实现说明

下面这段代码把链表、栈、队列三套操作都包含了，我加了比较详细的注释，你可以直接把这份代码复制到本地编译跑一下：

#include <stdio.h> #include <stdlib.h> // ---------- 链表 ---------- typedef struct Node { int data; struct Node *next; } Node; Node *createNode(int val) { Node *n = (Node *)malloc(sizeof(Node)); if (n == NULL) { exit(1); } n->data = val; n->next = NULL; return n; } void insertAtHead(Node **head, int val) { Node *n = createNode(val); n->next = *head; *head = n; } void deleteByValue(Node **head, int val) { Node *prev = NULL; Node *cur = *head; while (cur != NULL && cur->data != val) { prev = cur; cur = cur->next; } if (cur == NULL) return; if (prev == NULL) { *head = cur->next; } else { prev->next = cur->next; } free(cur); } void printList(Node *head) { Node *p = head; while (p != NULL) { printf("%d -> ", p->data); p = p->next; } printf("NULL\n"); } // ---------- 链式栈 ---------- typedef struct StackNode { int data; struct StackNode *next; } StackNode; void pushStack(StackNode **top, int val) { StackNode *n = createNode(val); n->next = *top; *top = n; } int popStack(StackNode **top) { if (*top == NULL) return -1; StackNode *tmp = *top; int val = tmp->data; *top = (*top)->next; free(tmp); return val; } // ---------- 链式队列 ---------- typedef struct QNode { int data; struct QNode *next; } QNode; typedef struct { QNode *front; QNode *rear; } LinkedQueue; void enQueue(LinkedQueue *q, int val) { QNode *n = createNode(val); if (q->rear == NULL) { q->front = n; q->rear = n; } else { q->rear->next = n; q->rear = n; } } int deQueue(LinkedQueue *q) { if (q->front == NULL) return -1; QNode *tmp = q->front; int val = tmp->data; q->front = q->front->next; if (q->front == NULL) { q->rear = NULL; } free(tmp); return val; } int main() { // 链表测试 Node *head = NULL; insertAtHead(&head, 10); insertAtHead(&head, 20); insertAtHead(&head, 30); printf("链表: "); printList(head); deleteByValue(&head, 20); printf("删除20后: "); printList(head); // 栈测试 StackNode *top = NULL; pushStack(&top, 1); pushStack(&top, 2); pushStack(&top, 3); printf("栈出栈顺序: %d %d %d\n", popStack(&top), popStack(&top), popStack(&top)); // 队列测试 LinkedQueue q; q.front = NULL; q.rear = NULL; enQueue(&q, 100); enQueue(&q, 200); enQueue(&q, 300); printf("队列出队顺序: %d %d %d\n", deQueue(&q), deQueue(&q), deQueue(&q)); return 0; }

运行结果应该是：

链表: 30 -> 20 -> 10 -> NULL 删除20后: 30 -> 10 -> NULL 栈出栈顺序: 3 2 1 队列出队顺序: 100 200 300

你看这个结果就能直观感受到三者的差别：链表按插入顺序从左到右展示（头插时数字是反的）；栈输出是逆序（3、2、1），先进的后出；队列输出是正序（100、200、300），先进先出。这种能直接看到行为差异的测试，比背定义有用得多。

5.3 时间复杂度分析与扩展建议

把三种结构写完之后，我建议顺手做一个复杂度复盘。链表的头插和头删是O(1)，但查找、按值删除是O(n)，因为必须从头遍历；栈的入栈和出栈，不管用顺序还是链式，都是O(1)，但查找某个元素需要O(n)；队列的入队和出队同样是O(1)，前提是你维护了rear指针，否则每次出队都要从头遍历，那就退化到O(n)。

从空间上看，数组实现的顺序栈、顺序队列，空间是预分配的，固定大小，要么浪费要么溢出；链表实现的链式栈、链式队列，每个节点多一个next指针的额外开销，但空间按需分配，更灵活。

学完这些基础代码后，可以往几个方向扩展：第一，把链表改成双向链表，写一个翻转链表的函数；第二，用栈结构实现一个十进制转二进制的程序；第三，用循环队列模拟一个简单的环形缓冲区，体会生产者消费者的基本逻辑。每扩展一个方向，你对指针和内存的理解都会再深一层。

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

6.1 为什么修改链表的头指针必须传二级指针

这是我在各个技术社区里看到新手提问频率最高的一个问题。很多人写头插法时这样写：

void insertAtHead(Node *head, int val) { Node *n = createNode(val); n->next = head; head = n; // 自以为修改了外部的head }

然后在main里调用insertAtHead(head, 10);，再打印链表发现head还是NULL。原因就一句话：C语言的函数参数是按值传递，head传进去的是一个副本，函数内部修改副本不影响外部的实参。

要修改外层的指针变量，必须传入这个指针变量本身的地址，也就是Node **head。函数里*head = n时，先拿到外层的head变量地址，再往这个地址写入新值，才能生效。

同样的规则也适用于删除节点、栈的push操作。如果你不想用二级指针，也可以让函数返回新的头指针，例如Node *insertAtHead(Node *head, int val)，调用时写成head = insertAtHead(head, 10);。两种方式都行，但千万不要以为“函数内部改了指针，外面就会跟着变”，这是新手最大的思维误区。

6.2 野指针、内存泄漏与段错误的排查

这三个问题就像C语言新手的“三座大山”。

野指针是指针指向了一块已经被释放或者无效的内存。最常见场景是free了一个节点，但还有另一个指针也指向它，后面再用这个指针访问数据就出问题。比如前面链式队列删除元素时，如果你没把q->rear在队列为空时置成NULL，q->rear就变成了一个野指针。解决办法是free之后立刻养成把指针置NULL的习惯，虽然这不总是能根治问题，但能减少很多偶然的崩溃。

内存泄漏是malloc出来的内存没有free。链表、栈、队列的节点都是动态分配的，如果你只做插入不做删除，程序退出时这些内存不会自动释放（操作系统会回收整个进程的空间，但程序长时间运行就不会释放）。写小demo不容易察觉，但写一个长时间运行的服务，泄漏积累多了内存就会暴涨。排查泄漏的常用工具是Valgrind，在Linux下可以用valgrind --leak-check=full ./demo查看详细报告。

段错误是访问了不属于你的内存，通常是解引用NULL指针或者越界访问。这个错误出现时，我的排查习惯是先用gdb跑一下，比如gdb ./demo，程序崩溃后输入bt查看调用栈，能直接定位到是哪一行出了问题。如果没有gdb，也可以用最笨的办法：在程序关键位置加入printf输出，看最后一个输出在哪，问题就在后面几行。

6.3 新手指南：常见错误与解决方案速查表

我整理了一份自己这几年在教学和踩坑中总结的速查表，遇到问题可以先对号入座。

这张表里的每一个问题都是我或者身边朋友实实在在踩过的坑，很多坑甚至踩了不止一次。尤其是循环队列的判满条件，我当年第一次实现时就写成了rear + 1 == front，当rear在数组末尾时直接越界判断，找了好久才发现是取模的问题。

排查问题这件事，我的体会是：不要怕报错，更要学会“制造”有意义的输出。调试链表时，把每个节点的地址和next地址都打印出来，你看到一串地址像锁链一样串联，马上就能理解节点是怎么串起来的。数据结构的学习本质上是把抽象逻辑变成看得见的内存事实，而C语言恰好是能看到这一切的那扇窗户，这也是为什么我一直认为，这套基础值得你多花几周时间，慢一点、稳一点地吃透。