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

双链表——“数据结构与算法”

10月前 作者：认真学习的小雅兰. 分类：Toy博客 阅读(38) 违法举报

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

各位CSDN的uu们你们好呀，今天，小雅兰又回来了，到了好久没有更新的数据结构与算法专栏，最近确实发现自己有很多不足，需要学习的内容也有很多，所以之后更新文章可能不会像之前那种一天一篇或者一天两篇啦，话不多说，下面，让我们进入双链表的世界吧

 之前小雅兰写过单链表的文章：https://xiaoyalan.blog.csdn.net/article/details/130353520?spm=1001.2014.3001.5502

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

双链表——“数据结构与算法”

双链表——“数据结构与算法”

 这八种结构分别为：单向带头循环链表、单向带头非循环链表、单向不带头循环链表、单向不带头非循环链表、双向带头循环链表、双向带头非循环链表、双向不带头循环链表、双向不带头非循环链表

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

单向不带头非循环链表和双向带头循环链表

双链表——“数据结构与算法”

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

下面，我们开始用代码和图来实现一下双向带头循环链表！！！

在后续函数中，有很多函数都需要这样一个功能：创建一个新节点

那么，我们把此功能单独封装成一个函数：

//创建一个新节点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = ((LTNode*)malloc(sizeof(LTNode)));
	if (newnode == NULL)
	{
		printf("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

双链表的初始化：

//双链表的初始化
LTNode* LTInit()
{
	//哨兵位的头节点
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

 尾插：

双链表——“数据结构与算法”

 双链表——“数据结构与算法”

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	//malloc一个新节点
	LTNode* newnode = BuyLTNode(x);
	//让tail的下一个结点指向newnode，链接起来
	tail->next = newnode;
	//newnode的前一个结点指向tail
	newnode->prev = tail;
	//newnode的下一个结点指向头，形成循环
	newnode->next = phead;
	//phead的上一个结点指向newnode
	phead->prev = newnode;
}

头插：

双链表——“数据结构与算法”

//头插
//插在哨兵位的头节点的后面
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

当然，这样的代码可读性是非常高的，可是，有些人就不喜欢定义那么多指针，然后就还有另外一种写法：

双链表——“数据结构与算法”

//头插
//插在哨兵位的头节点的后面
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;
}

 但是这样的代码，可读性就显得不是那么的高，所以尽量不要使用这种写法

不是说你写代码多定义了几个指针就说你写的代码没有那些没有定义什么指针的代码差，关键得看可读性！！！

双链表的打印：

//双链表的打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("guard<--->");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<--->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

 下面，让我们来验证一下头插和尾插的功能：

void TestDoubleList1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPrint(plist);
	LTPushFront(plist, 6);
	LTPushFront(plist, 7);
	LTPushFront(plist, 8);
	LTPushFront(plist, 9);
	LTPushFront(plist, 10);
	LTPrint(plist);
}
int main()
{
	TestDoubleList1();
	return 0;
}

双链表——“数据结构与算法”

 尾删：

双链表——“数据结构与算法”

 首先要判断此链表是否为空：

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

头删：

双链表——“数据结构与算法”

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* first = phead->next;
	LTNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);

}

头删也有另外一种写法，和上面阐述的一样，也是可以不用定义这么多指针，但是代码的可读性差一些

双链表——“数据结构与算法”

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
	free(next);
}

下面，让我们来验证一下头删和尾删的功能：

void TestDoubleList2()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPrint(plist);
	LTPushFront(plist, 6);
	LTPushFront(plist, 7);
	LTPushFront(plist, 8);
	LTPushFront(plist, 9);
	LTPushFront(plist, 10);
	LTPrint(plist);
	LTPopBack(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPopFront(plist);
	LTPrint(plist);
}
int main()
{
	TestDoubleList2();
	return 0;
}

双链表——“数据结构与算法”

在双链表里面查找：

//在双链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
}

在pos位置之前插入值： 双链表——“数据结构与算法”

//在pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

一般查找和在pos位置之前插入值是搭配使用的！！！

下面，让我们来测试一下此功能：

void TestDoubleList3()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPrint(plist);
	LTPushFront(plist, 6);
	LTPushFront(plist, 7);
	LTPushFront(plist, 8);
	LTPushFront(plist, 9);
	LTPushFront(plist, 10);
	LTPrint(plist);
	LTPopBack(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTNode* pos = LTFind(plist, 3);
	if (pos != NULL)
	{
		LTInsert(pos, 30);
	}
	LTPrint(plist);

}
int main()
{
	TestDoubleList3();
	return 0;
}

双链表——“数据结构与算法”

 在pos位置之前插入值这个功能，可以很好地解决之前头插和尾插的功能，头插和尾插可以直接复用此代码：

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	LTInsert(phead->next, x);
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead, x);
}

双链表——“数据结构与算法”

