一、什么是链表链表Linked List是一种非连续、非顺序的线性数据结构它通过指针将一组零散的内存块串联起来每个内存块被称为节点Node。简单来说链表就像一串 “糖葫芦”每个 “山楂” 是一个节点包含数据和下一个节点的地址通过 “竹签”指针将所有节点串联起来形成一个完整的链条。二、链表的核心结构节点每个链表节点由两部分组成数据域存储节点的具体数据指针域存储下一个节点的地址。对应的 C 语言代码定义如下// 链表节点结构体 typedef struct Node { int data; // 数据域存储节点数据 struct Node* next; // 指针域指向next节点 } Node;三、链表的基本操作1. 头插法在链表头部插入节点头插法是将新节点插入到链表的最前端步骤如下让新节点的next指向当前的头节点更新头节点为新节点。代码实现// 头插法在链表头部插入新节点 void headInsert(Node** head, int value) { // 1. 创建新节点 Node* newNode (Node*)malloc(sizeof(Node)); newNode-data value; // 2. 新节点的next指向当前头节点 newNode-next *head; // 3. 更新头节点为新节点 *head newNode; }2. 尾插法在链表尾部插入节点尾插法是将新节点插入到链表的最后端步骤如下遍历链表找到最后一个节点让最后一个节点的next指向新节点新节点的next指向NULL。代码实现// 尾插法在链表尾部插入新节点 void tailInsert(Node** head, int value) { // 1. 创建新节点 Node* newNode (Node*)malloc(sizeof(Node)); newNode-data value; newNode-next NULL; // 2. 如果链表为空直接让头节点指向新节点 if (*head NULL) { *head newNode; return; } // 3. 遍历找到最后一个节点 Node* p *head; while (p-next ! NULL) { p p-next; } // 4. 最后一个节点的next指向新节点 p-next newNode; }3. 遍历链表遍历链表是从头部开始依次访问每个节点直到遇到NULL结束时间复杂度为O(n)。代码实现// 遍历链表并打印所有节点 void traverseList(Node* head) { Node* p head; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }4. 指定位置插入节点在指定位置插入节点需要先找到该位置的前驱节点步骤如下遍历找到前驱节点p让新节点的next指向p的next让p的next指向新节点。代码实现// 指定位置插入节点在第pos个位置插入新节点pos从0开始 void insertAt(Node** head, int pos, int value) { // 1. 处理头插情况pos0 if (pos 0) { headInsert(head, value); return; } // 2. 找到前驱节点 Node* p *head; for (int i 0; i pos - 1 p ! NULL; i) { p p-next; } // 3. 如果前驱节点不存在直接返回 if (p NULL) { printf(插入位置无效\n); return; } // 4. 创建新节点并插入 Node* newNode (Node*)malloc(sizeof(Node)); newNode-data value; newNode-next p-next; p-next newNode; }5. 指定位置删除节点删除指定位置的节点需要先找到该位置的前驱节点步骤如下遍历找到前驱节点p保存要删除的节点tmp p-next让p的next指向tmp的next释放tmp的内存。代码实现// 指定位置删除节点删除第pos个位置的节点pos从0开始 void deleteAt(Node** head, int pos) { // 1. 处理头删情况pos0 if (pos 0 *head ! NULL) { Node* tmp *head; *head (*head)-next; free(tmp); return; } // 2. 找到前驱节点 Node* p *head; for (int i 0; i pos - 1 p ! NULL p-next ! NULL; i) { p p-next; } // 3. 如果前驱节点或要删除的节点不存在直接返回 if (p NULL || p-next NULL) { printf(删除位置无效\n); return; } // 4. 删除节点并释放内存 Node* tmp p-next; p-next tmp-next; free(tmp); }6. 头删与尾删 头删直接删除头节点更新头节点为下一个节点 尾删遍历找到倒数第二个节点让其next指向NULL释放最后一个节点。 代码实现// 头删删除链表的第一个节点 void headDelete(Node** head) { if (*head NULL) { printf(链表为空无法头删\n); return; } Node* tmp *head; *head (*head)-next; free(tmp); } // 尾删删除链表的最后一个节点 void tailDelete(Node** head) { if (*head NULL) { printf(链表为空无法尾删\n); return; } // 1. 如果只有一个节点直接删除 if ((*head)-next NULL) { free(*head); *head NULL; return; } // 2. 找到倒数第二个节点 Node* p *head; while (p-next-next ! NULL) { p p-next; } // 3. 删除最后一个节点 Node* tmp p-next; p-next NULL; free(tmp); }四、链表 vs 数组链表和数组是两种最常用的线性数据结构它们的区别如下五、链表的适用场景根据链表和数组的特性它们的适用场景如下链表适用场景数据量不确定需要动态扩容频繁进行插入、删除操作不需要频繁随机访问。数组适用场景数据量固定需要频繁随机访问内存连续需要高访问效率。六、完整代码示例#include stdio.h #include stdlib.h // 链表节点结构体 typedef struct Node { int data; struct Node* next; } Node; // 头插法 void headInsert(Node** head, int value) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data value; newNode-next *head; *head newNode; } // 尾插法 void tailInsert(Node** head, int value) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data value; newNode-next NULL; if (*head NULL) { *head newNode; return; } Node* p *head; while (p-next ! NULL) { p p-next; } p-next newNode; } // 遍历链表 void traverseList(Node* head) { Node* p head; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 指定位置插入 void insertAt(Node** head, int pos, int value) { if (pos 0) { headInsert(head, value); return; } Node* p *head; for (int i 0; i pos - 1 p ! NULL; i) { p p-next; } if (p NULL) { printf(插入位置无效\n); return; } Node* newNode (Node*)malloc(sizeof(Node)); newNode-data value; newNode-next p-next; p-next newNode; } // 指定位置删除 void deleteAt(Node** head, int pos) { if (pos 0 *head ! NULL) { Node* tmp *head; *head (*head)-next; free(tmp); return; } Node* p *head; for (int i 0; i pos - 1 p ! NULL p-next ! NULL; i) { p p-next; } if (p NULL || p-next NULL) { printf(删除位置无效\n); return; } Node* tmp p-next; p-next tmp-next; free(tmp); } // 头删 void headDelete(Node** head) { if (*head NULL) { printf(链表为空无法头删\n); return; } Node* tmp *head; *head (*head)-next; free(tmp); } // 尾删 void tailDelete(Node** head) { if (*head NULL) { printf(链表为空无法尾删\n); return; } if ((*head)-next NULL) { free(*head); *head NULL; return; } Node* p *head; while (p-next-next ! NULL) { p p-next; } Node* tmp p-next; p-next NULL; free(tmp); } // 释放链表内存 void freeList(Node** head) { Node* p *head; while (p ! NULL) { Node* tmp p; p p-next; free(tmp); } *head NULL; } int main() { Node* head NULL; // 测试头插法 headInsert(head, 3); headInsert(head, 5); headInsert(head, 7); printf(头插后链表); traverseList(head); // 输出7 5 3 // 测试尾插法 tailInsert(head, 9); printf(尾插后链表); traverseList(head); // 输出7 5 3 9 // 测试指定位置插入 insertAt(head, 2, 6); printf(在位置2插入6后); traverseList(head); // 输出7 5 6 3 9 // 测试指定位置删除 deleteAt(head, 2); printf(删除位置2的节点后); traverseList(head); // 输出7 5 3 9 // 测试头删 headDelete(head); printf(头删后链表); traverseList(head); // 输出5 3 9 // 测试尾删 tailDelete(head); printf(尾删后链表); traverseList(head); // 输出5 3 // 释放链表内存 freeList(head); printf(释放内存后链表为空%s\n, head NULL ? 是 : 否); // 输出是 return 0; }七、总结链表是一种动态、灵活的线性数据结构它通过指针将节点串联起来支持高效的插入和删除操作但随机访问效率较低。在实际开发中链表常用于动态数组如ArrayList的底层实现队列、栈等数据结构的实现操作系统的内存管理图和树的遍历等。希望这篇文章能帮助你深入理解链表的原理和实现