数据结构——单链表

embedded/2024/12/22 9:47:23/

目录

引言

什么是链表

链表的分类

1.单向链表和双向链表

(1)单向链表

(2)双向链表

2.带头结点链表和不带头结点链表

(1)带头结点链表

(2)不带头结点链表

3.循环链表和不循环链表

(1)循环链表

(2)不循环链表

单链表的功能

单链表的定义

单链表功能实现

1.打印单链表数据

(1)代码实现

(2)复杂度分析

2.单链表头插

(1)创建节点

(2)头插代码

(3)复杂度分析

3.单链表头删

(1)代码实现

(2)复杂度分析

4.单链表尾插

(1)代码实现

(2)复杂度分析

5.单链表尾删

(1)代码实现

(2)复杂度分析

6.单链表数据查找

(1)代码实现

(2)复杂度分析

7.单链表数据修改

(1)代码实现

(2)复杂度分析

8.指定位置数据插入

(1)指定位置之前插入数据

(2)指定位置之后插入数据

(3)复杂度分析

9.指定位置数据删除

(1)删除pos节点

(2)删除pos之后的节点

(3)复杂度分析

10.销毁单链表

(1)代码实现

(2)复杂度分析

完整代码

结束语

引言

在我的上一篇文章中 数据结构——顺序表 我们学习了数据结构中的顺序表，我们知道了顺序表的空间是连续存储的，这与数组非常类似。但是当我们同时当插入数据时可能存在移动数据与扩容的情况，这大大增加我们的时间与空间成本。因此我们接下来学习新的数据结构——链表。

球球点赞收藏关注！！！

什么是链表

链表（Linked List）是一种常见的数据结构，它通过一系列的节点（Node）来存储数据元素。这些节点之间通过指针或引用相互连接，从而形成一个链状结构。每个节点通常包含两部分：一部分用于存储数据元素，另一部分用于存储指向下一个节点的指针或引用。

链表的分类

链表可以分为几种不同的类型，其中最常见的有八种，它们大致可以分为三类：

1.单向链表和双向链表

(1)单向链表

在单向链表中，每个节点只包含一个指向下一个节点的指针。

如下图所示：

(2)双向链表

在双向链表中，每个节点除了包含数据元素外，还包含两个指针：一个指向下一个节点（称为后继节点），另一个指向前一个节点（称为前驱节点）。

如图所示：

2.带头结点链表和不带头结点链表

(1)带头结点链表

带头结点的单链表是在链表的第一个数据元素结点之前附加一个结点，称为头结点。

如图所示：

(2)不带头结点链表

非带头结点的单链表不包含头结点，链表的第一个结点即为数据元素结点，头指针直接指向链表的第一个数据元素结点。

如图所示：

3.循环链表和不循环链表

(1)循环链表

循环链表是一种特殊类型的链表，其中最后一个节点指向第一个节点，形成一个循环。这种结构使得链表在逻辑上成为一个环状结构。

如图所示：

(2)不循环链表

如图所示：

本篇博客将详细讲解一下无头单向非循环链表。

无头单向非循环链表是一种链表结构，其特点是没有头结点，且链表中的节点单向连接，不形成循环。这种链表结构相对简单，一般不会单独用来存储数据，而是作为其他数据结构的子结构，如哈希桶、图的邻接表等。

单链表的功能

单链表一般要实现如下几个功能：

  1. 打印单链表中的数据。
  2. 对单链表进行头插(开头插入数据)。
  3. 对单链表进行头删(开头删除数据)。
  4. 对单链表进行尾插(末尾插入数据)。
  5. 对单链表进行尾删(末尾删除数据)。
  6. 对单链表进行查找数据。
  7. 对单链表数据进行修改。
  8. 对指定位置的数据删除。
  9. 对指定位置的数据插入。
  10. 销毁单链表。

单链表的定义

