主页 > 开源代码 >

数据结构：单链表（SingleLinkedList）及其实现

开源代码
2025-09-05 05:18:01

什么是单链表？

单链表是一种最简单的链表结构，它就像一列火车，每节车厢（节点）都通过挂钩（指针）连接到下一节车厢。单链表中的每个节点都包含两部分：

数据：存储实际的数据（比如数字、字符串等）。

指针：指向下一个节点的地址。

单链表的特点是：数据在内存中不是连续存储的，而是通过指针连接起来的。正因为如此，单链表可以动态地增加或删除节点，而不需要像数组那样移动大量数据。

单链表的原理

单链表的每个节点都是一个独立的内存块，节点之间通过指针连接。单链表的开头有一个头指针（head），指向第一个节点；最后一个节点的指针指向 NULL，表示链表的结束。

单链表的优点：

动态扩容：可以随时增加或删除节点，不需要预先分配固定大小的内存。

插入和删除快：只需要修改指针，不需要移动大量数据。

单链表的缺点：

访问速度慢：不能像数组那样通过下标直接访问元素，需要从头开始遍历。

内存开销大：每个节点都需要额外的空间存储指针。

单链表的基本操作

单链表的基本操作包括：增、删、查、改。下面我们用大白话解释这些操作。

增加节点：

在链表头部插入节点：新节点的指针指向原来的头节点，然后更新头指针。

在链表中间插入节点：找到插入位置，修改前后节点的指针。

在链表尾部插入节点：找到最后一个节点，让它的指针指向新节点。

删除节点：

删除头节点：直接让头指针指向第二个节点。

删除中间节点：找到要删除的节点，让前一个节点的指针指向后一个节点。

删除尾节点：找到倒数第二个节点，让它的指针指向 NULL。

查找节点：

从头节点开始，依次遍历每个节点，直到找到目标节点。

修改节点：

找到目标节点后，直接修改它的数据。

C 语言实现单链表

下面是一个简单的单链表实现代码，包含初始化、插入、删除、查找和打印功能。

#include <stdio.h> #include <stdlib.h> // 定义链表节点结构体 typedef struct Node { int data; // 数据 struct Node *next; // 指向下一个节点的指针 } Node; // 初始化链表（创建一个空链表） Node* InitList() { return NULL; // 头指针初始化为 NULL } // 在链表头部插入节点 Node* InsertHead(Node *head, int value) { Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点 newNode->data = value; // 设置新节点的数据 newNode->next = head; // 新节点指向原来的头节点 return newNode; // 返回新的头节点 } // 在链表尾部插入节点 Node* InsertTail(Node *head, int value) { Node *newNode = (Node*)malloc(sizeof(Node)); // 创建新节点 newNode->data = value; // 设置新节点的数据 newNode->next = NULL; // 新节点指向 NULL if (head == NULL) { return newNode; // 如果链表为空，新节点就是头节点 } Node *current = head; while (current->next != NULL) { // 找到最后一个节点 current = current->next; } current->next = newNode; // 最后一个节点指向新节点 return head; } // 删除链表中指定值的节点 Node* DeleteNode(Node *head, int value) { if (head == NULL) { return NULL; // 链表为空，直接返回 } // 如果要删除的是头节点 if (head->data == value) { Node *temp = head->next; // 保存下一个节点 free(head); // 释放当前头节点 return temp; // 返回新的头节点 } Node *current = head; while (current->next != NULL && current->next->data != value) { current = current->next; // 找到要删除节点的前一个节点 } if (current->next != NULL) { Node *temp = current->next; // 保存要删除的节点 current->next = current->next->next; // 跳过要删除的节点 free(temp); // 释放要删除的节点 } return head; } // 查找链表中指定值的节点 Node* FindNode(Node *head, int value) { Node *current = head; while (current != NULL) { if (current->data == value) { return current; // 找到目标节点 } current = current->next; } return NULL; // 未找到目标节点 } // 打印链表 void PrintList(Node *head) { Node *current = head; printf("链表内容："); while (current != NULL) { printf("%d -> ", current->data); current = current->next; } printf("NULL\n"); } int main() { Node *head = InitList(); // 初始化链表 // 插入节点 head = InsertHead(head, 10); // 在头部插入 10 head = InsertHead(head, 20); // 在头部插入 20 head = InsertTail(head, 30); // 在尾部插入 30 PrintList(head); // 打印链表 // 删除节点 head = DeleteNode(head, 20); // 删除值为 20 的节点 PrintList(head); // 打印链表 // 查找节点 Node *target = FindNode(head, 30); if (target != NULL) { printf("找到节点：%d\n", target->data); } else { printf("未找到节点\n"); } return 0; } 单链表的使用场景

