双链表详解(后附完整源代码)

谁践踏了优雅 2024-03-26 21:00 84阅读 0赞

#### 双链表 ####

*  一.基本框架
 *  二.初始化哨兵位
 *  三.尾插
 *  四.打印链表
 *  五.尾删
 *  六.头插和头删
 *  七.任意位置插入和删除
 *  八.销毁
 *  九.源代码

## 一.基本框架 ##

![在这里插入图片描述][772c2dbb9c634e729fa4d727d260c9d9.png]

> **首先创立三个源文件分模块编写。**

![在这里插入图片描述][8a07defea95b4af296042ad930d943ea.png]

> **初始化定义一些结构。**

![在这里插入图片描述][0f5af5d7201b4b41ac97b5f9d346e8f0.png]

> **定义新节点，每次需要一个新节点时就从该函数调用。**

## 二.初始化哨兵位 ##

![在这里插入图片描述][eb19fa7109124aa08074ece13e88a2b6.png]

![在这里插入图片描述][54e15b787e134ff0bebf7b8b3812f623.png]

> **这里设立哨兵位的好处就是可以快速找尾并且不用判断链表是否为空（在单链表中我们需要判断，如果链表为空就给头节点赋值，但在这因为存在哨兵位故链表不可能为空）**

![在这里插入图片描述][6daf8754a1e540fc81af90a0923df24d.png]

![在这里插入图片描述][4e2a8d65d4d34bb79474f79ba3db611c.png]

![在这里插入图片描述][f413a224111c4fa5b4382cd22856b4d5.png]

## 三.尾插 ##

![在这里插入图片描述][05bcdbf8175841bc94e29386271a0c6a.png]

![在这里插入图片描述][49342d2a2d884b82ae82babd75c6d238.png]

![在这里插入图片描述][d99f838c89ae4b78bbdd602f2f63e88a.png]

## 四.打印链表 ##

![在这里插入图片描述][46035959da004a669883c0ad26cf4668.png]

![在这里插入图片描述][3660bbacdd434d08b0baa94534095901.png]

![在这里插入图片描述][a8dc7f273d1045afbb275f595f0dc9e6.png]

## 五.尾删 ##

> **在删除之前需要判断一下链表是否为空，所以增加一个函数。**

![在这里插入图片描述][10d6b262850f4030b9b0dbe58d45b20a.png]

> **接着进行尾删**

![在这里插入图片描述][63faeb1ee5ef4520b6c35196d243aae0.png]

![在这里插入图片描述][6a9e40ac3b1f4f26894a4b7984be29e6.png]

![在这里插入图片描述][d20bf1be2b0248239403467bd4076e4f.png]

![在这里插入图片描述][3d826c184f4646ac9a1f47caf84ca77c.png]

## 六.头插和头删 ##

![在这里插入图片描述][17c9ea769cda49ec96b78a8641119441.png]

![在这里插入图片描述][22f5c2ca86ee416aafe9eb8c89426516.png]

## 七.任意位置插入和删除 ##

> **在此之前需要找到该节点**

![在这里插入图片描述][e72e89e4f32441e1afa148bce307d968.png]

![在这里插入图片描述][080677fabed740468ee393a30aab0a10.png]

![在这里插入图片描述][70d426feb4b8443c93923cf9b41585ad.png]

> **开始插入和删除**

![在这里插入图片描述][21b225b7e0af47b7a33d65159bccb20d.png]

![在这里插入图片描述][647d2d0149e746dba8ed4952b67246f5.png]

![在这里插入图片描述][34401f52d05840048f2fa03d9f8b3d2d.png]

## 八.销毁 ##

![在这里插入图片描述][7cfee7bd41184141b3537f610cb6192e.png]

![在这里插入图片描述][1cbf4169bcf74982b4266bfc074d18c9.png]

![在这里插入图片描述][331a16e77a2f43688f39e1eb4c89ca83.png]

> **这里链表就完成了，其实可以看出后面我们写的任意位置插入和删除，那么头插头删尾插尾删，其实是可以直接用这两个函数替代的，具体怎么替代就不再写啦，原理很简单，大家可以试试看。**

## 九.源代码 ##

*test.c*

#include<stdio.h>
    #include"List.h"
    
    //测试链表
    void Test()
    {
        
    	LTNode* plist = LTInit();//初始化哨兵位
    	
    	LTPushBack(plist, 1);//插入一个值为1的节点
    	LTPushBack(plist, 2);//插入一个值为2的节点
    	LTPushBack(plist, 3);//插入一个值为3的节点
    	LTPushBack(plist, 4);//插入一个值为4的节点
    
    	LTPopBack(plist);//删除最后一个
    
    	LTPushFront(plist, 5);//头插5
    	LTPushFront(plist, 4);//头插4
    	LTPushFront(plist, 3);//头插3
    
    	LTPopFront(plist);//头删
    	
    	LTNode*pos=TLFind(plist,5);//找到值为5的节点
    
    	LTInsert(pos,6);//在pos前面位置插入6
    	LTErase(pos);//删除pos节点
    
    	LTPrint(plist);//打印链表
    
    	Dstroy(plist);//销毁链表
    
    }
    
    int main()
    {
        
    	Test();
    	return 0;
    }

