数据结构之手撕链表（讲解➕源代码）

2023-10-16 21:45
文章标签 讲解 链表 数据结构 源代码 之手

本文主要是介绍数据结构之手撕链表（讲解➕源代码），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0.引言

我们在学习过顺序表之后，会发现两点不是很优秀的操作：
1.顺序表的头插和中间的插入：
        非常麻烦，需要不断的覆盖数据。
2.动态开辟空间：
        a.一般动态开辟的空间都是以2倍的形式开辟，当我们已经开辟了100个空间，并且存满了，此时我们还需要存放5个数据，那么就又需要开辟200个空间了，我们存放5个数据之后，还剩余了195个空间没有放数据，这也就导致了空间的浪费。
        b. 而我们开辟新空间，拷贝数据，释放旧空间还会有一定的消耗。

注意⚠️⚠️⚠️：
        我们在申请空间的时候必须要主动给它释放掉，因为申请空间的时候，是在堆上申请的，这段空间不会随着程序的结束而自然释放掉，所以要在我们程序结束之前，主动释放掉这段空间。

那有没有一种结构会很简便呢？答案肯定是有的，就是我们本次要讲解的链表。


1.链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的 。也就是说链表的物理结构不连续，但逻辑结构连续。

我们通常定义一个结构体来表示链表的节点，结构体内部要包括节点的值和指向下一个节点的指针。

链表开始的节点称作：头节点，通常用head表示；

链表末尾的节点称作：尾结点，通常用tail表示；

其余节点称作：中间节点。

2.链表的逻辑模型

如图：在逻辑模型，可以看出它们是一个接着一个的，在逻辑上连续。

3.链表的物理模型

如图：在物理模型中，我们看到每个节点的地址都不是连续的，但是通过指针链接起来了。

 4.链表的分类

4.1 单向链表

        

4.2 双向链表

4.3 带头单向链表（带哨兵位）

4.4带头双向链表（带哨兵位）

4.5循环单链表

4.6循环双向链表

4.7带头循环单链表

4.8带头循环双向链表

5. 单链表的实现（接口实现代码）

5.1单链表的定义

typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

5.3单链表的销毁

void SLT_Destroy(SLTNode*phead)//销毁
{while (phead != NULL){SLTNode *over = phead->next;free(phead);phead = over;}
}

5.4单链表的动态申请一个节点空间

SLTNode* BuySListNode(SLTDataType x) //创造新节点
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

5.5单链表的头插头删

void SLTPushFront(SLTNode** pphead, SLTDataType x) //头插
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}void SLTPopFront(SLTNode** pphead) //头删
{// 空assert(*pphead);// 非空SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}

5.6单链表的尾插尾删

void SLTPushBack(SLTNode** pphead, SLTDataType x) //尾插
{SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){// 改变的结构体的指针，所以要用二级指针*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}// 改变的结构体，用结构体的指针即可tail->next = newnode;}
}void SLTPopBack(SLTNode** pphead) //尾删
{// 1、空assert(*pphead);// 2、一个节点// 3、一个以上节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

5.7单链表的在pos位置之前的插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//pos之前插入
{assert(pphead);assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}

5.8单链表的在pos位置之后的插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x)//在pos之后插入
{assert(pos);SLTNode* newnode = BuySListNode(x);pos->next = newnode;newnode->next = pos->next;
}

5.9单链表的删除pos位置的节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);//pos = NULL;}
}

5.10单链表的删除pos位置之后的节点

void SLTEraseAfter(SLTNode* pos)
{assert(pos);// 检查pos是否是尾节点assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;
}

5.11单链表的查找

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

6.带头双向循环链表的实现（接口实现代码）

6.1带头双向循环链表的定义

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev; //前驱LTDataType data;struct ListNode* next; //后继
}ListNode;

6.2带头双向循环链表的初始化

ListNode* ListInit() //初始化链表
{ListNode *head = (ListNode*) malloc(sizeof (ListNode));if(head ==  NULL){perror("初始化开辟空间失败");exit(-1);}head->data = -1;head->prev = head;head->next = head;return head;
}

6.3带头双向循环链表的销毁

void ListDestory(ListNode* pHead) //销毁
{int len = ListSize(pHead) + 1;while (len--)ListPopFront(pHead);
}