单链表的结点定义方式与我们以往定义的方式都不同，它是一个结构体中包含两个成员。一个是存储数值，一个存放下一个结点的地址。

//定义节点的结构
//数据+指向下一节点的指针
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

单链表功能实现

1.打印单链表数据

遍历链表并打印每个节点的数据来展示链表的内容，直到遇到链表的末尾。

(1)代码实现

void SLTPrint(SLTNode* phead)
{// 初始化一个指针pcur，指向链表的头节点SLTNode* pcur = phead;// 使用while循环遍历链表，直到pcur指向NULL（即链表末尾）  while (pcur != NULL){printf("%d->", pcur->data);pcur = pcur->next;}// 循环结束后，打印"NULL"以明确表示链表的结束 printf("NULL\n");
}

(2)复杂度分析

时间复杂度：因为要遍历整个链表，因此时间复杂度为O(n)。

空间复杂度：因为打印链表不需要格外的空间，因此空间复杂度为O(1)。

2.单链表头插

(1)创建节点

由于单链表每次插入都需要插入一个节点，因此我们可以写一个创建节点的函数方便后续调用。

代码实现如下：

//申请内存
SLTNode* SLTCreateNode(SLTDataType x)
{// 为新的单链表节点分配内存空间 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");exit(1);}// 初始化新节点的数据字段  newnode->data = x;newnode->next = NULL;return newnode;
}

(2)头插代码

在这里我们需要注意的是：单链表传参需要二级指针。因为头插数据需要改变一级指针plist的指向，而形参的改变无法影响实参，所以需要二级指针才能改变一级指针plist的指向。

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{// 断言确保传入的头节点指针的地址非空，避免解引用空指针assert(pphead);// 创建一个新的节点，并初始化其数据为x  SLTNode* newnode = SLTCreateNode(x);// 将新节点的next指针指向当前头节点newnode->next = *pphead;// 更新头节点指针，使其指向新节点*pphead = newnode;
}

(3)复杂度分析

时间复杂度：由于不需要额外时间的消耗，因此时间复杂度为O(1)。

空间复杂度：由于每次固定创造一个节点，因此空间复杂度为O(1)。

3.单链表头删

头删与头插类似，都可能需要改变plist的指向，所以也需要二级指针。并且也需要防止链表为空的情况发生。

(1)代码实现

//头删
void SLTPopFront(SLTNode** pphead)
{// 链表不能为空，确保pphead不是空指针// 且*pphead（即头节点）也不是空指针assert(pphead && *pphead);// 保存头节点的下一个节点的地址，// 以便删除头节点后能够更新头指针SLTNode* next = (*pphead)->next;free(*pphead);// 更新头节点*pphead = next;
}

(2)复杂度分析

时间复杂度：由于不需要额外时间的消耗，因此时间复杂度为O(1)。

空间复杂度：由于不需要额外空间的消耗，因此空间复杂度为O(1)。

4.单链表尾插

(1)代码实现

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//	*pphead就是指向第一个节点的指针//	处理空链表SLTNode* newnode = SLTCreateNode(x);// 判断链表是否为空if (*pphead == NULL){// 如果链表为空，则新节点即为头节点*pphead = newnode;}else{// 找尾SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}// 循环结束，ptail指向尾节点ptail->next = newnode;}
}

(2)复杂度分析

时间复杂度：由于需要遍历整个链表，因此时间复杂度为O(N)。

空间复杂度：由于每次固定创造一个节点，因此空间复杂度为O(1)。

5.单链表尾删

与单链表尾插类似，当链表只有一个头结点时需要将plist置为空，所以也需要二级指针。并且也需要防止链表为空的情况发生。

(1)代码实现

