网站导航
> 技术文档 > 数据结构之单链表

数据结构之单链表

网友: 技术文档 2025-07-30 10:38:38

欢迎拜访：雾里看山-CSDN博客
本篇主题：数据结构之单链表
发布时间：2025.6.29
隶属专栏：数据结构

在这里插入图片描述

目录

  • 链表
    • 链表的概念和结构
    • 链表的分类
  • 单链表
    • 单链表的优缺点分析
      • 优点：
      • 缺点：
    • 单链表的使用场景
    • 单链表的实现
      • 创建结构体
      • 基本功能 接口实现
      • 增删查改接口实现
        • 增
          • 头插
          • 尾插
          • pos位置之前插入
          • pos位置之后插入
        • 删
          • 头删
          • 尾删
          • 删除pos位置
          • 删除pos后一个位置
        • 查
        • 改
      • 整体代码显示

链表

链表的概念和结构

链表（Linked List）是一种线性数据结构，由一系列节点（Node）组成，每个节点包含两部分：

  1. 数据域：存储实际的数据元素
  2. 指针域：存储指向下一个节点的地址（在双向链表中还包含指向前一个节点的地址）

数据结构之单链表
链表中的所有节点，都是单独在堆区开辟出来的，相邻两个节点之间，可能连续也可能不连续。

核心特征：链表中的元素在内存中不是连续存储的，而是通过指针相互链接形成链式结构。这种设计使链表具有动态分配内存的能力，可以根据需要灵活地增加或删除元素。

链表的分类

实际中链表可能有以下几种情况，组合起来有8种。

  1. 单向或者双向
    数据结构之单链表

  2. 带头或者不带头
    数据结构之单链表

  3. 循环或者非循环

数据结构之单链表
在那么多种链表结构中，使用最多的有两种结构，分别是：
无头单向非循环列表：
数据结构之单链表
带头双向循环链表：
数据结构之单链表

  1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

单链表

单链表的优缺点分析

优点：

  • 动态内存分配：不需要预先分配固定空间，可以动态扩展
  • 高效插入删除：在已知位置时插入删除只需O(1)时间
  • 内存利用率高：不需要连续内存空间
  • 灵活性强：可以轻松实现各种复杂链表结构（双向、循环等）

缺点：

  • 访问效率低：不支持随机访问，查找元素需O(n)时间
  • 空间开销大：每个节点需要额外空间存储指针
  • 缓存不友好：非连续存储可能导致缓存命中率低
  • 操作复杂度高：需要处理指针操作，容易出错

单链表的使用场景

  • 需要频繁插入删除元素的应用
  • 元素数量变化较大或无法预估的情况
  • 实现栈、队列等动态数据结构
  • 需要节省连续内存的嵌入式系统
  • 实现哈希表的链地址法

单链表的实现

创建结构体

typedef int SLTDataType;// 定义存储的数据类型typedef struct SListNode{SLTDataType data; // 保存数据struct SListNode* next;// 保存下一个节点的指针}SLTNode;

基本功能 接口实现

打印

通过打印函数方便我们查看链表中的数据