6.4带头双向循环链表的打印

void ListPrint(ListNode* phead) //打印
{assert(phead);ListNode *phead_next = phead->next;printf("phead <-> ");while(phead_next != phead){printf("%d <-> ",phead_next->data);phead_next = phead_next->next;}printf("phead\n");
}

6.5带头双向链表的增加节点

ListNode* BuyListNode(LTDataType x) //增加节点
{ListNode *newnode = (ListNode*) malloc(sizeof (ListNode));if(newnode == NULL){perror("增加节点开辟空间失败");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

6.6带头双向循环链表的在pos之前插入

void ListInsert(ListNode* pos,LTDataType x)//在pos位置之前插入
{assert(pos);ListNode *newnode = BuyListNode(x);ListNode *pos_prev = pos->prev;pos_prev->next = newnode;newnode->prev = pos_prev;newnode->next = pos;pos->prev = newnode;
}

6.7带头双向循环链表删除pos位置

void ListErase(ListNode* pos)//删除pos位置的节点
{assert(pos);ListNode *pos_next = pos->next;ListNode *pos_prev = pos->prev;pos_prev->next = pos_next;pos_next->prev = pos_prev;free(pos);
}

6.8带头双向循环链表的尾插尾删

void ListPushBack(ListNode* phead,LTDataType x)//尾插
{assert(phead);ListInsert(phead,x);
}void ListPopBack(ListNode* phead)//尾删
{assert(phead);ListErase(phead->prev);
}

6.9带头双向循环链表的头插头删

void ListPushFront(ListNode* phead,LTDataType x)//头插
{assert(phead);ListInsert(phead->next,x);
}void ListPopFront(ListNode* phead)//头删
{assert(phead);ListErase(phead->next);
}

6.10带头双向循环链表的长度求解

int ListSize(ListNode* phead)//求链表的长度
{assert(phead);int len = 0;ListNode *phead_next = phead->next;while(phead != phead_next){len++;phead_next = phead_next->next;}return len;
}

6.11带头双向循环链表的寻找某一节点

ListNode*ListFind(ListNode* phead, LTDataType num)//寻找某一个节点
{assert(phead);ListNode *find = phead->next;while(find != phead){if(find->data == num){return find;}find = find->next;}return NULL;
}

7.顺序表和链表的区别

不同点顺序表链表

存储空间上 

物理上一定连续逻辑一定连续，物理不一定

任意位置插入或者删除

元素

需要覆盖数据通过指针就能找到

插入 

动态顺序表需要扩容没有容量概念，需要一个给一个

缓存利用率

高低

这篇关于数据结构之手撕链表（讲解➕源代码）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/220979。

相关文章

C++ vector的常见用法超详细讲解

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》：本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve
阅读更多...
Java调用C++动态库超详细步骤讲解(附源码)

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,：本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步：动态库生成（vs2017+qt5.12.10）第二步：Java调用C++
阅读更多...
Python基础文件操作方法超详细讲解(详解版)

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,：本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
C# WinForms存储过程操作数据库的实例讲解

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》：本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程（增删改）3. 查询数据三、事务处
阅读更多...
C++快速排序超详细讲解

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快
阅读更多...
Java集合中的List超详细讲解

Java集合中的List超详细讲解

《Java集合中的List超详细讲解》本文详细介绍了Java集合框架中的List接口,包括其在集合中的位置、继承体系、常用操作和代码示例,以及不同实现类（如ArrayList、LinkedList和V... 目录一，List的继承体系二，List的常用操作及代码示例1，创建List实例2，增加元素3，访问元
阅读更多...
Python使用国内镜像加速pip安装的方法讲解

Python使用国内镜像加速pip安装的方法讲解

《Python使用国内镜像加速pip安装的方法讲解》在Python开发中,pip是一个非常重要的工具,用于安装和管理Python的第三方库,然而,在国内使用pip安装依赖时,往往会因为网络问题而导致速... 目录一、pip 工具简介1. 什么是 pip？2. 什么是 -i 参数？二、国内镜像源的选择三、如何
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
Python itertools中accumulate函数用法及使用运用详细讲解

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》：本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言：1.2定义：1.3衍生用法：1.3Leetcode的实际运用:总结 1.1前言：本文将详
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2