1. Toy模板网首页
  2. > Toy博客

手撕双链表

9月前 作者：დ旧言~ 分类：Toy博客 阅读(39) 违法举报

这篇具有很好参考价值的文章主要介绍了手撕双链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

> 作者简介：დ旧言~，目前大一，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。
> 望小伙伴们点赞👍收藏✨加关注哟💕💕 

手撕双链表,数据结构,数据结构

 🌟前言       

        前面我们已经学习了顺序表和单链表，顺序表可以存储动态的数据，但是一旦元素过少，而又要开辟空间，这样就造成空间的浪费，而单链表以节点为单位存储，不支持随机访问，只能从头到尾遍历访问，为了解决上面两个问题，人们发现了双链表，把一个一个元素以链子的形式存储，可以存储相互的地址，那双链表如何实现呢，今天咱们就实现一下--《双链表》。

手撕双链表,数据结构,数据结构

手撕双链表,数据结构,数据结构

🌙主体

咱们从三个方面实现双链表，动态管理，头插头删尾插尾删，增删查改。

手撕双链表,数据结构,数据结构

在程序中为了实现双链表，需要创建头文件List.h ，创建源文件Test.c，List.c。

手撕双链表,数据结构,数据结构

 🌠动态管理

💤初始化动态双链表

既然实现双链表，初始化动态的双链表必不可少，从两个方面实现初始化动态的双链表。

1.首先我们在List.h定义动态的双链表，省得我们再定义节点（双链表）。

//定义数据类型
typedef int LTDataType;
//定义双链表初始化
typedef struct ListNode
{
	//上一个
	struct ListNode* next;
	//下一个
	struct ListNode* prev;
	LTDataType data;
}LTNode;

2.对双链表进行初始化

我们要明白，这里不像单链表一样，形成节点就行，还需要初始化。

💦这里采用malloc开辟空间

💦采用预指令判断空间是否开辟完成（没有开辟空间返回-1）

💦之后就是简单的初始数据

💦记得返回值

//初始化
LTNode* BuyLTNode(LTDataType x)
{
	//开辟空间
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	//判断开辟的空间是否为空
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//初始化
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

//形成双链表
LTNode* LTInit()
{
	//使头为0
	LTNode* phead = BuyLTNode(0);
	//构成循环
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

 💤释放双链表内存 

双链表的内存释放与单链表的内存释放有一定的区别，这里我们分开两类，清理与销毁

清理的代码如下：

//清理
void ListClear(LTNode* phead)
{
	//断言
	assert(phead);
	
	//清理全部数据，保留头结点
	LTNode* cur = phead->next;
	
	//循环销毁
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = NULL;
		cur = next;
	}
}

销毁的代码如下：

//销毁
void ListDestory(LTNode** pphead)
{
	//断言
	assert(*pphead);

	//调用清理（函数）
	ListClear(*pphead);
	
	//释放内存
	free(*pphead);
	*pphead = NULL;
}

🌠头插头删尾插尾删

💤打印元素

 打印元素就太简单了，直接上代码手撕双链表,数据结构,数据结构手撕双链表,数据结构,数据结构

//打印数据
void LTPrint(LTNode* phead)
{
	//断言
	assert(phead);

	printf("phead<=>");
	
	LTNode* cur = phead->next;
	//注意循环的结束的语句
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	
	printf("\n");
}

💤尾插（重点）

有了这个图就对指向的改变就轻轻松松手撕双链表,数据结构,数据结构手撕双链表,数据结构,数据结构

手撕双链表,数据结构,数据结构

//尾插（重点）
void LTPushBack(LTNode* phead, LTDataType x)
{
	//断言
	assert(phead);

	LTNode* tail = phead->prev;
	
	//给添加的元素创建节点
	LTNode* newnode = BuyLTNode(x);

    //新开辟的元素下一个节点指向尾
	newnode->prev = tail;
	//尾的上一个节点指向新的元素
    tail->next = newnode;

    //新元素的上一个节点指向头
	newnode->next = phead;
    //头的下一节点指向新的元素节点
	phead->prev = newnode;

	//本质上与尾插相似 （双向链表在pos的前面进行插入）
	//LTInsert(phead, x);
}

💤尾删（重点）

双链表重在画图，希望小伙伴们能看得懂。手撕双链表,数据结构,数据结构手撕双链表,数据结构,数据结构

手撕双链表,数据结构,数据结构

//尾删
void LTPopBack(LTNode* phead)
{
	//断言
	assert(phead);
	//防止没有头指向没有元素
	assert(phead->next != phead);

	//找到尾
	LTNode* tail = phead->prev;
	//找到尾前面一个元素
	LTNode* tailPrev = tail->prev;
	
	//释放内存
	free(tail);

	//（把尾的上一个元素）的上一个指针 指向头
	tailPrev->next = phead;
	//头的下一个指针指向尾的前一个元素
	phead->prev = tailPrev;

	// 双向链表删除pos位置的结点(本质上与尾删相似)
	//LTErase(phead->prev);
}

 💤头插（重点）

博主在这里采用三种方法，希望大家至少学会一种手撕双链表,数据结构,数据结构手撕双链表,数据结构,数据结构

手撕双链表,数据结构,数据结构

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	//方法一
	//初始化
	//LTNode* newnode = BuyLTNode(x);
	//newnode->next = phead->next;
	//phead->next->prev = newnode;
	//phead->next = newnode;
	//newnode->prev = phead;

	//方法二
	//初始化
	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;

	//方法三
	// 双向链表删除pos位置的结点(本质上就是头插)
	//LTInsert(phead->next, x);
}

 💤头删（重点）