删除pos位置的值： 双链表——“数据结构与算法”

//删除pos位置的值
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

验证一下该删除功能：

void TestDoubleList4()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	LTPrint(plist);
	LTPushFront(plist, 6);
	LTPushFront(plist, 7);
	LTPushFront(plist, 8);
	LTPushFront(plist, 9);
	LTPushFront(plist, 10);
	LTPrint(plist);
	LTPopBack(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTNode* pos = LTFind(plist, 3);
	if (pos != NULL)
	{
		LTInsert(pos, 30);
	}
	LTPrint(plist);
	pos = LTFind(plist, 1);
	if (pos != NULL)
	{
		LTErase(pos);
	}
	LTPrint(plist);
}
int main()
{
	TestDoubleList4();
	return 0;
}

 双链表——“数据结构与算法”

这个功能也很神奇，删除pos位置的值，之前我们写的头删和尾删一样可以复用此代码的功能

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->prev);
}
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->next);
}

双链表——“数据结构与算法”

 双链表的销毁：

//双链表的销毁
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

如果不销毁双链表，就会有内存泄漏的问题！！！

源代码如下：

List.h的内容：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDataType data;
}LTNode;
//双链表的初始化
LTNode* LTInit();
//双链表的打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//在双链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的值
void LTErase(LTNode* pos);
//双链表的销毁
void LTDestroy(LTNode* phead);

List.c的内容：

#include"List.h"
//创建一个新节点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = ((LTNode*)malloc(sizeof(LTNode)));
	if (newnode == NULL)
	{
		printf("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
//双链表的初始化
LTNode* LTInit()
{
	//哨兵位的头节点
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
//双链表的打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("guard<--->");
	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;
	//malloc一个新节点
	LTNode* newnode = BuyLTNode(x);
	//让tail的下一个结点指向newnode，链接起来
	tail->next = newnode;
	//newnode的前一个结点指向tail
	newnode->prev = tail;
	//newnode的下一个结点指向头，形成循环
	newnode->next = phead;
	//phead的上一个结点指向newnode
	phead->prev = newnode;
}
//头插
//插在哨兵位的头节点的后面
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}
头插
插在哨兵位的头节点的后面
//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;
//}
头插
//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	LTInsert(phead->next, x);
//}
尾插
//void LTPushBack(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTInsert(phead, x);
//}
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}
头删
//void LTPopFront(LTNode* phead)
//{
//	assert(phead);
//	assert(!LTEmpty(phead));
//	LTNode* next = phead->next;
//	phead->next = next->next;
//	next->next->prev = phead;
//	free(next);
//}
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* first = phead->next;
	LTNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
}
尾删
//void LTPopBack(LTNode* phead)
//{
//	assert(phead);
//	assert(!LTEmpty(phead));
//	LTErase(phead->prev);
//}
头删
//void LTPopFront(LTNode* phead)
//{
//	assert(phead);
//	assert(!LTEmpty(phead));
//	LTErase(phead->next);
//}
//在双链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
}
//在pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
//删除pos位置的值
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}
//双链表的销毁
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

好啦，小雅兰今天的学习内容就到这里啦，还要继续加油噢！！！

双链表——“数据结构与算法”文章来源地址https://www.toymoban.com/news/detail-444066.html

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

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

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

相关文章

  • 数据结构--双链表

    数据结构--双链表

    单链表 VS 双链表 单链表：无法逆向检索，有时候不太方便 双链表：可进可退，存储密度更低一丢丢 在p结点之后插入s结点 特殊处理：p是最后一个结点 用后插操作实现结点的插入有什么好处？ 按位序插入前插操作： 找到前一个结点进行后插操作 ####删除p的后继结点q 特殊处

    2024年02月11日
    浏览(40)
  • 【数据结构】双链表

    【数据结构】双链表

     带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。 1.准备工作  由于实际开发项目中，项目的实现都是采用模

    2024年02月14日
    浏览(40)
  • 数据结构之双链表

    数据结构之双链表

    双链表的思路和单链表大同小异,就是多加了一个前驱指针,希望大家好好学习双链表的代码

    2024年02月07日
    浏览(46)
  • 数据结构——双链表

    数据结构——双链表

    我宁愿靠自己的力量，打开我的前途，而不愿求有力者垂青  文章目录 双线向链表各接口函数名或变量名  双向链表接口实现源码 快速索引【头文件及函数声明】 双向链表接口实现 双向链表的构造分析 双向链表的定义及初始化 双向链表的插入和删除 往期回顾： 数据结构

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

    [数据结构初阶]双链表

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

    2024年02月12日
    浏览(38)
  • 【数据结构初阶】双链表

    【数据结构初阶】双链表

    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)

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

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

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

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

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

    2024年02月19日
    浏览(45)
  • 数据结构——双链表（C语言）

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

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

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

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

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

    2024年03月11日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包