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

数据结构——双向链表（保姆级教程，包学包会）

9月前 作者：吃火锅的腿腿 分类：Toy博客 阅读(35) 违法举报

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

1.双向链表的概念

双向链表就是带头双向循环链表

我们在学完单链表之后，就感觉这个非常简单了，他的主要表现就是拥有头节点，链表永不为空，不需要二级指针；可以通过一个节点找到上一个或者下一个节点；头尾相连呈环状。

他主要结构是由prev、next、data，这三个结构组成，通过prev找到前一个节点，next就不用多说了。

如图所示

双向链表,数据结构,链表,数据结构

 不多废话，直接上代码

2.双向链表的实现

2.1 结构设计

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;

}LTNode;

2.2 接口总览

实现一个双向链表的各个接口

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;

}LTNode;

LTNode* LTInit();
void LTPrint(LTNode* phead);

bool LTEmpty(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);

注意看一下啊我们的初始化的时候，这里是不带参数的，是为什么呢？

双向链表是带头的，有头节点，就是我们说的哨兵位，哨兵位不存储有效数据，所以链表的第一个节点就是哨兵位后面的第一个节点。

注意：这里面我们用二级指针也可以操作，但是我们在以后的代码中二级指针太麻烦而且容易用错，所以我们直接用哨兵位的办法来解决，不需要用二级指针。

2.3 初始化

创建一个哨兵位，让他自己变成一个环形链表

只需要让他自己指向自己就可以

双向链表,数据结构,链表,数据结构

 

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

 2.4 创建节点

当我们需要插入元素是，只需要创建节点，然后直接把值存入，两个指针置为空，返回该节点的地址就可。

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
	
}

2.5 尾插

直接图片更清晰观赏，我们思路是：将tail->next的链接直接连接到newnode，然后将newnode->prev连接到tail。最后phead的prev和next连接即可。

双向链表,数据结构,链表,数据结构

 

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

2.6 头插

头插就是将链表上的第一个节点与哨兵位的链接断开，但是在断开之前我们一定要先保存好将要断开的data，在去改变你将要头插的newnode

双向链表,数据结构,链表,数据结构

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* first = phead->next;
	LTNode* newnode = BuyLTNode(x);

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;

}

 2.7 尾删

这里我们还是一样的要找到tail前一个节点tailprev，然后直接释放掉尾节点就好

这里面注意一下，要是只有哨兵位就不能删除

双向链表,数据结构,链表,数据结构

 

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//防止把哨兵位删掉
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);

	phead->prev = tailprev;
	tailprev->next = phead;
}

2.8 头删

对于头删来说，我需要删除链表的第一个节点，也就是 哨兵位的 next 节点 ，我需要改变 哨兵位 和 第二个节点 的链接关系，然后释放 第一个节点 。

双向链表,数据结构,链表,数据结构

 

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* first = phead->next;
	LTNode* firstnext = first->next;
	free(first);

	firstnext->prev = phead;
	phead->next = firstnext;
}

2.9 查找

对于 双向链表 来说，它是没有指向NULL的节点的，它是一个环，停不下来。所以我们要把循环的截止条件设定为 ! = phead，这个条件就表示，已经遍历过一遍链表了

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

2.10 在pos之前插入

通过 pos 的 prev 找到 pos 位置的上一个节点 posprev ，然后改变 posprev 和 新节点 newnode  之间的链接和 newnode 和 pos 之间的链接

双向链表,数据结构,链表,数据结构

 

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;

	newnode->prev = posprev;
	posprev->next = newnode;

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

2.11 在pos之前插入

在pos位置删除，我们只需找到pos前一个节点posprev，和后一个节点posnext，将prev和next的链接接好，释放pos节点

双向链表,数据结构,链表,数据结构

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	free(pos);

	posprev->next = posnext;
	posnext->prev = posprev;
}

 

2.12 判断是否为空

这里我们可以加上这个函数，如果phead下一个等于phead，说明链表为空只剩下哨兵位自己，那么此时我们就不能继续删除了，这里我们可以用这个函数直接替换掉上面的断言

bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

这里我们也可以简写成：

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTInsert(phead, x);
}


void LTPushFront(LTNode* phead, LTDataType x)
{
	LTInsert(phead->next, x);
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->prev);
}


void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	LTErase(phead->next);

}

2.13 打印

void LTPrint(LTNode* phead)
{
	assert(phead);

	printf("guard<==>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.14 销毁

我们这时直接把链表节点全部删除，在删除过程中记住我们下一个节点以便于循环

注意：由于在函数中，我释放了哨兵位，并要将其置空。释放是可以的，因为我知道哨兵位的地址，释放就可以，但是置空却完成不了。因为我的 哨兵位 是形参，改变形参并不能影响实参，所以我们还需要在主函数中将 哨兵位 置空

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<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;

}LTNode;

LTNode* LTInit();
void LTPrint(LTNode* phead);

bool LTEmpty(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)
	{
		perror("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;
}

bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* first = phead->next;
	LTNode* newnode = BuyLTNode(x);

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;

}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//防止把哨兵位删掉
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);

	phead->prev = tailprev;
	tailprev->next = phead;
}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* first = phead->next;
	LTNode* firstnext = first->next;
	free(first);

	firstnext->prev = phead;
	phead->next = firstnext;
}

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;

	newnode->prev = posprev;
	posprev->next = newnode;

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

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	free(pos);

	posprev->next = posnext;
	posnext->prev = posprev;
}

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(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");
}