双链表会自带梢兵位（这个到后期博主会讲）

//头删（重点）
void LTPopFront(LTNode* phead)
{
	//断言
	assert(phead);
	//头指向不能为空
	assert(phead->next != phead);

	//找到梢兵位的节点
	LTNode* first = phead->next;
	//找到头后面一个元素
	LTNode* second = first->next;

	//释放内存
	free(first);

	//梢兵位的节点指向头后面一个元素
	phead->next = second;
	//后面一个元素指向梢兵位的节点
	second->prev = phead;

	//双向链表删除pos位置的结点(本质上和头删一样)
	//LTErase(phead->next);
}

  🌠增删查改

 💤统计双链表元素个数

这个函数还是比较简单的，注意循环的停止条件。

//统计双链表元素个数
int LTSize(LTNode* phead)
{
	//断言
	assert(phead);

	int size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}

	return size;
}

 💤双向链表在pos的前面进行插入

这里大家就看图理解就行啦

手撕双链表,数据结构,数据结构

// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
	//断言
	assert(pos);

	LTNode* posPrev = pos->prev;
	//为插入的元素开辟空间
	LTNode* newnode = BuyLTNode(x);

	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

 💤双向链表删除pos位置的结点

这里大家就看图理解就行啦

手撕双链表,数据结构,数据结构

// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{
	//断言
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	//释放内存
	free(pos);

	posPrev->next = posNext;
	posNext->prev = posPrev;
}

🌙代码总结

🌠主函数

//包含文件
#include"List.h"

void TestList1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPrint(plist);

	LTPushFront(plist, 10);
	LTPushBack(plist, 10);

	LTPrint(plist);
}

void TestList2()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPrint(plist);

	LTPopBack(plist);
	//LTPopFront(plist);
	LTPrint(plist);

	//LTPopFront(plist);
	//LTPopFront(plist);
	//LTPopFront(plist);
	//LTPopFront(plist);
	LTPrint(plist);
}

//void TestList3()
//{
//	LTNode* plist = LTInit();
//	LTPushBack(plist, 1);
//	LTPushBack(plist, 2);
//	LTPushBack(plist, 3);
//	LTPushBack(plist, 4);
//	LTPushBack(plist, 5);
//	LTPrint(plist);
//
//	LTPushFront(plist, 10);
//	LTPushFront(plist, 20);
//	LTPushFront(plist, 30);
//	LTPushFront(plist, 40);
//	LTPrint(plist);
//}
//
//void TestList4()
//{
//	LTNode* plist = LTInit();
//	LTPushBack(plist, 1);
//	LTPushBack(plist, 2);
//	LTPushBack(plist, 3);
//	LTPushBack(plist, 4);
//	LTPushBack(plist, 5);
//	LTPrint(plist);
//
//	LTPopFront(plist);
//	LTPrint(plist);
//
//	LTPopBack(plist);
//	LTPrint(plist);
//}

int main()
{
	TestList1();

	return 0;
}

🌠List.h头文件

//包含头文件
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

//定义数据类型
typedef int LTDataType;
//定义双链表初始化
typedef struct ListNode
{
	//上一个
	struct ListNode* next;
	//下一个
	struct ListNode* prev;
	LTDataType data;
}LTNode;

//初始化
LTNode* BuyLTNode(LTDataType x);

//形成双链表
LTNode* LTInit();

//打印数据
void LTPrint(LTNode* phead);

