行业知识
C语言之链表详解
2026-10-21 04:58:26
来源：互联网转载
���录
一、链表定义
二、链表分类
三、链表操作
四、单向链表
1.链表定义
2.插入操作
3.删除操作
4.修改操作
5.查找操作
五、双向链表
1.链表定义
2.插入操作
3.删除操作
4.修改操作
5.查找操作
一、链表定义
链表是一种基本的数据结构，它由一系列节点组成，每个节点包含一个值和指向下一个节点的指针。链表的特点是可以动态添加和删除节点，而不需要预先知道数据的数量。与数组不同，链表中的节点不一定是连续的存储空间，因此可以有效地利用内存空间。
二、链表分类
链表可以分为三种类型：
- 单向链表：每个节点只有一个指针指向下一个节点，最后一个节点的指针指向NULL。
- 双向链表：每个节点有两个指针，分别指向上一个节点和下一个节点，可以在O(1)时间内实现向前和向后遍历。
- 循环链表：在单向或双向链表的基础上，将最后一个节点的指针指向头节点，形成一个环。
三、链表操作
链表的操作包括插入、删除、查找、遍历等。
- 插入操作：可以在链表头或尾插入节点，也可以在指定位置插入节点。
- 删除操作：可以删除指定节点或按照值删除节点。
- 查找操作：可以查找指定节点或按照值查找节点。
- 遍历操作：可以遍历整个链表，输出每个节点的值或执行其他操作。
链表的优点是可以动态添加和删除节点，因此非常适用于需要频繁插入和删除数据的场景。链表的缺点是访问操作的时间复杂度为O(n)，而且需要额外的空间存储节点的指针，因此在需要频繁访问数据的场景中，效率可能不如数组。
链表在计算机科学中有广泛的应用，例如操作系统中的进程链表、文件系统中的目录链表、图论中的邻接表等。在C语言中，链表常常用于实现动态内存分配、函数调用栈、多项式运算等问题。
四、单向链表
单向链表是由若干个节点组成的数据结构，每个节点包含两个部分：数据域和指针域。数据域存储节点的数据，指针域存储下一个节点的地址。
1.链表定义
单向链表定义如下：
struct ListNode { int val; struct ListNode* next;};2.插入操作
链表的插入操作可以在链表的头部、尾部或指定位置插入节点。具体实现如下：
// 在头部插入节点struct ListNode* insertAtHead(struct ListNode* head, int val) { struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode)); new_node->val = val; new_node->next = head; return new_node;}// 在尾部插入节点struct ListNode* insertAtTail(struct ListNode* head, int val) { struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode)); new_node->val = val; new_node->next = NULL; if (head == NULL) { return new_node; } struct ListNode* p = head; while (p->next != NULL) { p = p->next; } p->next = new_node; return head;}// 在指定位置插入节点struct ListNode* insertAtIndex(struct ListNode* head, int index, int val) { int i = 0; struct ListNode* new_node = (struct ListNode*)malloc(sizeof(struct ListNode)); new_node->val = val; if (index == 0) { new_node->next = head; return new_node; } struct ListNode* p = head; while (i next; i++; } if (p == NULL) { free(new_node); return head; } new_node->next = p->next; p->next = new_node; return head;}3.删除操作
链表的删除操作可以删除指定位置或指定值的节点。具体实现如下：
// 删除指定位置的节点struct ListNode* deleteAtIndex(struct ListNode* head, int index) { int i = 0; if (head == NULL) { return NULL; } if (index == 0) { struct ListNode* temp = head; head = head->next; free(temp); return head; } struct ListNode* p = head; while (i next; i++; } if (p == NULL || p->next == NULL) { return head; } struct ListNode* temp = p->next; p->next = p->next->next; free(temp); return head;}// 删除指定值的节点struct ListNode* deleteNode(struct ListNode* head, int val) { struct ListNode* p = head; struct ListNode* prev = NULL; while (p != NULL && p->val != val) { prev = p; p = p->next; } if (p == NULL) { return head; } if (prev == NULL) { head = head->next; } else { prev->next = p->next; } free(p); return head;}4.修改操作
链表的修改操作可以修改指定位置或指定值的节点的值。具体实现如下：
// 修改指定位置的节点的值struct ListNode* modifyAtIndex(struct ListNode* head, int index, int val) { struct ListNode* p = head; int i = 0; while (i next; i++; } if (p == NULL) { return head; } p->val = val; return head;}// 修改指定值的节点的值struct ListNode* modifyNode(struct ListNode* head, int old_val, int new_val) { struct ListNode* p = head; while (p != NULL && p->val != old_val) { p = p->next; } if (p == NULL) { return head; } p->val = new_val; return head;}5.查找操作
链表的查找操作可以查找指定位置或指定值的节点。具体实现如下：
// 查找指定位置的节点的值int getValAtIndex(struct ListNode* head, int index) { struct ListNode* p = head; int i = 0; while (i next; i++; } if (p == NULL) { return -1; } return p->val;}// 查找指定值的节点的位置int getIndexByVal(struct ListNode* head, int val) { struct ListNode* p = head; int i = 0; while (p != NULL && p->val != val) { p = p->next; i++; } if (p == NULL) { return -1; } return i;}以上是链表的基本操作，实现时需要注意空指针和越界等问题。
五、双向链表
双向链表和单向链表的不同在于每个节点有两个指针，分别指向前驱节点和后继节点。双向链表的优点是可以实现双向遍历和O(1)的删除操作，缺点是每个节点需要额外的一个指针。
1.链表定义
双向链表定义如下：
struct ListNode { int val; struct ListNode* prev; struct ListNode* next;};2.插入操作
双向链表的插入操作可以在指定位置前面或后面插入节点，具体实现如下：
// 在指定位置前面插入节点struct ListNode* insertBefore(struct ListNode* head, int index, int val) { struct ListNode* p = head; int i = 0; while (i next; i++; } if (p == NULL) { return head; } struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode)); node->val = val; node->prev = p->prev; node->next = p; if (p->prev != NULL) { p->prev->next = node; } else { head = node; } p->prev = node; return head;}// 在指定位置后面插入节点struct ListNode* insertAfter(struct ListNode* head, int index, int val) { struct ListNode* p = head; int i = 0; while (i next; i++; } if (p == NULL) { return head; } struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode)); node->val = val; node->prev = p; node->next = p->next; if (p->next != NULL) { p->next->prev = node; } p->next = node; return head;}3.删除操作
双向链表的删除操作可以删除指定位置或指定值的节点，具体实现如下：
// 删除指定位置的节点struct ListNode* deleteAtIndex(struct ListNode* head, int index) { struct ListNode* p = head; int i = 0; while (i next; i++; } if (p == NULL) { return head; } if (p->prev != NULL) { p->prev->next = p->next; } else { head = p->next; } if (p->next != NULL) { p->next->prev = p->prev; } free(p); return head;}// 删除指定值的节点struct ListNode* deleteNode(struct ListNode* head, int val) { struct ListNode* p = head; while (p != NULL && p->val != val) { p = p->next; } if (p == NULL) { return head; } if (p->prev != NULL) { p->prev->next = p->next; } else { head = p->next; } if (p->next != NULL) { p->next->prev = p->prev; } free(p); return head;}4.修改操作
双向链表的修改操作可以直接修改指定节点的值，具体实现如下：
// 修改指定位置的节点值struct ListNode* updateAtIndex(struct ListNode* head, int index, int val) { struct ListNode* p = head; int i = 0; while (i next; i++; } if (p == NULL) { return head; } p->val = val; return head;}5.查找操作
双向链表的查找操作可以按位置或按值查找，具体实现如下：
// 按位置查找节点struct ListNode* getNodeAtIndex(struct ListNode* head, int index) { struct ListNode* p = head; int i = 0; while (i next; i++; } return p;}// 按值查找节点struct ListNode* getNodeByValue(struct ListNode* head, int val) { struct ListNode* p = head; while (p != NULL && p->val != val) { p = p->next; } return p;}如果觉得文章写的还不错，麻烦点赞，收藏加关注哦！
关于更多嵌入式C语言、FreeRTOS、RT-Thread、Linux应用编程、linux驱动等相关知识，关注公众号【嵌入式Linux知识共享】，后续精彩内容及时收看了解。
上一篇：服务器关闭怎么补偿?
