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

来领略一下带头双向循环链表的风采吧

9月前 分类：Toy博客 阅读(73) 违法举报

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

🍉 博客主页：阿博历练记
📖文章专栏：数据结构与算法
🚍代码仓库：阿博编程日记
🌹欢迎关注：欢迎友友们点赞收藏+关注哦

来领略一下带头双向循环链表的风采吧

🍄前言

来领略一下带头双向循环链表的风采吧
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
上期阿博带友友们实现了单链表,我们可以看出单链表的尾插以及尾删都是非常复杂的，比如尾插：如果链表为空，我们就需要调用二级指针改变来接收plist的地址，因为首次尾插，plist为空，我们要让plist指向结点，需要改变plist,所以传plist的地址，但是之后，我们只需要改变结构体中的next指针，让它指向我们开辟出来的结点就可以了，此时我们改变的是结构体，就不需要传结构体地址了。再比如我们的尾删：我们需要遍历链表，找到尾结点的前一个结点，这样非常麻烦，而且效率很低，但是双向循环链表就会方便很多，我们可以直接通过尾结点的prev指针找到它的前一个结点，我们尾插的时候就不用再判断链表是否为空了，因为就算链表为空，头、尾结点也不为空，它们此时都是哨兵位，我们尾插的时候改变的一直都是结构体的next指针.
来领略一下带头双向循环链表的风采吧

🍼双向循环链表

🔍1.链表的定义

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

🔍2.链表的初始化

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;
}

📢误区

❌错误案例

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;
}
void LTInit(LTNode*phead)
{
    phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
}

来领略一下带头双向循环链表的风采吧

⛳友友们，这里我们通过调试也可以看出plist的值并没有被改变，因为我们传的是plist的值，所以形参的改变不会影响实参，形参只是实参的一份临时拷贝，这里我们要改变的是plist，所以我们要传plist的地址，但是我们还可以通过通过返回值的方式来让plist接收newnode,这种就是值拷贝的方式返回，就是先把newnode的值拷贝给pilst,然后它又是一个局部变量，出完函数作用域就销毁了，但是我们通过plist找到那个开辟出来的结点，因为它在堆区上存放，所以出完函数作用域，那个结点并没有销毁.

🔍3.链表的尾插

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;
}
void  PushBack(LTNode* phead, LTDataType x)
{
	assert(phead);   //就算链表为空，这里也一定不能为空，因为phead是带哨兵位的头结点。
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
	//LTInsert(phead,x);
}

来领略一下带头双向循环链表的风采吧

🔍4.链表的头插

1.未定义指针版

void  PushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);

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

📢注意先后顺序

来领略一下带头双向循环链表的风采吧
2.定义指针版

void  PushFront(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;
	//LTInsert(phead->next,x);
}

来领略一下带头双向循环链表的风采吧

🔍5.链表的打印

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

来领略一下带头双向循环链表的风采吧

🔍6.链表的尾删

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

来领略一下带头双向循环链表的风采吧

所以友友们这里我们就可以定义一个布尔值，来判空，这样可以提高我们代码的可读性💯.

bool  LTEmpty(LTNode* phead)
{
	assert(phead);
	return  phead->next == phead;
}

友友们注意这里是个等号，不是赋值号，因为空链表是phead->next和phead相等，而不是赋值.

🔍7.链表的头删

void  PopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* cur = phead->next;
	phead->next = cur->next;
	cur->next->prev = phead;
	free(cur);
	//LTErase(phead->next);
}

来领略一下带头双向循环链表的风采吧
这里我们也可以定义两个指针来提高我们代码的可读性🙈🙈🙈.
来领略一下带头双向循环链表的风采吧

🔍8.链表的查找

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;
}

友友们注意，这里我们让cur从phead->next处开始遍历，因为哨兵位的头结点不存储有效数据.这个函数同时兼具修改的功能，因为它可以返回结点的地址.

🔍9.链表任意位置的插入（在pos之前插入）

1.未定义指针版

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;
}

📢注意先后顺序

来领略一下带头双向循环链表的风采吧
2.定义指针版
来领略一下带头双向循环链表的风采吧

友友们，当我们这个函数写好之后，我们的头插和尾插就可以附用这个函数了，头插就可以写成LTInsert(phead->next,x),尾插就可以写成LTInsert(phead,x),⛳友友们一定要注意尾插不是LTInsert（phead->prev,x）,因为我们是在pos之前插入的，所以我们pos的位置必须是头结点.

