数据结构-双向链表

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

前言:

在单链表那一篇博客中介绍了单链表和双向链表的优缺点,所以此篇博客直接分享怎样实现一个带头双向循环链表。

单链表博客:

1.头文件中的声明:

首先我们需要写一个结构体,双向带头链表的话需要一个前驱指针prev和一个后驱指针next,前驱指针的作用是方便找尾节点,因为头节点的prev指向的就是最后一个节点,后驱指针next的作用是方便插入和找头节点。

数据结构-双向链表,数据结构,数据结构,链表,c语言,学习

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

typedef int LTDataType;
typedef struct Listnode
{
	struct ListNode* prev;
	struct ListNode* next;
	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);
void LTInsert(LTNode* pos ,LTDataType x);//在pos位置之前插入x
void LTErase(LTNode* pos);//在pos位置删除
void LTDestroy(LTNode* phead);

2.带头双向链表的实现

2.1创建新节点

创建一个节点比较简单,首先malloc一块空间出来,然后将这个结构体的数据data设置成需要的数据,再将前驱指针和后驱指针全部置空就行,方便后续链接。

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

2.2链表初始化

双向带头链表的初始化肯定需要一个头节点,所以使用BuyLTNode创建一个头节点phead,然后将phead的next指向自己,prev也指向自己。

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

	return phead;
}

2.3打印链表

打印链表也很简单,只需要创建一个结构体指针cur来遍历链表就可以了,循环的结束条件是cur为phead,为什么呢?因为尾节点的next不为NULL,而是头指针,如果条件设置为NULL的话,就会陷入死循环,所以当cur走到头节点的话就代表已经遍历完一遍了。

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

2.4尾插

假设当前节点是这样的情况,我们要插入一个newnode,怎么尾插呢?这个时候我们就通过头节点phead找到尾节点n3,然后再尾插就可以了。首先定义一个结构体指针tail来找n3,然后将newnode进行链接,首先将newnode与tail进行链接,newnode->prev=tail,tail->next=newnode,再将newnode与phead进行链接,phead->prev=newnode,newnode->next=phead,然后newnode就在这个链表上完成尾插了。

数据结构-双向链表,数据结构,数据结构,链表,c语言,学习

数据结构-双向链表,数据结构,数据结构,链表,c语言,学习 

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

2.5尾删

尾删的话不仅要找到尾节点,还需要找到尾节点的前一个节点,所以创建一个尾节点tail,尾节点的前一个节点tailprev(tailprev=tail->prev),然后将tailprev与头节点进行链接,phead->prev=tailprev,tailprev->next=phead。

数据结构-双向链表,数据结构,数据结构,链表,c语言,学习

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTNode* tail = phead->prev;
	LTNode* pretail = tail->prev;

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

2.6头插

头插需要找到第一个节点,所以创建一个结构体指针tail指向第一个节点(tail=phead->next),然后将newnode与phead进行链接,phead->nedxt=newnode,newndoe->prev=phead,再将newnode与tail进行链接,newndoe->next=tail,tail->prev=newnode.

数据结构-双向链表,数据结构,数据结构,链表,c语言,学习

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

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

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

2.7头删

头删需要找到第一个和第二个节点,所以定义一个结构体指针first来指向第一个节点,second指向第二个节点(second=first->next),然后将第二个节点和phead进行链接,phead->next=second,second->prev=phead,然后释放第一个节点的空间,free(first)。

数据结构-双向链表,数据结构,数据结构,链表,c语言,学习

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

	LTNode* first = phead->next;
	LTNode* second = first->next;
	phead->next =second;
	second->prev = phead;
	free(first);
}

2.8有效数据

求出链表的有效数据个数就比较简单了,遍历的时候size++就行了。

int LTSize(LTNode* phead)
{
	assert(phead);
	int size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
	printf("\n");
}

2.9寻找节点

寻找节点也比较简单,在遍历链表的时候判断当前节点的data是否等于x即可。

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位置之前插入x

这里需找到pos和pos前一个节点,所以创建一个结构体指针posprev指向pos的前一个节点(posprev=pos->prev),然后将newnode与posprev进行链接,posprev->next=newnode,newnoe->prev=posprev,再将newnode与pos进行链接,pos->prev=newnode,newnode->next=pos。

数据结构-双向链表,数据结构,数据结构,链表,c语言,学习

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyLTNode(x);
	LTNode* prepos = pos->prev;
	newnode->next = pos;
	pos->prev = newnode;
	newnode->prev = prepos;
	prepos->next = newnode;

}

将这个函数完成之后就可以对头插与尾插进行简化了。

尾插:

这里大家需要了解一下为什么第一个参数是phead,因为LTInsert这个函数是实现pos位置之前的插入,当我们需要尾插,那么尾巴的后一个节点是什么呢?不就是头节点吗!!

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

	LTInsert(phead, x);
}

头插:

头插就比较好理解了,第一个参数就是头节点的下一个节点。

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

	LTInsert(phead->next, x);
}

2.11删除pos位置的节点