//尾插（重点）
void LTPushBack(LTNode* phead, LTDataType x);
//尾删（重点）
void LTPopBack(LTNode* phead);
//头插（重点）
void LTPushFront(LTNode* phead, LTDataType x);
//头删（重点）
void LTPopFront(LTNode* phead);

//统计双链表元素个数
int LTSize(LTNode* phead);
// 双向链表查找（在双链表中不合适）
LTNode* LTFind(LTNode* phead, LTDataType x);

// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);

//清理
void ListClear(LTNode* phead);
//销毁
void ListDestory(LTNode** pphead);

🌠List.c源文件



//包含文件
#include"List.h"

//初始化
LTNode* BuyLTNode(LTDataType x)
{
	//开辟空间
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	//判断开辟的空间是否为空
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//初始化
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

//形成双链表
LTNode* LTInit()
{
	//使头为0
	LTNode* phead = BuyLTNode(0);
	//构成循环
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

//打印数据
void LTPrint(LTNode* phead)
{
	//断言
	assert(phead);

	printf("phead<=>");
	
	LTNode* cur = phead->next;
	//注意循环的结束的语句
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	
	printf("\n");
}

//尾插（重点）
void LTPushBack(LTNode* phead, LTDataType x)
{
	//断言
	assert(phead);

	LTNode* tail = phead->prev;

	//给添加的元素创建节点
	LTNode* newnode = BuyLTNode(x);

	//新开辟的元素下一个节点指向尾
	newnode->prev = tail;
	//尾的上一个节点指向新的元素
	tail->next = newnode;

	//新元素的上一个节点指向头
	newnode->next = phead;
	//头的下一节点指向新的元素节点
	phead->prev = newnode;

	//本质上与尾插相似 （双向链表在pos的前面进行插入）
	//LTInsert(phead, x);
}

//尾删
void LTPopBack(LTNode* phead)
{
	//断言
	assert(phead);
	//防止没有头指向没有元素
	assert(phead->next != phead);

	//找到尾
	LTNode* tail = phead->prev;
	//找到尾前面一个元素
	LTNode* tailPrev = tail->prev;
	
	//释放内存
	free(tail);

	//（把尾的上一个元素）的上一个指针 指向头
	tailPrev->next = phead;
	//头的下一个指针指向尾的前一个元素
	phead->prev = tailPrev;

	// 双向链表删除pos位置的结点(本质上与尾删相似)
	//LTErase(phead->prev);
}

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	//方法一
	//初始化
	//LTNode* newnode = BuyLTNode(x);
	//newnode->next = phead->next;
	//phead->next->prev = newnode;
	//phead->next = newnode;
	//newnode->prev = phead;

	//方法二
	//初始化
	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;

	//方法三
	// 双向链表删除pos位置的结点(本质上就是头插)
	//LTInsert(phead->next, x);
}

//头删（重点）
void LTPopFront(LTNode* phead)
{
	//断言
	assert(phead);
	//头指向不能为空
	assert(phead->next != phead);

	//找到梢兵位的节点
	LTNode* first = phead->next;
	//找到头后面一个元素
	LTNode* second = first->next;

	//释放内存
	free(first);

	//梢兵位的节点指向头后面一个元素
	phead->next = second;
	//后面一个元素指向梢兵位的节点
	second->prev = phead;

	//双向链表删除pos位置的结点(本质上和头删一样)
	//LTErase(phead->next);
}

//统计双链表元素个数
int LTSize(LTNode* phead)
{
	//断言
	assert(phead);

	int size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}

	return size;
}

// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
	//断言
	assert(pos);

	LTNode* posPrev = pos->prev;
	//为插入的元素开辟空间
	LTNode* newnode = BuyLTNode(x);

	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{
	//断言
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	//释放内存
	free(pos);

	posPrev->next = posNext;
	posNext->prev = posPrev;
}


//清理
void ListClear(LTNode* phead)
{
	//断言
	assert(phead);
	
	//清理全部数据，保留头结点
	LTNode* cur = phead->next;
	
	//循环销毁
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = NULL;
		cur = next;
	}
}

//销毁
void ListDestory(LTNode** pphead)
{
	//断言
	assert(*pphead);

	//调用清理（函数）
	ListClear(*pphead);
	
	//释放内存
	free(*pphead);
	*pphead = NULL;
}

🌟结束语

       今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小说手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。

手撕双链表,数据结构,数据结构文章来源地址https://www.toymoban.com/news/detail-723932.html