Test.c

#include"List.h"

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

	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

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

	LTDestroy(plist);
	plist = NULL;
}

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

	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	/*LTPopFront(plist);
	LTPrint(plist);*/

	LTDestroy(plist);
	plist = NULL;
}

void TestList3()
{
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);

	LTNode* pos = LTFind(plist, 3);
	if (pos)
	{
		LTInsert(pos, 30);
	}
	LTPrint(plist);

	LTDestroy(plist);
	plist = NULL;
}

int main()
{
	TestList3();

	return 0;
}

以上就是今天的分享喜欢的话请三联支持一下我们下期再见哦文章来源地址https://www.toymoban.com/news/detail-769512.html

到了这里，关于数据结构——双向链表（保姆级教程，包学包会）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

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

相关文章

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

    单向链表：一块内存指向下一个内存。 单链表存在一些缺陷： 1.查找速度慢。 2.不能从后往前找。 3.找不到前驱。 链表的结构分为8种： 1.单向和双向 2.带头和不带头 带头的链表有一个带哨兵位的头结点，这个节点不存储有效数据。 好处 ：尾插更方便，不需要二级指针了，

    2024年02月02日
    浏览(45)
  • 数据结构 - 双向链表

    数据结构 - 双向链表

    文章目录 目录 文章目录 前言 一、什么是双向链表? 双向链表有什么优势? 二、双向链表的设计和实现 1.设计思想 尾增 : 在链表的末尾添加新的元素  头插 : 在链表头部插入节点  删除 : 根据val的值删除节点  查找 : 根据索引的值查找并返回节点 总结 大家好,今天给大家讲解

    2024年02月09日
    浏览(37)
  • 数据结构—双向链表

    数据结构—双向链表

    目录 1.  链表的种类 2.  最实用的两种链表类型 3.  实现双向带头循环链表                   3.1 创建头节点         3.2 实现双向循环功能—返回头指针         3.3  尾插           3.4 头插         3.5 尾删         3.6 头删 4.  实现两个重要接口函数  

    2023年04月23日
    浏览(65)
  • 数据结构-双向链表

    数据结构-双向链表

    在单链表那一篇博客中介绍了单链表和双向链表的优缺点，所以此篇博客直接分享怎样实现一个带头双向循环链表。 单链表博客： 首先我们需要写一个结构体，双向带头链表的话需要一个前驱指针prev和一个后驱指针next，前驱指针的作用是方便找尾节点，因为头节点的prev指

    2024年02月05日
    浏览(48)
  • 数据结构——实现双向链表

    数据结构——实现双向链表

    怎么说呢？光乍一听名字好像很难的样子是吧，那如果你这样认为的话，可就要让你大跌眼镜了哦，其实双向带头循环链表从操作和理解上来说都是要易于单项不带头不循环链表（俗称单链表）的。 咱们就来见识见识吧！希望真的能让你们“大跌眼镜”哈！ 双向带头循环链

    2024年02月07日
    浏览(54)
  • 【数据结构】链表的分类和双向链表

    【数据结构】链表的分类和双向链表

    本篇是基于上篇单链表所作，推荐与上篇配合阅读，效果更加 http://t.csdnimg.cn/UhXEj 链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构： 我们一般叫这个头为哨兵位 我们上回讲的单链表就是不带头单项不循环链表。 今天我们要讲带头双向循环的链表。 不过

    2024年01月25日
    浏览(38)
  • 数据结构入门 — 链表详解_双向链表

    数据结构入门 — 链表详解_双向链表

    数据结构入门 — 双向链表详解 博客主页链接：https://blog.csdn.net/m0_74014525 关注博主，后期持续更新系列文章 文章末尾有源码 *****感谢观看，希望对你有所帮助***** 第一篇：数据结构入门 — 链表详解_单链表 第二篇：数据结构入门 — 链表详解_双向链表 第三篇：数据结构入门

    2024年02月11日
    浏览(47)
  • 数据结构：详解【链表】的实现（单向链表+双向链表）

    数据结构：详解【链表】的实现（单向链表+双向链表）

    1.顺序表的问题和思考 问题： 中间/头部的插入删除，时间复杂度为O(N)。 增容需要申请新空间，拷贝数据，释放旧空间,会有不小的消耗。 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据

    2024年03月26日
    浏览(65)
  • 【数据结构与算法】双向链表

    【数据结构与算法】双向链表

    作者：旧梦拾遗186 专栏：数据结构成长日记   带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。 现在我们来通

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

    【数据结构】双向链表详解

    当我们学习完单链表后，双向链表就简单的多了，双向链表中的头插，尾插，头删，尾删，以及任意位置插，任意位置删除比单链表简单，今天就跟着小张一起学习吧！！ 还有双向带头不循环链表，双向不带头循环链表，着重使用双向带头循环链表，带头也就是有哨兵位。

    2024年02月09日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包