数据量不确定：比如存储用户输入的数据，数据量可能随时增加或减少。

频繁插入和删除：比如实现一个任务队列，需要频繁添加或移除任务。

内存灵活管理：比如实现内存池或缓存系统。

图片介绍

下面是一个单链表的示意图：

头指针 -> [10] -> [20] -> [30] -> NULL

每个方框代表一个节点，包含数据和指针。

指针指向下一个节点，最后一个节点的指针指向 NULL。

单链表的应用实例：任务管理系统

单链表在实际开发中有很多应用场景，比如实现一个简单的任务管理系统。我们可以用单链表来存储任务列表，每个任务包含一个任务名和优先级。用户可以添加新任务、删除已完成任务、查找特定任务，以及打印所有任务。

1. 需求分析

添加任务：用户可以添加一个新任务，指定任务名和优先级。

删除任务：用户可以根据任务名删除一个任务。

查找任务：用户可以根据任务名查找任务，并查看其优先级。

打印任务：打印所有任务，按优先级排序。

2. 代码实现

以下是基于单链表实现的任务管理系统的完整代码：

#include <stdio.h> #include <stdlib.h> #include <string.h> // 定义任务结构体 typedef struct Task { char name[50]; // 任务名 int priority; // 优先级 struct Task *next; // 指向下一个任务的指针 } Task; // 初始化任务列表（创建一个空链表） Task* InitTaskList() { return NULL; // 头指针初始化为 NULL } // 添加任务（按优先级插入） Task* AddTask(Task *head, char *name, int priority) { Task *newTask = (Task*)malloc(sizeof(Task)); // 创建新任务 strcpy(newTask->name, name); // 设置任务名 newTask->priority = priority; // 设置优先级 newTask->next = NULL; // 新任务指向 NULL // 如果链表为空，或者新任务的优先级最高 if (head == NULL || newTask->priority > head->priority) { newTask->next = head; // 新任务指向原来的头节点 return newTask; // 返回新的头节点 } // 找到合适的位置插入新任务 Task *current = head; while (current->next != NULL && current->next->priority >= newTask->priority) { current = current->next; } newTask->next = current->next; // 新任务指向下一个节点 current->next = newTask; // 当前节点指向新任务 return head; } // 删除任务 Task* DeleteTask(Task *head, char *name) { if (head == NULL) { return NULL; // 链表为空，直接返回 } // 如果要删除的是头节点 if (strcmp(head->name, name) == 0) { Task *temp = head->next; // 保存下一个节点 free(head); // 释放当前头节点 return temp; // 返回新的头节点 } Task *current = head; while (current->next != NULL && strcmp(current->next->name, name) != 0) { current = current->next; // 找到要删除节点的前一个节点 } if (current->next != NULL) { Task *temp = current->next; // 保存要删除的节点 current->next = current->next->next; // 跳过要删除的节点 free(temp); // 释放要删除的节点 } return head; } // 查找任务 Task* FindTask(Task *head, char *name) { Task *current = head; while (current != NULL) { if (strcmp(current->name, name) == 0) { return current; // 找到目标任务 } current = current->next; } return NULL; // 未找到目标任务 } // 打印任务列表 void PrintTasks(Task *head) { Task *current = head; printf("任务列表：\n"); while (current != NULL) { printf("任务名：%s，优先级：%d\n", current->name, current->priority); current = current->next; } } int main() { Task *taskList = InitTaskList(); // 初始化任务列表 // 添加任务 taskList = AddTask(taskList, "写作业", 3); taskList = AddTask(taskList, "买菜", 1); taskList = AddTask(taskList, "开会", 5); PrintTasks(taskList); // 打印任务列表 // 删除任务 taskList = DeleteTask(taskList, "买菜"); PrintTasks(taskList); // 打印任务列表 // 查找任务 Task *target = FindTask(taskList, "开会"); if (target != NULL) { printf("找到任务：%s，优先级：%d\n", target->name, target->priority); } else { printf("未找到任务\n"); } return 0; }

3. 代码说明

任务结构体：每个任务包含任务名、优先级和指向下一个任务的指针。

添加任务：按优先级插入任务，优先级高的任务排在前面。

删除任务：根据任务名删除任务。

查找任务：根据任务名查找任务。

打印任务：按优先级从高到低打印所有任务。

4. 运行结果

假设我们按照以下步骤操作：

添加任务：“写作业”（优先级 3）、“买菜”（优先级 1）、“开会”（优先级 5）。

删除任务：“买菜”。

查找任务：“开会”。

程序输出如下：