一、链表定义
1.什么是链表
链表是一种动态数据结构，由一系列节点组成，每个节点包含两部分：
C算法
C 语言链表入门详解
C 语言中链表的基础知识，包括链表定义、与数组的对比、节点结构及类型。详细讲解了创建、输出、插入、删除等核心操作，并提供了栈、队列及多项式运算的应用示例。最后总结了内存管理、指针操作等常见易错点及调试方法，帮助初学者掌握动态数据结构的使用。
C 语言中链表的基础知识，包括链表定义、与数组的对比、节点结构及类型。详细讲解了创建、输出、插入、删除等核心操作，并提供了栈、队列及多项式运算的应用示例。最后总结了内存管理、指针操作等常见易错点及调试方法，帮助初学者掌握动态数据结构的使用。
链表是一种动态数据结构，由一系列节点组成，每个节点包含两部分：
与数组不同。例如，在定义一个班级的人数时，如果小班是 30 人，普通班级是 50 人，且定义班级人数时使用的是数组，那么定义数组的大小应为最大人数，也就是最少为 50 个元素，否则不满足最大时的情况，这种方式非常浪费空间。
这时就希望有一种存储方式，其存储元素的个数是不受限制的，当添加元素时存储元素的个数就会随之改变，这种存储方式就是链表。链表的元素在内存中不是连续存储的，而是通过指针连接起来。
链表结构的示意图如下图所示：
图 1 链表结构的示意图
从图 1 可以看到，head（头）节点指向第 1 个元素，第 1 个元素中的指针又指向第 2 个元素的地址，第 2 个元素的指针又指向第 3 个元素的地址，第 3 个元素的指针指向空。
注意，链表这种数据结构必须利用指针才能实现，因此链表中的节点应该包含一个指针变量来保存下一个节点的地址。
例如，设计一个链表表示一个班级，其中链表中的节点表示学生，代码如下：
struct Student {
char cName[20]; /*姓名*/
int iNumber; /*学号*/
struct Student* pNext; /*指向下一个节点的指针*/
};
可以看到学生的姓名和学号属于数据部分，而 pNext 就是指针部分，用来保存下一个节点的地址。
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存分配 | 静态，编译时确定 | 动态，运行时分配 |
| 内存连续性 | 连续 | 不连续 |
| 插入/删除效率 | O(n) | O(1)（已知位置） |
| 访问效率 | O(1) | O(n) |
| 大小 | 固定 | 可动态调整 |
// 定义链表节点
struct ListNode {
int data; // 数据域
struct ListNode *next; // 指针域，指向下一个节点
};
// 为了方便，通常使用 typedef
typedef struct ListNode {
int data;
struct ListNode *next;
} Node;
从前面的讲解不难看出，链表并不是一开始就设定好大小的，而是根据节点的多少确定的，因此链表的创建过程是一个动态的过程。
定义一个 Create() 函数，用来创建链表。该函数会返回链表的头指针，代码如下：
int iCount; /*全局变量表示链表长度*/
struct Student* Create() {
struct Student* pHead = NULL; /*初始化链表头指针，使其为空*/
struct Student* pEnd, *pNew;
iCount = 0; /*初始化链表长度*/
pEnd = pNew = (struct Student*)malloc(sizeof(struct Student));
printf("please first enter Name ,then Number\n");
scanf("%s", &pNew->cName);
scanf("%d", &pNew->iNumber);
while (pNew->iNumber != 0) {
iCount++;
if (iCount == 1) {
pNew->pNext = pHead; /*使得指向为空*/
pEnd = pNew; /*跟踪新加入的节点*/
pHead = pNew; /*头指针指向首节点*/
} else {
pNew->pNext = NULL; /*新节点的指针为空*/
pEnd->pNext = pNew; /*原来的尾节点指向新节点*/
pEnd = pNew; /*pEnd 指向新节点*/
}
pNew = (struct Student*)malloc(sizeof(struct Student)); /*再次分配节点内存空间*/
scanf("%s", &pNew->cName);
scanf("%d", &pNew->iNumber);
}
free(pNew); /*释放没有用到的空间*/
return pHead;
}
从上述代码中可以看出以下内容：
这样，链表就通过动态分配内存空间的方式创建完成了。
首先先创建节点
#include <stdio.h>
#include <stdlib.h>
// 节点定义
typedef struct Node {
int data;
struct Node *next;
} Node;
// 创建新节点
Node* createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败！\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 头插法 - 新节点插入在链表头部
Node* insertAtHead(Node *head, int data) {
Node *newNode = createNode(data);
newNode->next = head;
return newNode; // 返回新的头节点
}
// 尾插法 - 新节点插入在链表尾部
Node* insertAtTail(Node *head, int data) {
Node *newNode = createNode(data);
// 如果链表为空，新节点就是头节点
if (head == NULL) {
return newNode;
}
// 找到最后一个节点
Node *current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
return head;
}
链表已经被创建出来，构建数据结构就是为了使用它，以将保存的信息进行输出。接下来介绍如何将链表中的数据输出。代码如下：
void print(struct Student* pHead) {
struct Student *pTemp; /*循环所用的临时指针*/
int iIndex = 1; /*表示链表中节点的序号*/
printf("----the List has %d members:----\n", iCount); /*提示信息*/
printf("\n"); /*换行*/
pTemp = pHead; /*指针得到首节点的地址*/
while (pTemp != NULL) {
printf("the NO%d member is:\n", iIndex);
printf("the name is: %s\n", pTemp->cName); /*输出姓名*/
printf("the number is: %d\n", pTemp->iNumber); /*输出学号*/
printf("\n"); /*换行*/
pTemp = pTemp->pNext; /*移动临时指针到下一个节点*/
iIndex++; /*进行自加运算*/
}
}
结合创建链表和输出链表的过程，运行程序，结果为：
please first enter Name ,then Number
dahua 1
xiaoning 2
daxhuang 3
lucy 4
exit 0
----the List has 4 members:----
the N01 member is:
the name is: dahua
the number is: 1
the N02 member is:
the name is: xiaoning
the number is: 2
the N03 member is:
the name is: daxhuang
the number is: 3
the N04 member is:
the name is: lucy
the number is: 4
printf() 函数用来将链表中的数据进行输出。在函数的参数中，pHead 表示一个链表的头节点。在函数中，定义一个临时的指针 pTemp 用来进行循环操作。定义一个整型变量表示链表中的节点序号。然后使用临时指针变量 pTemp 保存首节点的地址。
使用 while 语句将所有节点中保存的数据都输出。每输出一个节点的数据后，就移动 pTemp 指针指向下一个节点的地址。当为最后一个节点时，其所有的指针指向空，此时循环结束。
链表的插入操作可以在链表的头节点位置进行，也可以在某个节点的位置进行，或者可以像创建结构一样在链表的后面添加节点。这 3 种插入操作的思路都是一样的。
下面主要介绍第一种插入操作，即在链表的头节点位置插入节点，如下图所示：
图 2 插入节点
插入节点的过程就如手拉手的小朋友连成一条线，这时又来了一个小朋友，他要站在第一位小朋友的前面，那么他只需要牵原来第一位小朋友的手就可以了。这样，这条连成的线还是连在一起的。
设计一个函数用来向链表中添加节点，代码如下：
struct Student* Insert(struct Student* pHead) {
struct Student* pNew; /*指向新分配的空间*/
printf("----Insert member at first----\n"); /*提示信息*/
pNew = (struct Student*)malloc(sizeof(struct Student)); /*分配内存空间，并返回指向该内存空间的指针*/
scanf("%s", &pNew->cName);
scanf("%d", &pNew->iNumber);
pNew->pNext = pHead; /*新节点指针指向原来的首节点*/
pHead = pNew; /*头指针指向新节点*/
iCount++; /*增加链表节点数量*/
return pHead; /*返回头指针*/
}
上述代码插入节点的步骤如下：
主函数 main() 的代码如下：
int main() {
struct Student* pHead; /*定义头节点*/
pHead = Create(); /*创建节点*/
pHead = Insert(pHead); /*插入节点*/
print(pHead); /*输出链表*/
return 0; /*程序结束*/
}
运行程序，结果为：
please first enter Name ,then Number
liuwen 2
suyunjing 3
exit 0
----Insert member at first----
wangjiashen 1
----the List has 3 members:----
the N01 member is:
the name is: wangjiashen
the number is: 1
the N02 member is:
the name is: liuwen
the number is: 2
the N03 member is:
the name is: suyunjing
the number is: 3
之前介绍的操作是向链表中添加节点，当希望删除链表中的节点时，应该怎么办呢？还是通过前文中小朋友手拉手的例子进行介绍，队伍中的一个小朋友想离开，使这个队伍不会断开的方法是他两边的小朋友将手拉起来。
例如，在一个链表中删除其中的一个节点，如下图所示：
图 3 删除节点
通过图 3 可以发现，要删除一个节点，先要找到这个节点的位置。例如要删除 NO2 节点，首先要找到 NO2 节点，然后删除该节点，将 NO1 节点的指针指向 NO3 节点，最后释放 NO2 节点的内存空间，这样就完成了节点的删除。
根据这种思想编写删除链表节点的函数，代码如下：
void Delete(struct Student* pHead, int iIndex) /*pHead 表示头节点，iIndex 表示要删除的节点索引*/ {
int i; /*控制循环的变量*/
struct Student* pTemp; /*临时指针*/
struct Student* pPre; /*表示要删除的节点前的节点*/
pTemp = pHead; /*得到头节点*/
pPre = pTemp;
printf("----delete NO%d member----\n", iIndex); /*提示信息*/
/*for 循环使得 pTemp 指向要删除的节点*/
for (i = 1; i<iIndex; i++) {
pPre = pTemp;
pTemp = pTemp->pNext;
}
pPre->pNext = pTemp->pNext; /*连接要删除的节点两边的节点*/
free(pTemp); /*释放要删除的节点的内存空间*/
iCount--; /*减少链表中的元素个数*/
}
为 Delete() 函数传递两个参数，pHead 表示链表的头节点，iIndex 表示要删除的节点的索引。定义整型变量 i 用来控制循环的次数，然后定义两个指针，分别用来表示要删除的节点和这个节点之前的节点。
输出一行提示信息表示要进行删除操作，之后利用 for 语句进行循环操作，找到要删除的节点，使用 pTemp 保存要删除节点的地址，pPre 保存前一个节点的地址。找到要删除的节点后，连接要删除的节点两边的节点，并使用 free() 函数将 pTemp 指向的内存空间释放。
接下来在 main() 函数中添加代码执行删除操作，将链表中的第二个节点删除。代码如下：
int main() {
struct Student* pHead; /*定义头节点*/
pHead = Create(); /*创建节点*/
pHead = Insert(pHead); /*插入节点*/
Delete(pHead, 2); /*删除第二个节点的操作*/
print(pHead); /*输出链表*/
return 0; /*程序结束*/
}
运行程序，通过运行结果可以看到第二个节点中的数据被删除，结果为：
please first enter Name ,then Number
WangJun 2
LiXin 3
exit 0
----Insert member at first----
XuMing 1
----delete N02 member----
----the List has 2 members:----
the N01 member is:
the name is: XuMing
the number is: 1
the N02 member is:
the name is: LiXin
the number is: 3
// 遍历链表并打印
void printList(Node *head) {
Node *current = head;
printf("链表内容：");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
// 查找节点
Node* searchNode(Node *head, int data) {
Node *current = head;
while (current != NULL) {
if (current->data == data) {
return current;
}
current = current->next;
}
return NULL; // 未找到
}
// 获取链表长度
int getLength(Node *head) {
int length = 0;
Node *current = head;
while (current != NULL) {
length++;
current = current->next;
}
return length;
}
// 释放整个链表
void freeList(Node *head) {
Node *current = head;
while (current != NULL) {
Node *temp = current;
current = current->next;
free(temp);
}
printf("链表已释放\n");
}
#include <stdio.h>
#include <stdlib.h>
// 节点定义
typedef struct Node {
int data;
struct Node *next;
} Node;
// 函数声明
Node* createNode(int data);
Node* insertAtHead(Node *head, int data);
Node* insertAtTail(Node *head, int data);
Node* insertAtPosition(Node *head, int data, int position);
Node* deleteNode(Node *head, int data);
Node* searchNode(Node *head, int data);
void printList(Node *head);
int getLength(Node *head);
void freeList(Node *head);
int main() {
Node *head = NULL;
printf("=== 链表操作演示 ===\n");
// 尾插法创建链表
head = insertAtTail(head, 10);
head = insertAtTail(head, 20);
head = insertAtTail(head, 30);
printf("初始链表：");
printList(head);
// 头插法
head = insertAtHead(head, 5);
printf("头插入 5 后：");
printList(head);
// 在指定位置插入
head = insertAtPosition(head, 15, 2);
printf("在位置 2 插入 15 后：");
printList(head);
// 删除节点
head = deleteNode(head, 20);
printf("删除 20 后：");
printList(head);
// 查找节点
Node *found = searchNode(head, 15);
if (found != NULL) {
printf("找到节点：%d\n", found->data);
} else {
printf("未找到节点\n");
}
// 获取长度
printf("链表长度：%d\n", getLength(head));
// 释放内存
freeList(head);
return 0;
}
// 函数实现（前面已经给出，此处省略重复代码）
// 使用链表实现栈
typedef struct Stack {
Node *top;
} Stack;
Stack* createStack() {
Stack *stack = (Stack*)malloc(sizeof(Stack));
stack->top = NULL;
return stack;
}
void push(Stack *stack, int data) {
stack->top = insertAtHead(stack->top, data);
}
int pop(Stack *stack) {
if (stack->top == NULL) {
printf("栈为空！\n");
return -1;
}
int data = stack->top->data;
stack->top = deleteNode(stack->top, data);
return data;
}
int peek(Stack *stack) {
if (stack->top == NULL) {
printf("栈为空！\n");
return -1;
}
return stack->top->data;
}
// 使用链表实现队列
typedef struct Queue {
Node *front;
Node *rear;
} Queue;
Queue* createQueue() {
Queue *queue = (Queue*)malloc(sizeof(Queue));
queue->front = queue->rear = NULL;
return queue;
}
void enqueue(Queue *queue, int data) {
Node *newNode = createNode(data);
if (queue->rear == NULL) {
queue->front = queue->rear = newNode;
return;
}
queue->rear->next = newNode;
queue->rear = newNode;
}
int dequeue(Queue *queue) {
if (queue->front == NULL) {
printf("队列为空！\n");
return -1;
}
int data = queue->front->data;
Node *temp = queue->front;
queue->front = queue->front->next;
if (queue->front == NULL) {
queue->rear = NULL;
}
free(temp);
return data;
}
// 多项式节点
typedef struct PolyNode {
int coeff; // 系数
int exp; // 指数
struct PolyNode *next;
} PolyNode;
// 多项式加法
PolyNode* addPolynomials(PolyNode *poly1, PolyNode *poly2) {
PolyNode *result = NULL;
PolyNode *tail = NULL;
while (poly1 != NULL && poly2 != NULL) {
PolyNode *newNode = (PolyNode*)malloc(sizeof(PolyNode));
if (poly1->exp == poly2->exp) {
newNode->coeff = poly1->coeff + poly2->coeff;
newNode->exp = poly1->exp;
poly1 = poly1->next;
poly2 = poly2->next;
} else if (poly1->exp > poly2->exp) {
newNode->coeff = poly1->coeff;
newNode->exp = poly1->exp;
poly1 = poly1->next;
} else {
newNode->coeff = poly2->coeff;
newNode->exp = poly2->exp;
poly2 = poly2->next;
}
newNode->next = NULL;
if (result == NULL) {
result = tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}
// 处理剩余节点
while (poly1 != NULL) {
PolyNode *newNode = (PolyNode*)malloc(sizeof(PolyNode));
newNode->coeff = poly1->coeff;
newNode->exp = poly1->exp;
newNode->next = NULL;
tail->next = newNode;
tail = newNode;
poly1 = poly1->next;
}
while (poly2 != NULL) {
PolyNode *newNode = (PolyNode*)malloc(sizeof(PolyNode));
newNode->coeff = poly2->coeff;
newNode->exp = poly2->exp;
newNode->next = NULL;
tail->next = newNode;
tail = newNode;
poly2 = poly2->next;
}
return result;
}
错误示例
// 错误：忘记分配内存
Node *newNode;
newNode->data = 10; // 未分配内存就使用
// 错误：内存泄漏
void addNode(Node *head, int data) {
Node *newNode = createNode(data);
// 忘记将新节点连接到链表
}
正确做法
// 正确：分配内存并检查
Node *newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
// 处理内存分配失败
}
// 正确：确保新节点被正确连接
newNode->next = head->next;
head->next = newNode;
错误示例
// 错误：丢失头指针
void wrongDelete(Node *head, int data) {
// 如果删除的是头节点，头指针会丢失
if (head->data == data) {
Node *temp = head;
head = head->next; // 这个修改不会影响外部的 head
free(temp);
}
}
正确做法
// 正确：返回新的头指针
Node* correctDelete(Node *head, int data) {
if (head->data == data) {
Node *temp = head;
head = head->next;
free(temp);
return head; // 返回新的头指针
}
// ... 其他删除逻辑
return head;
}
// 处理各种边界条件
Node* safeInsert(Node *head, int data, int position) {
// 1. 检查位置是否合法
if (position < 0) {
printf("位置不能为负数\n");
return head;
}
// 2. 空链表且位置不为 0
if (head == NULL && position != 0) {
printf("位置超出链表长度\n");
return head;
}
// 3. 位置为 0（头插）
if (position == 0) {
return insertAtHead(head, data);
}
// 4. 正常插入逻辑
// ...
}
// 检测链表是否有环
int hasCycle(Node *head) {
if (head == NULL || head->next == NULL) {
return 0;
}
Node *slow = head;
Node *fast = head->next;
while (slow != fast) {
if (fast == NULL || fast->next == NULL) {
return 0;
}
slow = slow->next;
fast = fast->next->next;
}
return 1;
}
// 详细的链表打印函数
void debugPrintList(Node *head, const char *listName) {
printf("=== 调试信息：%s ===\n", listName);
printf("头节点地址：%p\n", (void*)head);
Node *current = head;
int count = 0;
while (current != NULL) {
printf("节点 [%d]: 地址=%p, data=%d, next=%p\n", count, (void*)current, current->data, (void*)current->next);
current = current->next;
count++;
// 防止无限循环
if (count > 100) {
printf("警告：可能存在循环链表！\n");
break;
}
}
printf("链表长度：%d\n", count);
printf("========================\n");
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online