🔍10.链表任意位置的删除（pos位置）

void  LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

来领略一下带头双向循环链表的风采吧

友友们，当我们这个函数写好之后，我们的头删和尾删就可以附用这个函数了，头删就可以写成LTErase（phead->next）,尾删就可以写成LTErase（phead->prev）.

🔍11.链表的销毁

void  LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		//cur = cur->next;   这里cur已经被释放了，不能在使用了，否则就是野指针
		cur = next;
	}
	free(phead);
	//phead = NULL;   这里置空也没用，因为phead是一级指针，形参的改变不会影响实参，就算把它置空，plist也不会被改变.
}

友友们注意，这里phead=NULL对plist是无效的，因为它们是值传递，形参只是实参的一份临时拷贝，形参的改变不会影响实参.所以我们可以在外面把plist置空，当我们头插，尾插之后一定要注意及时释放，否则就会出现内存泄露.

👻List.h代码

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef  int  LTDataType;
typedef struct  ListNode
{
	LTDataType  data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;
LTNode* LTInit();    //初始化链表
void  LTPrint(LTNode* phead);   //打印链表
void  PushBack(LTNode* phead, LTDataType x);   //尾插
void  PushFront(LTNode* phead, LTDataType x);  //头插
bool  LTEmpty(LTNode* phead);
void  PopFront(LTNode* phead);        //头删
void  PopBack(LTNode* phead);         //尾删
LTNode* LTFind(LTNode* phead, LTDataType x);  //链表的查找
//在pos之前插入
void  LTInsert(LTNode* pos, LTDataType x);
void  LTErase(LTNode* pos);  //删除pos位置的值
void  LTDestroy(LTNode* phead);  //链表的销毁

👻List.c代码

#define  _CRT_SECURE_NO_WARNINGS 1
#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;
}
void  LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("guard<==>");
	while (cur != phead)
	{
		printf("%d<==>",cur->data);
		cur = cur->next;
	}
	printf("\n");
}
void  PushBack(LTNode* phead, LTDataType x)
{
	assert(phead);   //就算链表为空，这里也一定不能为空，因为phead是带哨兵位的头结点。
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
	//LTInsert(phead,x);
}
void  PushFront(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* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
	//LTInsert(phead->next,x);
}
bool  LTEmpty(LTNode* phead)
{
	assert(phead);
	return  phead->next == phead;
}
void  PopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* cur = phead->next;
	phead->next = cur->next;
	cur->next->prev = phead;
	free(cur);
	//LTErase(phead->next);
}
void  PopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
	//LTErase(phead->prev);
}
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* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
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 = cur->next;   这里cur已经被释放了，不能在使用了，否则就是野指针
		cur = next;
	}
	free(phead);
	//phead = NULL;   这里置空也没用，因为phead是一级指针，形参的改变不会影响实参，就算把它置空，plist也不会被改变.
}

👻test.c代码

#define  _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void  TestList1()
{
	LTNode* plist = LTInit();
	PushBack(plist, 1);
	PushBack(plist, 2);
	PushBack(plist, 3);
	PushBack(plist, 4);
	LTPrint(plist);

	PopBack(plist);
	LTPrint(plist);

	PopBack(plist);
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}
void TestList2()
{

	LTNode* plist = LTInit();
	PushFront(plist, 1);
	PushFront(plist, 2);
	PushFront(plist, 3);
	PushFront(plist, 4);
	PopFront(plist);
	LTNode* pos = LTFind(plist, 3);
	if (pos)
	{
		LTInsert(pos, 30);
	}
	LTPrint(plist);
	LTDestroy(plist);
	plist = NULL;
}
int  main()
{
	TestList1();
	TestList2();
	return  0;
}

🧋代码效果展示

来领略一下带头双向循环链表的风采吧文章来源地址https://www.toymoban.com/news/detail-450165.html

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

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

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