//尾删
void SLTPopBack(SLTNode** pphead)
{// 链表不能为空，确保pphead不是空指针，// 且*pphead（即头节点）也不是空指针assert(pphead && *pphead);// 如果链表只有一个节点if ((*pphead)->next == NULL)	//->优先级高于*{free(*pphead);*pphead = NULL;}else{// 链表有多个节点SLTNode* prev = *pphead;SLTNode* ptail = *pphead;// 遍历链表直到找到尾节点while (ptail->next){prev = ptail;			// 更新prev节点ptail = ptail->next;	// 移动到下一个节点}free(ptail);	// 释放尾节点prev->next = NULL;}
}

(2)复杂度分析

时间复杂度：由于需要遍历整个链表，因此时间复杂度为O(N)。

空间复杂度：由于不需要额外空间的消耗，因此空间复杂度为O(1)。

6.单链表数据查找

如果找到了就返回这个节点的地址，否则就返回空指针NULL。

(1)代码实现

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;// 遍历链表，直到当前节点为空（即到达链表末尾）while (pcur){if (pcur->data == x){return pcur;	// 找到当前节点的指针}pcur = pcur->next;}return NULL;
}

(2)复杂度分析

时间复杂度：由于可能要完整遍历整个链表，因此时间复杂度为O(n)。

空间复杂度：由于不需要额外空间的消耗，因此空间复杂度为O(1)。

7.单链表数据修改

(1)代码实现

//数据修改 
void SLTModifity(SLTNode* pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos); SLTNode* cur = pphead;while (cur){if (cur == pos){cur->data = x;break;}cur = cur->next;}
}

(2)复杂度分析

时间复杂度：由于可能要完整遍历整个链表，因此时间复杂度为O(n)。

空间复杂度：由于不需要额外空间的消耗，因此空间复杂度为O(1)。

8.指定位置数据插入

(1)指定位置之前插入数据

代码如下：

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTCreateNode(x);// 如果插入位置是链表的第一个位置（即pos等于头节点）// 则调用头插函数if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}

(2)指定位置之后插入数据

代码如下：

//在指定位置之后插入数据
void SLTnsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTCreateNode(x);// 将新节点的next指针指向pos的下一个节点newnode->next = pos->next;// 将pos的next指针指向新节点，完成插入操作pos->next = newnode;
}

(3)复杂度分析

时间复杂度：最坏的情况都是需要完整遍历整个链表，因此时间复杂度为O(n)。

空间复杂度：由于每次固定创造一个节点，因此空间复杂度为O(1)。

9.指定位置数据删除

(1)删除pos节点

代码如下：

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pphead && *pphead);// 如果删除的节点是头节点if (pos == *pphead){SLTPopFront(pphead);	// 头删}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}// 将prev的next指针指向pos的下一个节点// 从而绕过pos节点，实现删除prev->next = pos->next;free(pos);pos = NULL;}
}

(2)删除pos之后的节点

代码如下：

//删除pos之后的节点
void SLTraseAfter(SLTNode* pos)
{assert(pos && pos->next);// 创建一个临时指针del，指向pos之后的节点，即要删除的节点SLTNode* del = pos->next;// 将pos的next指针指向del的下一个节点，从而绕过del节点，实现删除pos->next = del->next;free(del);del = NULL;
}

(3)复杂度分析

时间复杂度：最坏的情况都是需要完整遍历整个链表，因此时间复杂度为O(n)。

空间复杂度：空间复杂度均为O(1)。

10.销毁单链表

销毁链表需要依次遍历释放节点。

(1)代码实现