*list.h*

#include<stdio.h>
    #include<assert.h>
    #include<stdlib.h>
    #include<stdbool.h>
    #define LTDataType int
    
    typedef struct ListNode
    {
        
    	struct ListNode* pre;
    	struct ListNode* next;
    	LTDataType data;//这里依然设定特定结构为了防止以后储存不同类型数据需要不断更改类型
    }LTNode;
    
    LTNode* LTInit();//初始化哨兵位
    
    void LTPushBack(LTNode* phead, LTDataType x);//尾插
    
    void LTPrint(LTNode*phead);//打印链表
    
    void LTPopBack(LTNode* phead);//尾删
    
    void LTPushFront(LTNode* phead, LTDataType x);//头插
    
    void LTPopFront(LTNode* phead);//头删
    
    LTNode* TLFind(LTNode* pos, LTDataType x);//找到改节点
    
    void LTInsert(LTNode* pos, LTDataType x);//在第pos个节点前插入
    
    void LTErase(LTNode* pos);//删除pos节点
    
    void Dstroy(LTNode* phead);//销毁链表

*list.c*

#include"List.h"
    
    
    LTNode* BuyList(LTDataType x)
    {
        
    	LTNode* node = (LTNode*)malloc(sizeof (LTNode));//开辟一个新节点
    	if (node == NULL)
    	{
        
    		perror("malloc fail");
    		return NULL;
    	}//防止开辟失败
    	node->next = NULL;
    	node->pre = NULL;
    	node->data = x;//初始化节点
    
    	return node;
    }//开辟节点
    
    
    LTNode* LTInit()//初始化
    {
        
    	LTNode*phead = BuyList(-1);//初始化值为-1
    	phead->next = phead;
    	phead->pre = phead;//初始化两个指针都指向自己
    	return phead;
    }
    
    
    bool LTEmpty(LTNode* phead)//判断是否为空
    {
        
    	assert(phead);
    	
    	return phead->next == phead;
    }
    
    
    
    void LTPushBack(LTNode* phead, LTDataType x)//尾插
    {
        
    	assert(phead);//断言头节点是否为空
    
    	LTNode* newnode = BuyList(x);//创建一个值为x的节点
    	LTNode*tail = phead->pre;//让尾部指向之前最后一个节点
    
    	tail->next = newnode;//之前最后一个节点指向现在最后一个节点
    	newnode->next = phead;//新节点的下一个节点指向哨兵位
    	newnode->pre = tail;//新节点的前一个指向之前最后一个节点
    	phead->pre = newnode;//哨兵位的前一个节点指向新节点
    
    }
    
    
    void LTPrint(LTNode*phead)//打印链表
    {
        
    	assert(phead);
    
    	LTNode* cur = phead->next;
    	while (cur != phead)
    	{
        
    		printf("%d<=>", cur->data);
    		cur = cur->next;
    	}
    	printf("\n");
    }
    
    
    void LTPopBack(LTNode* phead)//尾删
    {
        
    	assert(phead);
    	assert(!LTEmpty(phead));//断言链表是否为空
    
    	LTNode* tail = phead->pre;//找到尾
    	LTNode* tailPre = tail->pre;//找到尾部前一个
    
    	phead->pre = tailPre;//让哨兵位前一个指向倒数第二个节点
    	tailPre->next = phead;//倒数第二个指向哨兵位
    	free(tail);//释放尾节点
    	tail = NULL;
    }
    
    
    
    void LTPushFront(LTNode* phead, LTDataType x)//头插
    {
        
    	LTNode* newnode = BuyList(x);//创建一个值为x的节点
    
    	newnode->next = phead->next;
    	newnode->pre = phead;//改变新节点的两个指针
    	phead->next->pre = newnode;//改变原第一个节点的前一个指针
    	phead->next = newnode;//改变哨兵位的后一个指针
    
    }
    
    void LTPopFront(LTNode* phead)//头删
    {
        
    	assert(phead);
    	assert(!LTEmpty(phead));//判断释放为空
    
    	LTNode* tail = phead->next;
    	LTNode* tailP = tail->next;
    
    	phead->next = tailP;
    	tailP->pre = phead;
    	free(tail);
    	tail = NULL;
    }
    
    LTNode* TLFind(LTNode* pos, LTDataType x)//找到改节点
    {
        
    	assert(pos);
    
    	LTNode* cur = pos->next;
    	while (cur!= NULL)
    	{
        
    		if (cur->data == x)
    		{
        
    			return cur;
    		}
    		cur = cur->next;
    	}
    
    	return NULL;
    }
    
    
    void LTInsert(LTNode* pos, LTDataType x)//在第pos个节点前插入
    {
        
    	assert(pos);
    
    	LTNode* newnode = BuyList(x);
    	newnode->next = pos;
    	newnode->pre = pos->pre;//改变新节点的两个指针
    	pos->pre->next = newnode;//改变原pos前节点的后指针
    	pos->pre = newnode;//改变Pos的前指针
    
    }
    
    void LTErase(LTNode* pos)//删除pos节点
    {
        
    	assert(pos);
    
    	LTNode* p = pos->pre;
    	LTNode* n = pos->next;
    
    	p->next = n;
    	n->pre = p;
    	free(pos);
    }
    
    
    void Dstroy(LTNode* phead)//销毁链表
    {
        
    	assert(phead);
    
    	LTNode* cur = phead->next;
    	while (cur != phead)
    	{
        
    		LTNode* n = cur->next;
    		free(cur);
    		cur = n;
    	}
    	free(phead);
    }

