链表是一种常见的数据结构，由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的最大特点是节点在内存中不必连续存储，因而在插入和删除操作时更加高效。下面我们将详细讲解C语言中单链表、双向链表和循环链表的基本概念、实现方法及其相关操作。
以下是本文中提到的重要内容及其简要描述的表格：
| 内容 | 描述 |
|---|---|
| 单链表（Singly Linked List） | 每个节点包含一个数据域和一个指针域，指向下一个节点。头节点指向链表的第一个节点，尾节点指向 NULL。 |
| 双向链表（Doubly Linked List） | 每个节点包含数据域、前驱指针和后继指针，允许双向遍历。前驱指针指向前一个节点，后继指针指向后一个节点。 |
| 循环链表（Circular Linked List） | 最后一个节点的指针域指向头节点，形成一个环形结构。可以是单向的或双向的。 |
| 创建节点 | 动态分配内存，为链表创建新节点。 |
| 插入节点 | 将新节点插入到链表中的特定位置或链表末尾。 |
| 删除节点 | 从链表中移除特定节点，并释放相应的内存。 |
| 动态内存分配 | 链表节点在运行时动态分配和释放内存，不需要在编译时指定大小。 |
| 插入和删除效率 | 插入和删除操作效率高，在已知节点位置的情况下时间复杂度为 O(1)。 |
| 随机访问效率 | 随机访问效率低，无法通过索引直接访问元素，必须从头开始遍历，时间复杂度为 O(n)。 |
| 应用 | 常用于实现队列、栈、图和网络的表示等数据结构，以及内存管理中的空闲块管理。 |
一、单链表
1. 基本概念
单链表（Singly Linked List）是一种链表结构，其中每个节点包含一个数据域和一个指针域，指针域指向下一个节点。链表的第一个节点称为头节点，最后一个节点的指针域指向NULL，表示链表的结束。
节点结构定义
struct Node {
int data; // 数据域
struct Node* next; // 指针域，指向下一个节点
};
2. 创建链表
示例代码
#include <stdio.h>
#include <stdlib.h>
// 节点结构定义
struct Node {
int data;
struct Node* next;
};
// 创建新节点
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 添加节点到链表末尾
void append(struct Node** headRef, int data) {
struct Node* newNode = createNode(data);
if (*headRef == NULL) {
*headRef = newNode;
} else {
struct Node* temp = *headRef;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}
// 打印链表
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
append(&head, 1);
append(&head, 2);
append(&head, 3);
printList(head);
return 0;
}
输出结果
1 -> 2 -> 3 -> NULL
3. 插入节点
示例代码
// 在特定位置插入新节点
void insertAfter(struct Node* prevNode, int data) {
if (prevNode == NULL) {
printf("前置节点不能为空\n");
return;
}
struct Node* newNode = createNode(data);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
int main() {
struct Node* head = NULL;
append(&head, 1);
append(&head, 2);
append(&head, 3);
insertAfter(head->next, 4); // 在第二个节点后插入4
printList(head);
return 0;
}
输出结果
1 -> 2 -> 4 -> 3 -> NULL
4. 删除节点
示例代码
// 删除包含特定数据的节点
void deleteNode(struct Node** headRef, int key) {
struct Node* temp = *headRef;
struct Node* prev = NULL;
if (temp != NULL && temp->data == key) {
*headRef = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
int main() {
struct Node* head = NULL;
append(&head, 1);
append(&head, 2);
append(&head, 3);
deleteNode(&head, 2); // 删除包含数据2的节点
printList(head);
return 0;
}
输出结果
1 -> 3 -> NULL
二、双向链表
1. 基本概念
双向链表（Doubly Linked List）是一种链表结构，其中每个节点包含三个部分：数据域、前驱指针域和后继指针域。前驱指针指向前一个节点，后继指针指向后一个节点。双向链表允许双向遍历。
节点结构定义
struct DNode {
int data;
struct DNode* prev; // 前驱指针
struct DNode* next; // 后继指针
};
2. 创建双向链表
示例代码
#include <stdio.h>
#include <stdlib.h>
// 双向链表节点结构定义
struct DNode {
int data;
struct DNode* prev;
struct DNode* next;
};
// 创建新节点
struct DNode* createDNode(int data) {
struct DNode* newNode = (struct DNode*)malloc(sizeof(struct DNode));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// 添加节点到链表末尾
void appendD(struct DNode** headRef, int data) {
struct DNode* newNode = createDNode(data);
if (*headRef == NULL) {
*headRef = newNode;
} else {
struct DNode* temp = *headRef;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
// 打印双向链表
void printDList(struct DNode* head) {
struct DNode* temp = head;
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct DNode* head = NULL;
appendD(&head, 1);
appendD(&head, 2);
appendD(&head, 3);
printDList(head);
return 0;
}
输出结果
1 <-> 2 <-> 3 <-> NULL
3. 插入节点
示例代码
// 在特定节点后插入新节点
void insertAfterD(struct DNode* prevNode, int data) {
if (prevNode == NULL) {
printf("前置节点不能为空\n");
return;
}
struct DNode* newNode = createDNode(data);
newNode->next = prevNode->next;
prevNode->next = newNode;
newNode->prev = prevNode;
if (newNode->next != NULL) {
newNode->next->prev = newNode;
}
}
int main() {
struct DNode* head = NULL;
appendD(&head, 1);
appendD(&head, 2);
appendD(&head, 3);
insertAfterD(head->next, 4); // 在第二个节点后插入4
printDList(head);
return 0;
}
输出结果
1 <-> 2 <-> 4 <-> 3 <-> NULL
4. 删除节点
示例代码
// 删除包含特定数据的节点
void deleteDNode(struct DNode** headRef, int key) {
struct DNode* temp = *headRef;
while (temp != NULL && temp->data != key) {
temp = temp->next;
}
if (temp == NULL) return;
if (temp->prev != NULL) {
temp->prev->next = temp->next;
} else {
*headRef = temp->next;
}
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
free(temp);
}
int main() {
struct DNode* head = NULL;
appendD(&head, 1);
appendD(&head, 2);
appendD(&head, 3);
deleteDNode(&head, 2); // 删除包含数据2的节点
printDList(head);
return 0;
}
输出结果
1 <-> 3 <-> NULL
三、循环链表
1. 基本概念
循环链表（Circular Linked List）是一种链表结构，其中最后一个节点的指针域指向链表的头节点，形成一个环形结构。循环链表可以是单向的或双向的。
节点结构定义
struct CNode {
int data;
struct CNode* next;
};
2. 创建循环链表
示例代码
#include <stdio.h>
#include <stdlib.h>
// 循环链表节点结构定义
struct CNode {
int data;
struct CNode* next;
};
// 创建新节点
struct CNode* createCNode(int data) {
struct CNode* newNode = (struct CNode*)malloc(sizeof(struct CNode));
newNode->data = data;
newNode->next = newNode; // 初始时，节点的next指向自身
return newNode;
}
// 添加节点到循环链表末尾
void appendC(struct CNode** headRef, int data) {
struct CNode* newNode = createCNode(data);
if (*headRef == NULL) {
*headRef = newNode;
} else {
struct CNode* temp = *headRef;
while (temp->next != *headRef) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = *headRef;
}
}
// 打印循环链表
void printCList(struct CNode* head) {
if (head == NULL) return;
struct CNode* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(back to head)\n");
}
int main() {
struct CNode* head = NULL;
appendC(&head, 1);
appendC(&head, 2);
appendC(&head, 3);
printCList(head);
return 0;
}
输出结果
1 -> 2 -> 3 -> (back to head)
3. 插入节点
在循环链表中插入节点时，需要特别小心处理环的连接，以确保新节点正确地链接到链表中。
示例代码
// 在特定位置后插入新节点
void insertAfterC(struct CNode* prevNode, int data) {
if (prevNode == NULL) {
printf("前置节点不能为空\n");
return;
}
struct CNode* newNode = createCNode(data);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
int main() {
struct CNode* head = NULL;
appendC(&head, 1);
appendC(&head, 2);
appendC(&head, 3);
insertAfterC(head->next, 4); // 在第二个节点后插入4
printCList(head);
return 0;
}
输出结果
1 -> 2 -> 4 -> 3 -> (back to head)
4. 删除节点
在循环链表中删除节点时，特别要注意处理头节点的删除和尾节点的循环连接。
示例代码
// 删除包含特定数据的节点
void deleteCNode(struct CNode** headRef, int key) {
if (*headRef == NULL) return;
struct CNode *curr = *headRef, *prev = NULL;
// 处理头节点可能是目标节点的情况
if (curr->data == key) {
while (curr->next != *headRef) {
curr = curr->next;
}
if (curr == *headRef) {
// 链表只有一个节点
free(*headRef);
*headRef = NULL;
} else {
// 链表有多个节点
curr->next = (*headRef)->next;
free(*headRef);
*headRef = curr->next;
}
return;
}
// 查找目标节点
do {
prev = curr;
curr = curr->next;
} while (curr != *headRef && curr->data != key);
// 未找到目标节点
if (curr == *headRef) return;
// 解除目标节点
prev->next = curr->next;
free(curr);
}
int main() {
struct CNode* head = NULL;
appendC(&head, 1);
appendC(&head, 2);
appendC(&head, 3);
deleteCNode(&head, 2); // 删除包含数据2的节点
printCList(head);
return 0;
}
输出结果
1 -> 3 -> (back to head)
四、链表的优缺点与应用
1. 优点
- 动态内存分配：链表可以在运行时动态分配和释放内存，不需要在编译时指定大小。
- 插入和删除效率高：在已知节点位置的情况下，链表的插入和删除操作非常高效，时间复杂度为 O(1)。
2. 缺点
- 额外的存储开销：每个节点需要存储指针，增加了内存使用。
- 随机访问不便：无法通过索引直接访问元素，必须从头开始遍历，时间复杂度为 O(n)。
3. 常见应用
- 实现数据结构：如队列、栈等。
- 内存管理：如动态内存分配器的空闲块管理。
- 图和网络的表示：如邻接表表示法。
五、总结
链表是一种重要的基础数据结构，适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现，以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
六、结束语
- 本节内容已经全部介绍完毕，希望通过这篇文章，大家对C语言链表有了更深入的理解和认识。
- 感谢各位的阅读和支持，如果觉得这篇文章对你有帮助，请不要吝惜你的点赞和评论，这对我们非常重要。再次感谢大家的关注和支持！