删除pos位置需要找到pos的前一个节点和后一个节点,所以创建一个结构体指针posprev保存pos的前一个节点(posprev=pos->prev),再创建一个结构体指针保存pos的后一个节点(posnext=pos->next),然后将posprev与posnext进行链接,posprev->next=posnext,posnext->prev=posprev,然后free掉pos。

数据结构-双向链表,数据结构,数据结构,链表,c语言,学习

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

}

将这个函数完成之后就可以对头删与尾删进行简化了。

头删:

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

	LTErase(phead->next);
}

尾删:

尾节点通过头节点phead的前驱指针来找就好了。

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	LTErase(phead->prev);
}

2.12销毁

销毁链表还是和单链表一样,区别就是循环结束条件是cur走到头节点,还有就是保存cur的后一个节点,最后还要free掉头节点,因为没有走到头节点。

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-751859.html

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

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

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】—C语言实现双向链表(超详细!)

                                          食用指南:本文在有C基础的情况下食用更佳                                       🔥 这就不得不推荐此专栏了:C语言                                     🍀 双向链表 前 置知识 :单链表      

    2024年02月13日
    浏览(21)
  • 【数据结构】C语言实现双向链表(带头结点、循环)

    结点定义: 接口定义: 我们将申请结点的代码封装成函数,方便后续使用 由于是带头结点的双向链表,因此在使用链表前,我们需要对链表进行初始化。 遍历链表,值得说的是,带头结点的双向链表的循环结束条件是 cur != phead 尾插时,需要先找到尾结点,然后将新结点插

    2024年02月03日
    浏览(22)
  • 【数据结构初阶】四、线性表里的链表(带头+双向+循环 链表 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】三、 线性表里的链表(无头+单向+非循环链表 -- C语言实现)-CSDN博客  ====

    2024年02月08日
    浏览(24)
  • 数据结构学习分享之双向链表详解

        💓博主CSDN:杭电码农-NEO💓🎉🎉🎉       ⏩专栏分类:数据结构学习分享(持续更新中🫵)⏪🎉🎉🎉       我们上一期说到,两链表中有两个最常用的结构,一个是最简单的无头不循环单向链表,还有一个就是 结构相对比较复杂的带头双向循环链表 ,我们这一章节就来

    2024年02月04日
    浏览(27)
  • 『初阶数据结构 • C语言』⑨ - 基于结点的数据结构——链表(单链表&&双向循环链表)附完整源码

      本章内容 1.什么是链表 2.链表常见几种形式 3.无头单向非循环链表的实现 3.1结点结构的定义 3.2函数接口的实现 3.2.1尾插 3.2.2尾删 4. 带头双向循环链表的实现 4.1结点结构的定义 4.2函数接口的实现 5.两种链表的差异 ①尾插与尾删的时间复杂度 ②头插与头删的时间复杂度 ③

    2024年02月16日
    浏览(12)
  • 链接未来:深入理解链表数据结构(二.c语言实现带头双向循环链表)

    上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表:链接未来:深入理解链表数据结构(一.c语言实现无头单向非循环链表)-CSDN博客 那今天接着给大家带来带头双向循环链表的实现 : 头文件DoubleList.h:用来基础准备(常量定义,typedef),链表表的基本框架

    2024年01月16日
    浏览(21)
  • 【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)

    🎁 单链表的节点中只有一个 next 指针引用着下一个节点的地址 🎁 当要获取单链表中的最后一个元素的时候,需要从头节点开始遍历到最后 🎁 单链表一开始的时候有 first 头指针引用着头节点的地址 💰 双向链表可以提升链表的综合性能 💰 双向链表的节点中有 prev 指针引

    2024年02月12日
    浏览(20)
  • 数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印(基于C语言实现)

    版本: 2024年4月26日 V1.0 发布于博客园 目录 目录 双向循环链表公式 初始化双向循环链表 构建双向循环链表结点 创建一个空链表(仅头结点) 创建一个新结点 插入数据 头插 中插 尾插 删除数据 头删 中删 尾删 查询打印数据 遍历打印 测试 测试结果: 完整代码 DoubleCirLList.h

    2024年04月27日
    浏览(15)
  • 数据结构-链表结构-双向链表

    双向链表也叫双链表,与单向链表不同的是,每一个节点有三个区域组成:两个指针域,一个数据域 前一个指针域:存储前驱节点的内存地址 后一个指针域:存储后继节点的内存地址 数据域:存储节点数据 以下就是双向链表的最基本单位 节点的前指针域指向前驱,后指针

    2024年02月04日
    浏览(20)
  • 青岛大学_王卓老师【数据结构与算法】Week04_04_双向链表的插入_学习笔记

    本文是个人学习笔记,素材来自青岛大学王卓老师的教学视频。 一方面用于学习记录与分享,另一方面是想让更多的人看到这么好的《数据结构与算法》的学习视频。 如有侵权,请留言作删文处理。 课程视频链接: 数据结构与算法基础–第04周04–2.5.4双向链表2–双向链表

    2024年02月12日
    浏览(22)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包