链表(Linked List)是一种基本的数据结构,由一系列节点(Node)组成,每个节点包含数据域和指向下一个节点的指针。与数组不同,链表的元素在内存中不需要连续存储,这使得它在插入和删除元素时具有更好的性能表现。
在C语言中,实现链表需要定义节点的结构体,并通过指针来连接各个节点。
链表的基本结构
首先,我们需要定义链表节点的结构体:
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int data; // 数据域
struct Node* next; // 指向下一个节点的指针
} Node;
在这个结构体中:
data
:存储节点的数据,可以是任意类型,根据需求进行调整。next
:指向链表中下一个节点的指针。如果是链表的最后一个节点,next
指针为空 (NULL
)。
创建节点
创建一个新的节点通常涉及分配内存空间并初始化其数据和指针。
// 创建一个新节点并返回指针
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 分配内存
if (!newNode) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = data; // 初始化数据
newNode->next = NULL; // 初始化指针
return newNode;
}
链表的基本操作
1. 插入节点
链表的插入操作包括在头部插入、在尾部插入和在指定位置插入。
在头部插入
void insertAtHead(Node** head, int data) {
Node* newNode = createNode(data); // 创建新节点
newNode->next = *head; // 新节点指向当前头节点
*head = newNode; // 更新头指针
}
在尾部插入
void insertAtTail(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) { // 遍历到最后一个节点
temp = temp->next;
}
temp->next = newNode;
}
在指定位置插入
void insertAfter(Node* prevNode, int data) {
if (prevNode == NULL) {
printf("前一个节点不能为空\n");
return;
}
Node* newNode = createNode(data);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
2. 删除节点
删除操作包括删除头节点、删除尾节点和删除指定节点。
删除头节点
void deleteHead(Node** head) {
if (*head == NULL) {
printf("链表为空\n");
return;
}
Node* temp = *head;
*head = (*head)->next;
free(temp);
}
删除尾节点
void deleteTail(Node** head) {
if (*head == NULL) {
printf("链表为空\n");
return;
}
if ((*head)->next == NULL) { // 只有一个节点
free(*head);
*head = NULL;
return;
}
Node* temp = *head;
while (temp->next->next != NULL) { // 找到倒数第二个节点
temp = temp->next;
}
free(temp->next);
temp->next = NULL;
}
删除指定节点
假设要删除链表中第一个值为 key
的节点:
void deleteNode(Node** head, int key) {
Node* temp = *head;
Node* prev = NULL;
// 如果头节点自身就是要删除的节点
if (temp != NULL && temp->data == key) {
*head = temp->next; // 更新头指针
free(temp);
return;
}
// 查找要删除的节点,记录前驱节点
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// 未找到
if (temp == NULL) {
printf("未找到值为 %d 的节点\n", key);
return;
}
// 从链表中移除节点
prev->next = temp->next;
free(temp);
}
3. 遍历链表
遍历链表用于显示所有节点的数据或进行其他操作。
void traverseList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
4. 搜索节点
在链表中查找是否存在某个值的节点。
Node* search(Node* head, int key) {
Node* temp = head;
while (temp != NULL) {
if (temp->data == key) {
return temp; // 找到节点
}
temp = temp->next;
}
return NULL; // 未找到
}
完整示例
下面是一个完整的示例程序,展示了如何创建链表并执行基本操作:
#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) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 在头部插入
void insertAtHead(Node** head, int data) {
Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
// 在尾部插入
void insertAtTail(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
// 在指定节点后插入
void insertAfter(Node* prevNode, int data) {
if (prevNode == NULL) {
printf("前一个节点不能为空\n");
return;
}
Node* newNode = createNode(data);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
// 删除头节点
void deleteHead(Node** head) {
if (*head == NULL) {
printf("链表为空\n");
return;
}
Node* temp = *head;
*head = (*head)->next;
free(temp);
}
// 删除尾节点
void deleteTail(Node** head) {
if (*head == NULL) {
printf("链表为空\n");
return;
}
if ((*head)->next == NULL) {
free(*head);
*head = NULL;
return;
}
Node* temp = *head;
while (temp->next->next != NULL) {
temp = temp->next;
}
free(temp->next);
temp->next = NULL;
}
// 删除指定节点
void deleteNode(Node** head, int key) {
Node* temp = *head;
Node* prev = NULL;
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
printf("未找到值为 %d 的节点\n", key);
return;
}
prev->next = temp->next;
free(temp);
}
// 遍历链表
void traverseList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// 搜索节点
Node* searchList(Node* head, int key) {
Node* temp = head;
while (temp != NULL) {
if (temp->data == key)
return temp;
temp = temp->next;
}
return NULL;
}
// 主函数示例
int main() {
Node* head = NULL; // 初始化空链表
// 插入节点
insertAtHead(&head, 3);
insertAtHead(&head, 2);
insertAtHead(&head, 1);
insertAtTail(&head, 4);
insertAtTail(&head, 5);
printf("链表内容: ");
traverseList(head); // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
// 插入节点后操作
Node* secondNode = head->next; // 节点2
insertAfter(secondNode, 99);
printf("插入99后链表内容: ");
traverseList(head); // 输出: 1 -> 2 -> 99 -> 3 -> 4 -> 5 -> NULL
// 删除头节点
deleteHead(&head);
printf("删除头节点后链表内容: ");
traverseList(head); // 输出: 2 -> 99 -> 3 -> 4 -> 5 -> NULL
// 删除尾节点
deleteTail(&head);
printf("删除尾节点后链表内容: ");
traverseList(head); // 输出: 2 -> 99 -> 3 -> 4 -> NULL
// 删除指定节点
deleteNode(&head, 99);
printf("删除值为99的节点后链表内容: ");
traverseList(head); // 输出: 2 -> 3 -> 4 -> NULL
// 搜索节点
int key = 3;
Node* found = searchList(head, key);
if (found != NULL) {
printf("找到值为 %d 的节点\n", found->data);
} else {
printf("未找到值为 %d 的节点\n", key);
}
// 释放剩余节点内存
while (head != NULL) {
deleteHead(&head);
}
return 0;
}
输出结果
链表内容: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
插入99后链表内容: 1 -> 2 -> 99 -> 3 -> 4 -> 5 -> NULL
删除头节点后链表内容: 2 -> 99 -> 3 -> 4 -> 5 -> NULL
删除尾节点后链表内容: 2 -> 99 -> 3 -> 4 -> NULL
删除值为99的节点后链表内容: 2 -> 3 -> 4 -> NULL
找到值为 3 的节点
链表的优缺点
优点
- 动态大小:链表的大小可以根据需要动态调整,不需要事先确定大小。
- 高效的插入和删除:在已知位置的情况下,插入和删除操作只需要修改指针,不需要移动其他元素。
- 节省内存:仅按需分配内存,不需要为不会用到的元素预留空间。
缺点
- 访问效率低:链表不支持随机访问,无法通过索引直接访问某个元素,需要从头开始遍历。
- 额外的内存开销:每个节点都需要额外存储指针,增加了内存消耗。
- 缓存局部性差:由于节点在内存中不连续,可能导致缓存命中率降低,影响性能。
链表的变种
双向链表(Doubly Linked List):每个节点不仅有指向下一个节点的指针,还有指向前一个节点的指针,便于双向遍历和操作。
typedef struct DNode { int data; struct DNode* next; struct DNode* prev; } DNode;
循环链表(Circular Linked List):链表的最后一个节点指向头节点,形成一个环,适用于需要循环遍历的场景。
void traverseCircularList(Node* head) { if (head == NULL) return; Node* temp = head; do { printf("%d -> ", temp->data); temp = temp->next; } while (temp != head); printf("HEAD\n"); }
跳表(Skip List):在链表的基础上增加多级索引,提高搜索效率,常用于实现高效的有序数据结构。
总结
链表是C语言中一种灵活且高效的数据结构,特别适合需要频繁插入和删除元素的场景。虽然它在随机访问和内存使用上存在一些缺点,但通过不同的变种和优化,可以在多种应用中发挥重要作用。在实际开发中,根据具体需求选择合适的数据结构是至关重要的。