单链表的基本概念
一个单链表由一系列节点组成,每个节点包含两部分：
（图片来源网络，侵删）
- 数据域：存储实际的数据。
- 指针域：存储指向下一个节点的内存地址。
整个链表通过一个头指针 来标识，头指针指向链表的第一个节点，如果链表为空，头指针就为 NULL。
节点结构示意图：
+-------+ +-------+ +-------+ +-------+
| Data | -> | Data | -> | Data | -> | ... |
+-------+ +-------+ +-------+ +-------+
| | | |
next-> next-> next-> next-> NULL
| | | |
Head Node Second Node Third Node Tail Node定义单链表的结构
在C语言中，我们通常使用 struct 来定义节点。
#include <stdio.h>
#include <stdlib.h> // 用于 malloc 和 free
// 定义链表节点结构体
typedef struct Node {
int data; // 数据域，这里以整型为例
struct Node *next; // 指针域，指向下一个节点
} Node;
// 定义链表结构体，包含头指针和链表长度（可选，但推荐）
typedef struct {
Node *head; // 头指针
int length; // 链表长度
} LinkedList;
单链表的基本操作实现
我们将围绕 LinkedList 结构体来实现所有操作。
（图片来源网络，侵删）
1 初始化链表
创建一个空链表，头指针指向 NULL,长度为0。
// 初始化链表
void initList(LinkedList *L) {
L->head = NULL;
L->length = 0;
}
2 销毁链表
释放链表中所有节点的内存,防止内存泄漏。
// 销毁链表，释放所有节点
void destroyList(LinkedList *L) {
Node *current = L->head;
Node *nextNode;
while (current != NULL) {
nextNode = current->next; // 保存下一个节点的地址
free(current); // 释放当前节点
current = nextNode; // 移动到下一个节点
}
L->head = NULL;
L->length = 0;
}
3 插入节点
插入操作是链表的精髓,通常分为三种情况：
a) 在头部插入（头插法）
创建一个新节点，使其 next 指向原来的头节点,然后更新链表的头指针。
（图片来源网络，侵删）
// 在链表头部插入一个新节点
void insertAtHead(LinkedList *L, int data) {
// 1. 创建新节点
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败!\n");
return;
}
newNode->data = data;
// 2. 新节点的next指向当前的头节点
newNode->next = L->head;
// 3. 更新链表的头指针
L->head = newNode;
// 4. 更新链表长度
L->length++;
}
b) 在尾部插入（尾插法）
需要遍历到链表末尾，然后将最后一个节点的 next 指向新节点，为了提高效率,可以维护一个尾指针。
// 在链表尾部插入一个新节点
void insertAtTail(LinkedList *L, int data) {
// 1. 创建新节点
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败!\n");
return;
}
newNode->data = data;
newNode->next = NULL; // 新节点是最后一个，所以next为NULL
// 2. 如果链表为空，新节点就是头节点
if (L->head == NULL) {
L->head = newNode;
} else {
// 3. 否则，遍历到链表末尾
Node *current = L->head;
while (current->next != NULL) {
current = current->next;
}
// 4. 将最后一个节点的next指向新节点
current->next = newNode;
}
// 5. 更新链表长度
L->length++;
}
c) 在指定位置插入 找到插入位置的前一个节点，然后进行插入操作，注意边界条件（如插入位置为0）。
// 在指定位置插入一个新节点 (位置从0开始)
void insertAtPosition(LinkedList *L, int data, int position) {
// 检查位置是否合法
if (position < 0 || position > L->length) {
printf("插入位置不合法!\n");
return;
}
// 如果在头部插入，复用头插法逻辑
if (position == 0) {
insertAtHead(L, data);
return;
}
// 1. 创建新节点
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败!\n");
return;
}
newNode->data = data;
// 2. 找到插入位置的前一个节点
Node *current = L->head;
for (int i = 0; i < position - 1; i++) {
current = current->next;
}
// 3. 插入节点
newNode->next = current->next; // 新节点指向原位置的后继节点
current->next = newNode; // 前驱节点指向新节点
// 4. 更新链表长度
L->length++;
}
4 删除节点
同样分为三种情况：
a) 删除头部节点 将头指针指向第二个节点,然后释放原来的第一个节点。
// 删除头部的节点
void deleteAtHead(LinkedList *L) {
if (L->head == NULL) {
printf("链表为空，无法删除!\n");
return;
}
Node *temp = L->head; // 临时保存要删除的节点
L->head = L->head->next; // 头指针后移一位
free(temp); // 释放原头节点的内存
L->length--;
}
b) 删除尾部节点
需要遍历到倒数第二个节点，将其 next 设为 NULL,然后释放最后一个节点。
// 删除尾部的节点
void deleteAtTail(LinkedList *L) {
if (L->head == NULL) {
printf("链表为空，无法删除!\n");
return;
}
// 如果链表只有一个节点
if (L->head->next == NULL) {
free(L->head);
L->head = NULL;
} else {
// 遍历到倒数第二个节点
Node *current = L->head;
while (current->next->next != NULL) {
current = current->next;
}
// 释放最后一个节点
free(current->next);
// 将倒数第二个节点的next设为NULL
current->next = NULL;
}
L->length--;
}
c) 删除指定位置的节点
找到要删除节点的前一个节点，然后修改其 next 指针,跳过要删除的节点。
// 删除指定位置的节点 (位置从0开始)
void deleteAtPosition(LinkedList *L, int position) {
if (position < 0 || position >= L->length || L->head == NULL) {
printf("删除位置不合法或链表为空!\n");
return;
}
// 如果删除头节点，复用deleteAtHead逻辑
if (position == 0) {
deleteAtHead(L);
return;
}
// 1. 找到要删除节点的前一个节点
Node *current = L->head;
for (int i = 0; i < position - 1; i++) {
current = current->next;
}
// 2. current->next 就是要删除的节点
Node *nodeToDelete = current->next;
// 3. 将前一个节点的next指向要删除节点的下一个节点
current->next = nodeToDelete->next;
// 4. 释放要删除节点的内存
free(nodeToDelete);
L->length--;
}
5 查找节点
根据值查找节点，如果找到则返回节点的指针，否则返回 NULL。
// 根据值查找节点，如果找到返回节点指针，否则返回NULL
Node* findNode(LinkedList *L, int data) {
Node *current = L->head;
while (current != NULL) {
if (current->data == data) {
return current; // 找到，返回节点指针
}
current = current->next;
}
return NULL; // 未找到
}
6 打印链表
遍历链表并打印每个节点的数据。
// 打印链表中的所有节点
void printList(LinkedList *L) {
if (L->head == NULL) {
printf("链表为空，\n");
return;
}
printf("链表内容 (长度: %d): [ ", L->length);
Node *current = L->head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("]\n");
}
完整示例代码
下面是一个完整的 main 函数,演示了如何使用上述所有操作。
int main() {
LinkedList myList;
initList(&myList);
// 测试插入
printf("--- 测试插入操作 ---\n");
insertAtHead(&myList, 10);
insertAtHead(&myList, 20);
insertAtTail(&myList, 30);
insertAtTail(&myList, 40);
insertAtPosition(&myList, 25, 2); // 在位置2插入25
printList(&myList); // 预期输出: [ 20 10 25 30 40 ]
// 测试删除
printf("\n--- 测试删除操作 ---\n");
deleteAtHead(&myList);
deleteAtTail(&myList);
deleteAtPosition(&myList, 1); // 删除位置1的节点
printList(&myList); // 预期输出: [ 10 30 ]
// 测试查找
printf("\n--- 测试查找操作 ---\n");
Node *foundNode = findNode(&myList, 30);
if (foundNode != NULL) {
printf("找到节点，其值为: %d\n", foundNode->data);
} else {
printf("未找到值为30的节点，\n");
}
foundNode = findNode(&myList, 100);
if (foundNode != NULL) {
printf("找到节点，其值为: %d\n", foundNode->data);
} else {
printf("未找到值为100的节点，\n");
}
// 测试销毁
printf("\n--- 测试销毁操作 ---\n");
destroyList(&myList);
printList(&myList); // 预期输出: 链表为空。
return 0;
}
- 优点：单链表的插入和删除操作非常高效（时间复杂度为 O(1)，前提是已知插入/删除位置的前驱节点）,无需像数组那样移动大量元素。
- 缺点：访问元素需要从头指针开始遍历，时间复杂度为 O(n),并且每个节点都需要额外的空间来存储指针。
掌握单链表的基本操作是学习更复杂数据结构（如栈、队列、树、图）的基础,希望这份详细的讲解能帮助你彻底理解！