void SLTPrint(SLTNode* phead){SLTNode* cur = phead;while (cur){printf(\"%d->\", cur->data);cur = cur->next;}printf(\"NULL\\n\");}
创建节点

通过malloc函数动态开辟空间创建节点。

SLTNode* BuySListNode(SLTDataType x){SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror(\"malloc fail\\n\");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;}

增删查改接口实现

增
头插

头插要更改头结点，这个时候就需要传入二级指针。

void SLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead);SLTNode* phead = *pphead;SLTNode *newhead = BuySListNode(x);newhead->next = phead;*pphead = newhead;}
尾插

当链表为空时，也需要更改头结点来完成插入操作，同样需要传入二级指针。

void SLTPushBack(SLTNode** pphead, SLTDataType x){assert(pphead);SLTNode *phead = *pphead;if (phead == NULL)//链表为空{phead = BuySListNode(x);*pphead = phead;}else//链表不为空{SLTNode *cur = phead;while (cur->next){cur = cur->next;}SLTNode* newhead = BuySListNode(x);cur->next = newhead;}}
pos位置之前插入

更符合我们熟悉的插入逻辑，但是需要遍历链表找到pos位置的前一个数据，时间复杂度较高。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead);assert(pos);SLTNode* phead = *pphead;if (pos == phead){SLTNode* newhead = BuySListNode(x);newhead->next = phead;*pphead = newhead;}else{SLTNode* cur = phead;while (cur->next != pos && cur->next){cur = cur->next;}SLTNode* last = cur->next;SLTNode* newnode = BuySListNode(x);newnode->next = last;cur->next = newnode;}}
pos位置之后插入

虽然不符合我们常见的插入逻辑，但是不需要遍历链表，直接插入即可，时间复杂度仅为O(1)。

void SLTInsertAfter(SLTNode* pos, SLTDataType x){assert(pos);SLTNode* last = pos->next;SLTNode* newnode = BuySListNode(x);newnode->next = last;pos->next = newnode;}
删
头删

要考虑链表是否为空，头删还会更改头结点，所以需要传入二级指针。

void SLTPopFront(SLTNode** pphead){assert(pphead);// 链表为空assert(*pphead);SLTNode *phead = *pphead;SLTNode* newhead = phead->next;free(phead);*pphead = newhead;}
尾删

尾删同样考虑链表为空的情况，并且当链表中只有一个数据时，同样会更改头结点，所以也要传入二级指针。

void SLTPopBack(SLTNode** pphead){assert(pphead);// 链表为空assert(*pphead);SLTNode* cur = *pphead;if (cur->next == NULL){free(cur);*pphead = NULL;return;}while (cur->next->next){cur = cur->next;}SLTNode* node = cur->next;free(node);cur->next = NULL;}
删除pos位置

符合常见的删除逻辑，但是需要遍历数组找到pos位置之前的节点，如果pos是头结点，还需要更改头结点。

void SLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead);assert(pos);SLTNode* phead = *pphead;if (pos == phead){*pphead = phead->next;free(phead);}else{SLTNode* cur = phead;while (cur->next != pos){cur = cur->next;}SLTNode* last = pos->next;cur->next = last;free(pos);}}
删除pos后一个位置

操作简单，也不需要遍历链表，而且不会更改头结点，不需要传入二级指针。

void SLTEraseAfter(SLTNode* pos){assert(pos);assert(pos->next);SLTNode* next = pos->next;SLTNode* nnext = next->next;pos->next = nnext;free(next);next = NULL;}
查

遍历链表，找到后返回节点指针，没找到则返回空指针。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x){SLTNode* cur = phead;while (cur){if (cur->data == x)return cur;elsecur = cur->next;}return NULL;}
改

找到节点以后本可以直接改数据，但是为了统一接口，所以封装成了函数。

void STLModify(SLTNode* pos, SLTDataType x){assert(pos);pos->data = x;}

整体代码显示

整体代码包含三个文件：SList.h、SList.c和main.c
SList.h：

#pragma once#include #include #include typedef int SLTDataType;typedef struct SListNode{SLTDataType data;struct SListNode* next;}SLTNode;void SLTPrint(SLTNode* phead);SLTNode* BuySListNode(SLTDataType x);void SLTPushBack(SLTNode** pphead, SLTDataType x);void SLTPushFront(SLTNode** pphead, SLTDataType x);void SLTPopBack(SLTNode** pphead);void SLTPopFront(SLTNode** pphead);SLTNode* SLTFind(SLTNode* phead, SLTDataType x);// 在pos之前插入xvoid SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);// 在pos以后插入xvoid SLTInsertAfter(SLTNode* pos, SLTDataType x);// 删除pos位置void SLTErase(SLTNode** pphead, SLTNode* pos);// 删除pos的后一个位置void SLTEraseAfter(SLTNode* pos);// 修改pos位置的数据void STLModify(SLTNode* pos, SLTDataType x);

SList.c：

#include \"SList.h\"void SLTPrint(SLTNode* phead){SLTNode* cur = phead;while (cur){printf(\"%d->\", cur->data);cur = cur->next;}printf(\"NULL\\n\");}SLTNode* BuySListNode(SLTDataType x){SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror(\"malloc fail\\n\");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;}void SLTPushBack(SLTNode** pphead, SLTDataType x){assert(pphead);SLTNode *phead = *pphead;if (phead == NULL)//链表为空{phead = BuySListNode(x);*pphead = phead;}else//链表不为空{SLTNode *cur = phead;while (cur->next){cur = cur->next;}SLTNode* newhead = BuySListNode(x);cur->next = newhead;}}void SLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead);SLTNode* phead = *pphead;SLTNode *newhead = BuySListNode(x);newhead->next = phead;*pphead = newhead;}void SLTPopBack(SLTNode** pphead){assert(pphead);// 链表为空assert(*pphead);SLTNode* cur = *pphead;if (cur->next == NULL){free(cur);*pphead = NULL;return;}while (cur->next->next){cur = cur->next;}SLTNode* node = cur->next;free(node);cur->next = NULL;}void SLTPopFront(SLTNode** pphead){assert(pphead);// 链表为空assert(*pphead);SLTNode *phead = *pphead;SLTNode* newhead = phead->next;free(phead);*pphead = newhead;}SLTNode* SLTFind(SLTNode* phead, SLTDataType x){SLTNode* cur = phead;while (cur){if (cur->data == x)return cur;elsecur = cur->next;}return NULL;}// 在pos之前插入xvoid SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead);assert(pos);SLTNode* phead = *pphead;if (pos == phead){SLTNode* newhead = BuySListNode(x);newhead->next = phead;*pphead = newhead;}else{SLTNode* cur = phead;while (cur->next != pos && cur->next){cur = cur->next;}SLTNode* last = cur->next;SLTNode* newnode = BuySListNode(x);newnode->next = last;cur->next = newnode;}}// 在pos以后插入xvoid SLTInsertAfter(SLTNode* pos, SLTDataType x){assert(pos);SLTNode* last = pos->next;SLTNode* newnode = BuySListNode(x);newnode->next = last;pos->next = newnode;}// 删除pos位置void SLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead);assert(pos);SLTNode* phead = *pphead;if (pos == phead){*pphead = phead->next;free(phead);}else{SLTNode* cur = phead;while (cur->next != pos){cur = cur->next;}SLTNode* last = pos->next;cur->next = last;free(pos);}}// 删除pos的后一个位置void SLTEraseAfter(SLTNode* pos){assert(pos);assert(pos->next);SLTNode* next = pos->next;SLTNode* nnext = next->next;pos->next = nnext;free(next);next = NULL;}// 修改pos位置的数据void STLModify(SLTNode* pos, SLTDataType x){assert(pos);pos->data = x;}

main.c：

#include \"SList.h\"void TestSList1(){int n;printf(\"请输入链表的长度：\");scanf(\"%d\", &n);printf(\"\\n请依次输入每个节点的值:\");SLTNode* plist = NULL;for (int i = 0; i < n; i++){int val;scanf(\"%d\", &val);SLTNode* newnode = BuySListNode(val);// 头插newnode->next = plist;plist = newnode;}SLTPrint(plist);SLTPushBack(&plist, 10000);SLTPrint(plist);}void TestSList2(){SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);SLTPushFront(&plist, 10);SLTPushFront(&plist, 20);SLTPushFront(&plist, 30);SLTPushFront(&plist, 40);SLTPrint(plist);}void TestSList3(){SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist); //SLTPopBack(&plist); //SLTPrint(plist);}void TestSList4(){SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);//SLTPopFront(&plist);SLTPrint(plist);}void TestSList5(){SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);SLTNode* pos = SLTFind(plist, 4);if (pos){pos->data *= 10;}SLTPrint(plist);int x;scanf(\"%d\", &x);pos = SLTFind(plist, x);if (pos){SLTInsert(&plist, pos, x * 10);}SLTPrint(plist);}void TestSList6(){SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);int x;scanf(\"%d\", &x);SLTNode* pos = SLTFind(plist, x);if (pos){SLTInsertAfter(pos, x * 10);}SLTPrint(plist);}void TestSList7(){SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPrint(plist);int x;scanf(\"%d\", &x);SLTNode* pos = SLTFind(plist, x);if (pos){//SLTErase(&plist, pos);SLTEraseAfter(pos);pos = NULL;}SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);}int main(){TestSList7();return 0;}

⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！

网络标签：

相关问题