//销毁链表
void SListDesTory(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){// 保存当前节点的下一个节点的指针// 以便在释放当前节点后能够继续遍历SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

(2)复杂度分析

时间复杂度：由于需要遍历整个链表，因此时间复杂度为O(n)。

空间复杂度：由于不需要额外空间的消耗，因此空间复杂度为O(1)。

完整代码

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义节点的结构
//数据+指向下一节点的指针
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//打印
void SLTPrint(SLTNode* phead);
//尾插
void SLTPushBack(SLTNode** phead, SLTDataType);
//头插
void SLTPushFront(SLTNode** phead, SLTDataType);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在制定位置之后插入数据
void SLTnsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTraseAfter(SLTNode* pos);//销毁链表
void SListDesTory(SLTNode** pphead);//数据修改
void SLTModifity(SLTNode* pphead, SLTNode* pos, SLTDataType x);

SList.c

#include"SList.h"void SLTPrint(SLTNode* phead)
{// 初始化一个指针pcur，指向链表的头节点SLTNode* pcur = phead;// 使用while循环遍历链表，直到pcur指向NULL（即链表末尾）  while (pcur != NULL){printf("%d->", pcur->data);pcur = pcur->next;}// 循环结束后，打印"NULL"以明确表示链表的结束 printf("NULL\n");
}//申请内存
SLTNode* SLTCreateNode(SLTDataType x)
{// 为新的单链表节点分配内存空间 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");exit(1);}// 初始化新节点的数据字段  newnode->data = x;newnode->next = NULL;return newnode;
}//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//	*pphead就是指向第一个节点的指针//	处理空链表SLTNode* newnode = SLTCreateNode(x);// 判断链表是否为空if (*pphead == NULL){// 如果链表为空，则新节点即为头节点*pphead = newnode;}else{// 找尾SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}// 循环结束，ptail指向尾节点ptail->next = newnode;}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{// 断言确保传入的头节点指针的地址非空，避免解引用空指针assert(pphead);// 创建一个新的节点，并初始化其数据为x  SLTNode* newnode = SLTCreateNode(x);// 将新节点的next指针指向当前头节点newnode->next = *pphead;// 更新头节点指针，使其指向新节点*pphead = newnode;
}//尾删
void SLTPopBack(SLTNode** pphead)
{// 链表不能为空，确保pphead不是空指针，// 且*pphead（即头节点）也不是空指针assert(pphead && *pphead);// 如果链表只有一个节点if ((*pphead)->next == NULL)	//->优先级高于*{free(*pphead);*pphead = NULL;}else{// 链表有多个节点SLTNode* prev = *pphead;SLTNode* ptail = *pphead;// 遍历链表直到找到尾节点while (ptail->next){prev = ptail;			// 更新prev节点ptail = ptail->next;	// 移动到下一个节点}free(ptail);	// 释放尾节点prev->next = NULL;}
}//头删
void SLTPopFront(SLTNode** pphead)
{// 链表不能为空，确保pphead不是空指针// 且*pphead（即头节点）也不是空指针assert(pphead && *pphead);// 保存头节点的下一个节点的地址，// 以便删除头节点后能够更新头指针SLTNode* next = (*pphead)->next;free(*pphead);// 更新头节点*pphead = next;
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;// 遍历链表，直到当前节点为空（即到达链表末尾）while (pcur){if (pcur->data == x){return pcur;	// 找到当前节点的指针}pcur = pcur->next;}return NULL;
}//数据修改 
void SLTModifity(SLTNode* pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos); SLTNode* cur = pphead;while (cur){if (cur == pos){cur->data = x;break;}cur = cur->next;}
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTCreateNode(x);// 如果插入位置是链表的第一个位置（即pos等于头节点）// 则调用头插函数if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}//在指定位置之后插入数据
void SLTnsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTCreateNode(x);// 将新节点的next指针指向pos的下一个节点newnode->next = pos->next;// 将pos的next指针指向新节点，完成插入操作pos->next = newnode;
}//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pphead && *pphead);// 如果删除的节点是头节点if (pos == *pphead){SLTPopFront(pphead);	// 头删}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}// 将prev的next指针指向pos的下一个节点// 从而绕过pos节点，实现删除prev->next = pos->next;free(pos);pos = NULL;}
}//删除pos之后的节点
void SLTraseAfter(SLTNode* pos)
{assert(pos && pos->next);//创建临时变量delSLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}//销毁链表
void SListDesTory(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){// 保存当前节点的下一个节点的指针// 以便在释放当前节点后能够继续遍历SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

结束语

OK了家人们，感谢看到最后的友友们！！！

求点赞收藏关注！！！


http://www.ppmy.cn/embedded/97634.html

相关文章

【密码学】密钥管理：②密钥分配

【密码学】密钥管理：②密钥分配

一、密钥分配的定义 密钥分配是密钥管理生命周期中最重要的部分&#xff0c;密钥分配方案研究的是密码系统中密钥的分发和传送问题。从本质上讲&#xff0c;密钥分配为通信双方建立用于信息加密、解密签名等操作的密钥&#xff0c;以实现保密通信或认证签名等。 &#xff08;1…
阅读更多...
django之BaseSerializer

django之BaseSerializer

BaseSerializer 是 Django REST framework (DRF) 中的一个核心类&#xff0c;用于将复杂的数据类型&#xff08;如查询集和模型实例&#xff09;转换为 Python 数据类型&#xff0c;以便于渲染成 JSON、XML 或其他内容类型。BaseSerializer 是所有序列化器的基类&#xff0c;提…
阅读更多...
小米便签——ui包详细解读

小米便签——ui包详细解读

目录 ui:用户界面类 1 AlarmAlertActivity 2 AlarmInitReceiver 3 AlarmReceiver 4 DateTimePicker 5 DateTimePickerDialog 6 DropdownMenu 7 FoldersListAdapter 8 NoteEditActivity 9 NoteltemData 10 NotesListActivity 11 NoteEditText 12 NotesListAdapter …
阅读更多...
Mysql 中的Undo日志

Mysql 中的Undo日志

在 MySQL 的 InnoDB 存储引擎中&#xff0c;Undo Log 是用于实现数据库事务的回滚功能的一种日志。Undo Log 记录了对数据的修改&#xff0c;以便在事务出现问题时可以恢复到之前的状态。下面将介绍 Undo Log 的结构和样本数据。 Undo Log 的基本概念 目的: Undo Log 的主要目…
阅读更多...
一文掌握 Web 测试：功能、界面、兼容与安全的综合测试指南！

一文掌握 Web 测试：功能、界面、兼容与安全的综合测试指南！

随着Web技术的不断演进&#xff0c;测试除了对应用的功能性、界面美观性、跨平台兼容性的基本要求外、安全性和性能的要求也逐步增高。因此&#xff0c;全面、系统的测试思维和策略成为了保证Web应用高质量的关键因素。本篇文章将从功能测试、界面测试、兼容性测试和安全测试四…
阅读更多...
StarSpider：一款高效的网络爬虫框架解析与实战

StarSpider：一款高效的网络爬虫框架解析与实战

文章目录 引言官网链接StarSpider 原理简介基础使用1. 添加依赖2. 编写PageProcessor3. 启动爬虫 高级使用1. 分布式抓取2. 自定义下载器3. 深度定制 优点结语 引言 在大数据时代&#xff0c;数据成为了推动业务增长和创新的关键。网络爬虫作为数据获取的重要手段之一&#xf…
阅读更多...
集合的知识点

集合的知识点

一、集合的简介 1.1 什么是集合 集合(Collection)&#xff0c;也是一个数据容器&#xff0c;类似于数组&#xff0c;但是和数组是不一样的。集合是一个可变的容器&#xff0c;可以随时向集合集合中添加元素&#xff0c;也可以随时从集合中删除元素。另外&#xff0c;集合还提…
阅读更多...
Oracle（63）什么是临时表（Temporary Table）？

Oracle（63）什么是临时表（Temporary Table）？

临时表&#xff08;Temporary Table&#xff09;是一种特殊类型的表&#xff0c;用于存储临时数据&#xff0c;这些数据在会话期间或事务期间是短暂的。临时表在不同的数据库系统中都有实现&#xff0c;但功能和特性可能有所不同。临时表通常用于存储中间计算结果、临时数据处理…
阅读更多...
最新文章

Copyright @ 2022~2023