相关文章

  • 【数据结构 -- C语言】 双向带头循环链表的实现

    【数据结构 -- C语言】 双向带头循环链表的实现

    目录 1、双向带头循环链表的介绍 2、双向带头循环链表的接口 3、接口实现 3.1 开辟结点 3.2 创建返回链表的头结点 3.3 判断链表是否为空 3.4 打印 3.5 双向链表查找 3.6 双向链表在pos的前面进行插入 3.6.1 头插 3.6.2 尾插 3.6.3 更新头插、尾插写法 3.7 双向链表删除pos位置的节点

    2024年02月09日
    浏览(62)
  • 【数据结构】—带头双向循环链表的实现（完美链表）

    【数据结构】—带头双向循环链表的实现（完美链表）

    链表结构一共有八种形式，在前面的文章里已经讲完了不带头单向非循环链表的实现，但是我们发现该链表实现尾插与尾删时比较麻烦，要先从头节点进行遍历，找到尾节点，时间复杂度为O(N)，而本次所讲的带头双向循环单链表，则可以直接找到尾节点。 虽然该链表看起来

    2024年01月25日
    浏览(61)
  • 【数据结构】链表：带头双向循环链表的增删查改

    【数据结构】链表：带头双向循环链表的增删查改

    本篇要分享的内容是带头双向链表，以下为本片目录 目录 一、链表的所有结构 二、带头双向链表 2.1尾部插入 2.2哨兵位的初始化 2.3头部插入 2.4 打印链表 2.5尾部删除 2.6头部删除  2.7查找结点 2.8任意位置插入 2.9任意位置删除  在刚开始接触链表的时候，我们所学仅仅所学的

    2024年02月05日
    浏览(89)
  • 数据结构:链表基础OJ练习+带头双向循环链表的实现

    数据结构:链表基础OJ练习+带头双向循环链表的实现

    目录 一.leetcode剑指 Offer II 027. 回文链表 1.问题描述 2.问题分析与求解 (1) 快慢指针法定位链表的中间节点 (2) 将链表后半部分进行反转 附:递归法反转链表 (3) 双指针法判断链表是否回文 二.带头双向循环链表的实现 1.头文件 2.节点内存申请接口和链表初始化接口 3.链表的打

    2024年02月02日
    浏览(49)
  • 实现带头双向循环链表

    实现带头双向循环链表

    描述：一个节点内包含两个指针，一个指向上一个节点，另一个指向下一个节点。哨兵位指向的下一个节点为头节点，哨兵位的上一个指向尾节点。 结构优势：高效率找尾节点；高效率插入与删除；无需判断多种复杂情况，如尾节点、空节点等。 BuyListNode节点创建函数（）

    2024年02月10日
    浏览(54)
  • 带头双向循环链表

    带头双向循环链表

    前言：当我们想要挪动大量数据的时候，单链表的效率就很低了，比如尾插，要找到尾，通过遍历的时间复杂度最坏情况是O(N),所以我们引进结构复杂但效率高的双向带头循环链表 带头双向循环链表指得是什么呢？就是既存储了上一个节点的地址，又存储了下一个节点的地址

    2024年04月23日
    浏览(31)
  • 双向带头循环链表

    双向带头循环链表

    所属专栏：初始数据结构 博主首页：初阳785 代码托管：chuyang785 感谢大家的支持，您的点赞和关注是对我最大的支持！！！ 博主也会更加的努力，创作出更优质的博文！！ 关注我，关注我，关注我，重要的事情说三遍！！！！！！！！ 我们之前也已经学完了单链表，并且也

    2024年02月05日
    浏览(39)
  • 双向--＞带头--＞循环链表

    双向--＞带头--＞循环链表

    目录 一、双向带头循环链表概述 1.什么是双向带头循环链表 2.双向带头循环链表的优势 3.双向带头循环链表简图 二、双向带头循环链表的增删查改图解及代码实现 1.双向带头循环链表的头插 2.双向带头循环链表的尾插 3.双向带头循环链表的头删 4.双向带头循环链表的尾删

    2024年02月12日
    浏览(55)
  • “车裂”链表---双向带头循环链表

    “车裂”链表---双向带头循环链表

    目录 前言： 1.先看结构： 2.创建节点 3.初始化链表 4.打印链表 5.判空 6.尾插​ 7.头插​ 8.尾删​ 9.头删 10.查找与修改 修改： 11.插入---在pos之前插入 12.删除---删除pos 13.销毁 总结： 继上一章的单链表，再介绍一个更加方便的链表---双向带头循环链表： 带头即哨兵位的头节点

    2024年02月19日
    浏览(82)
  • 链表（2）——带头双向循环链表

    链表（2）——带头双向循环链表

    目录 🍁一、链表的分类 🌕1.单向或者双向 🌕2.带头或者不带头（有无哨兵） 🌕3.循环或者不循环 🌕4.无头单向非循环链表（常用） 🌕5.带头双向循环链表（常用） 🌕注意： 🍁二、双向链表的定义： 🍁三、带头双向循环链表的定义 🍁四、带头双向循环链表操作实现（

    2024年02月08日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包