[772c2dbb9c634e729fa4d727d260c9d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2659d6b2142f4ccd97ceeeb1ab8c2254.png
[8a07defea95b4af296042ad930d943ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9ae06488f6e747f88eacdff427383d3c.png
[0f5af5d7201b4b41ac97b5f9d346e8f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4d5b582519af4367890ae426b5602462.png
[eb19fa7109124aa08074ece13e88a2b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b0e20931060846c78fe53c96fbd9b440.png
[54e15b787e134ff0bebf7b8b3812f623.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/55a069515d8f478283f39e53398d4d1d.png
[6daf8754a1e540fc81af90a0923df24d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7a0f349fb44d4f61a61a751ba82495a5.png
[4e2a8d65d4d34bb79474f79ba3db611c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8fe090a948ef4349b9e8c430e8b718af.png
[f413a224111c4fa5b4382cd22856b4d5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/16ee06b7c9f448a4b26d122fbfe815c7.png
[05bcdbf8175841bc94e29386271a0c6a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/fe04a59d696a432dbe0ae58f5288370b.png
[49342d2a2d884b82ae82babd75c6d238.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/07c7fc3b786f42b7834ad77200935a6d.png
[d99f838c89ae4b78bbdd602f2f63e88a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4c8c92e795d94fee9b931d3ad545a97c.png
[46035959da004a669883c0ad26cf4668.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c669de371eec48c6a8b720f224d5d54c.png
[3660bbacdd434d08b0baa94534095901.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/09a337e9a260440ab3715b9c49681a9b.png
[a8dc7f273d1045afbb275f595f0dc9e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7e5dabf7e5854bf1a7686affa1b99b3a.png
[10d6b262850f4030b9b0dbe58d45b20a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9e9526cc965846adb93e532da33b030a.png
[63faeb1ee5ef4520b6c35196d243aae0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f07f478d72104df6b59a2a3ac61619b4.png
[6a9e40ac3b1f4f26894a4b7984be29e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2589541b7083431db1c0ea9993d69d3c.png
[d20bf1be2b0248239403467bd4076e4f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a889d11405824acca5b6891151bf7f25.png
[3d826c184f4646ac9a1f47caf84ca77c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b5b59cd4c64e4b8ba3847282115a0ca6.png
[17c9ea769cda49ec96b78a8641119441.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c55ed7154f05444d9686350fa3edddba.png
[22f5c2ca86ee416aafe9eb8c89426516.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ab070915169041f5997f504425fc47f3.png
[e72e89e4f32441e1afa148bce307d968.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4767d7a47a6443939011c32b1a1d6741.png
[080677fabed740468ee393a30aab0a10.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/19ed579ad5ea4f5cb307e0c065e14a4d.png
[70d426feb4b8443c93923cf9b41585ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/6904c7b18c434c609c9c525b3df49a75.png
[21b225b7e0af47b7a33d65159bccb20d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3c59d0e741144b918318d06066e58d15.png
[647d2d0149e746dba8ed4952b67246f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/42bbb02826814817b6a395dd8c9ad343.png
[34401f52d05840048f2fa03d9f8b3d2d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/29b0cd1ceb194117bcb43e5463db4640.png
[7cfee7bd41184141b3537f610cb6192e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8db2d6fd6310477e830c2261f16d1bde.png
[1cbf4169bcf74982b4266bfc074d18c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a9e79d00723740c9a223b59619ee5fc3.png
[331a16e77a2f43688f39e1eb4c89ca83.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/42318225b7c241ffae1156c5367429d8.png