到了这里，关于手撕双链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构初阶】双链表

    【数据结构初阶】双链表

    1.1结口实现 1.2申请结点 1.3初始化双链表 1.4打印双链表 1.5尾插 1.6尾删 1.7头插 1.8头删 1.9计算大小 1.10查找 1.11pos位置插入 1.12删除pos位置 1.12删除双链表 List.h List.c test.c 💘不知不觉，【数据结构初阶】双链表 以告一段落。通读全文的你肯定收获满满，让我们继续为数据结构学

    2024年02月05日
    浏览(40)
  • [数据结构初阶]双链表

    [数据结构初阶]双链表

    目录 双链表定义 初始化 创建节点  尾插 ​编辑 尾删 头插 头删 打印 查找 pos插入 头插复用 尾插复用  pos删除 头删复用 尾删复用 判空 size 销毁  完整代码 前面我们学习了单链表，但按照 带头不带头(哨兵)和循环不循环 我们可以有四种单链表，双链表也是如此，我们最常

    2024年02月12日
    浏览(37)

  • 数据结构-单链表-双链表

    “收藏从未停止，练习从未开始”，或许有那么一些好题好方法，在被你选中收藏后却遗忘在收藏夹里积起了灰？今天请务必打开你沉甸甸的收藏重新回顾，分享一下那些曾让你拍案叫绝的好东西吧！ H x ，表示向链表头插入一个数 x。 D k ，表示删除第 k 个插入的数后面的数

    2024年02月15日
    浏览(54)
  • 【数据结构】数组、双链表代码实现

    【数据结构】数组、双链表代码实现

    💗💗💗欢迎来到我的博客，你将找到有关如何使用技术解决问题的文章，也会找到某个技术的学习路线。无论你是何种职业，我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章，也欢迎在文章下方留下你的评论和反馈。我期待着与你分享知识、互

    2024年02月19日
    浏览(42)
  • 数据结构(二)——线性表(双链表)

    数据结构(二)——线性表(双链表)

    单链表：单链表结点中只有一个指向其后继的指针，使得单链表只能从前往后依次遍历,无法逆向检索，有时候不太方便 双链表的定义： 双链表结点中有两个指针prior和next，分别指向其直接前驱和直接后继 表头结点的prior域和尾结点的next域都是NULL。 双链表结点类型描述如下

    2024年03月11日
    浏览(48)
  • 数据结构——双链表（C语言）

    数据结构——双链表（C语言）

    目录 ​编辑  双链表的初始化：  双链表的打印： 双链表的尾插： 双链表的头插：  双链表的尾删：   双链表的头删： 双链表pos位置之前的插入： 双链表pos位置的删除： 关于顺序表和链表的区别：   上篇文章给大家讲解了无头单向循环链表，它的特点：结构简单，一般

    2024年02月13日
    浏览(50)
  • 【数据结构】双链表的定义和操作

    【数据结构】双链表的定义和操作

    目录 1.双链表的定义 2.双链表的创建和初始化 3.双链表的插入节点操作 4.双链表的删除节点操作 5.双链表的查找节点操作 6.双链表的更新节点操作 7.完整代码 🌈嗨！我是Filotimo__🌈。很高兴与大家相识，希望我的博客能对你有所帮助。 💡本文由Filotimo__✍️原创，首发于CS

    2024年02月03日
    浏览(84)
  • 【数据结构】单双链表超详解！(图解+源码)

    【数据结构】单双链表超详解！(图解+源码)

    🎥 屿小夏 ： 个人主页 🔥个人专栏 ： 数据结构解析 🌄 莫道桑榆晚，为霞尚满天！ 什么是链表？链表有着什么样的结构性？它是怎么实现的？ 看完这篇文章，你对链表的理解将会上升新的高度！ 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺

    2024年02月06日
    浏览(46)
  • 【数据结构】单链表 && 双链表(链式和数组实现)

    【数据结构】单链表 && 双链表(链式和数组实现)

           🔥🔥 欢迎来到小林的博客！！       🛰️博客主页：✈️小林爱敲代码       🛰️博客专栏：✈️ 数据结构与算法       🛰️社区 :✈️ 进步学堂       🛰️欢迎关注：👍点赞🙌收藏✍️留言 今天给大家带来四个内容，一个

    2024年02月01日
    浏览(52)
  • 【C语言】数据结构——带头双链表实例探究

    【C语言】数据结构——带头双链表实例探究

    💗个人主页💗 ⭐个人专栏——数据结构学习⭐ 💫点击关注🤩一起学习C语言💯💫 我们在前面学习了单链表和顺序表。 今天我们来学习双向循环链表。 在经过前面的一系列学习，我们已经掌握很多知识，相信今天的内容也是很容易理解的。 关注博主或是订阅专栏，掌握第

    2024年02月03日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包