一、引言
单链表是数据结构中最基础也是最重要的一种链式数据结构。它在内存中的元素不需要连续存储，每个元素通过指针连接到下一个元素。这种结构使得插入和删除操作变得高效，适合动态数据的管理。本文将全面介绍单链表的基本概念、结构、常见操作，并提供完整的实现代码。
二、单链表的基本概念与结构
1. 概念
单链表是一种链式存储的数据结构，由一系列节点（Node）组成。每个节点包含两部分：
- 数据域（Data）：存储实际的数据。
- 指针域（Next）：指向链表中的下一个节点。
链表的特点是节点不需要在内存中连续存储，这允许链表在插入和删除操作时具有更高的灵活性和效率。
2. 基本结构
单链表的基本结构如下：
typedef int DataType; typedef struct ListNode { DataType data;//数据域 struct ListNode* next;//指针域,指向下一个节点 }LN;
三、单链表优缺点
1.优点
动态内存管理：节点在内存中不需要连续存储，支持动态扩展。
高效插入和删除：在链表中插入或删除节点的操作时间复杂度为 O(1)O(1)O(1)。
适应不同数据大小：可以处理动态变化的数据大小，无需事先定义固定大小。
2.缺点
额外空间开销：每个节点需要额外存储一个指针，增加内存开销。
访问效率低：访问链表中的第 nnn 个元素需要逐一遍历，时间复杂度为 O(n)O(n)O(n)。
不支持反向遍历：只能从头到尾遍历，不能直接反向遍历。
四、单链表的常见操作
单链表的操作包括节点的插入、删除、查找以及链表的遍历。下面是这些操作的详细说明及代码实现。
1.创建节点
//创建节点 LN* CreateNode(DataType x) { LN* newnode = (LN*)malloc(sizeof(LN)); if (newnode==NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
2.初始化(创建头节点)
// 初始化链表（创建头节点） LN*ListInit() { LN* headnode = CreateNode(0); // 头节点值为0（或任何不使用的值） return headnode; }
3.头插
//头插 void ListPushHead(LN* phead, DataType x) { assert(phead); LN* newnode = CreateNode(x); newnode->next = phead->next; phead->next = newnode; }
4.尾插
//尾插 void ListPushBack(LN* phead, DataType x) { assert(phead); LN* newnode = CreateNode(x); LN* pcur = phead; while (pcur->next != NULL) { pcur = pcur->next; } pcur->next = newnode; }
5.头删
//头删 void ListDelHead(LN* phead) { assert(phead); if (phead->next == NULL) { printf("链表为空，无法进行删除操作！\n"); return; } LN* temp = phead->next; phead->next = phead->next->next; free(temp); }
6.尾删
//尾删 void ListDelBack(LN* phead) { assert(phead); if (phead->next == NULL) { printf("链表为空，无法进行删除操作！\n"); return; } LN* pcur = phead; while (pcur->next->next != NULL) { pcur = pcur->next; } free(pcur->next); pcur->next = NULL; }
7.查找
//查找 LN* ListFind(LN* phead, DataType x) { assert(phead); LN* pcur = phead->next; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; }
8.指定位置前插入
//指定位置前插入 void ListInsertFront(LN* phead, LN*pos,DataType x) { assert(phead); LN* pcur = phead; if (pos==NULL) { printf("插入位置非法\n"); return; } while (pcur->next != pos) { pcur=pcur->next; } LN* newnode = CreateNode(x); newnode->next = pos; pcur->next = newnode; }
9.指定位置后插入
//指定位置后插入 void ListInsertBack(LN* pos, DataType x) { if (pos == NULL) { printf("插入位置非法\n"); return; } LN* newnode = CreateNode(x); newnode->next = pos->next; pos->next = newnode; }
10.指定位置删除
//指定位置节点删除 void ListErase(LN*phead,LN*pos) { assert(phead); if (pos == NULL) { printf("删除位置非法\n"); return; } if (phead->next == NULL) { printf("链表为空，无法进行删除操作！\n"); return; } LN* pcur = phead; while (pcur->next!=pos) { pcur = pcur->next; } pcur->next = pos->next; free(pos); }
11.打印
//打印链表 void ListPrint(LN* phead) { assert(phead); LN* pcur = phead->next;//注意这里带头节点，所以打印数值从头节点的下一位打印 while (pcur) { printf("%d->", pcur->data); pcur = pcur->next; } printf("NULL\n"); }
12.销毁
//销毁 void ListDestory(LN** pphead) { LN* pcur=*pphead; LN* temp = NULL; while (pcur) { temp = pcur->next; // 保存下一个节点的指针 free(pcur);// 释放当前节点的内存 pcur = temp;// 移动到下一个节点 } // 将头指针置为 NULL，确保链表被正确销毁 *pphead= NULL; }
五、完整代码
1.List.h
该部分放顺序表结构定义、函数的声明
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int DataType; typedef struct ListNode { DataType data;//数据域 struct ListNode* next;//指针域,指向下一个节点 }LN; //创建节点 LN* CreateNode(DataType x); // 初始化链表（创建头节点） LN* ListInit(); //尾插 void ListPushBack(LN* phead, DataType x); //头插 void ListPushHead(LN* phead, DataType x); //尾删 void ListDelBack(LN* phead); //头删 void ListDelHead(LN* phead); //打印链表 void ListPrint(LN *phead); //查找 LN* ListFind(LN* phead, DataType x); //指定位置前插入 void ListInsertFront(LN* phead, LN*pos,DataType x); //指定位置后插入 void ListInsertBack(LN* pos, DataType x); //指定位置节点删除 void ListErase(LN*phead,LN*pos); //销毁 void ListDestory(LN**pphead);
2.List.c
该部分是函数功能的实现
#define _CRT_SECURE_NO_WARNINGS #include"List.h" //创建节点 LN* CreateNode(DataType x) { LN* newnode = (LN*)malloc(sizeof(LN)); if (newnode==NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } // 初始化链表（创建头节点） LN*ListInit() { LN* headnode = CreateNode(0); // 头节点值为0（或任何不使用的值） return headnode; } //尾插 void ListPushBack(LN* phead, DataType x) { assert(phead); LN* newnode = CreateNode(x); LN* pcur = phead; while (pcur->next != NULL) { pcur = pcur->next; } pcur->next = newnode; } //头插 void ListPushHead(LN* phead, DataType x) { assert(phead); LN* newnode = CreateNode(x); newnode->next = phead->next; phead->next = newnode; } //尾删 void ListDelBack(LN* phead) { assert(phead); if (phead->next == NULL) { printf("链表为空，无法进行删除操作！\n"); return; } LN* pcur = phead; while (pcur->next->next != NULL) { pcur = pcur->next; } free(pcur->next); pcur->next = NULL; } //头删 void ListDelHead(LN* phead) { assert(phead); if (phead->next == NULL) { printf("链表为空，无法进行删除操作！\n"); return; } LN* temp = phead->next; phead->next = phead->next->next; free(temp); } //打印链表 void ListPrint(LN* phead) { assert(phead); LN* pcur = phead->next;//注意这里带头节点，所以打印数值从头节点的下一位打印 while (pcur) { printf("%d->", pcur->data); pcur = pcur->next; } printf("NULL\n"); } //查找 LN* ListFind(LN* phead, DataType x) { assert(phead); LN* pcur = phead->next; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; } //指定位置前插入 void ListInsertFront(LN* phead, LN*pos,DataType x) { assert(phead); LN* pcur = phead; if (pos==NULL) { printf("插入位置非法\n"); return; } while (pcur->next != pos) { pcur=pcur->next; } LN* newnode = CreateNode(x); newnode->next = pos; pcur->next = newnode; } //指定位置后插入 void ListInsertBack(LN* pos, DataType x) { if (pos == NULL) { printf("插入位置非法\n"); return; } LN* newnode = CreateNode(x); newnode->next = pos->next; pos->next = newnode; } //指定位置节点删除 void ListErase(LN*phead,LN*pos) { assert(phead); if (pos == NULL) { printf("删除位置非法\n"); return; } if (phead->next == NULL) { printf("链表为空，无法进行删除操作！\n"); return; } LN* pcur = phead; while (pcur->next!=pos) { pcur = pcur->next; } pcur->next = pos->next; free(pos); } //销毁 void ListDestory(LN** pphead) { LN* pcur=*pphead; LN* temp = NULL; while (pcur) { temp = pcur->next; // 保存下一个节点的指针 free(pcur);// 释放当前节点的内存 pcur = temp;// 移动到下一个节点 } // 将头指针置为 NULL，确保链表被正确销毁 *pphead= NULL; }
3.test.c
该部分用来测试我们写的函数(函数的调用)
#define _CRT_SECURE_NO_WARNINGS #include"List.h" void test1() { LN* phead = ListInit();//创建头节点，头指针指向头节点 ListPushHead(phead, 1); ListPushHead(phead, 2); ListPushHead(phead, 3); //ListDelBack(phead); //ListDelHead(phead); //测试查找 LN * find = ListFind(phead,2); /*if (find == NULL) { printf("没有找到!\n"); } else { printf("找到了!\n"); }*/ //ListInsertFront(phead, find, 99); //ListInsertBack(find,88); //ListErase(phead, find); ListPrint(phead); //ListDestory(&phead); } int main() { test1(); return 0; }
六、总结
单链表是一种简单而强大的数据结构，适用于动态数据存储和管理。通过本文，我们介绍了单链表的基本概念、常见操作及其实现。掌握单链表的操作可以帮助我们更好地解决实际编程问题，特别是在需要频繁插入和删除操作的场景中。
希望这篇博客对你理解和使用单链表有所帮助。如果你有任何问题或想进一步了解更多高级用法，请随时留言讨论！
