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

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

目录

1.单向链表的劣势

2.带头双向循环链表

        1.逻辑结构

       2.结点的代码实现

3.双向链表接口的实现

        1.接口1---初始化

        2.接口2,3---头插,尾插

        3. 接口4,5---头删,尾删

        3. 接口6---查找

         4. 接口7,8--插入,删除

        5. 接口8---打印

        6. 接口9--销毁

4.完整代码及效果展示 


1.单向链表的劣势

        上期我们讲解了链表8种结构中最为常用的两种结构之一单向不带头不循环链表的基本概念和实现方法(传送门:动图详解单向链表)。但是在实现时我们发现了以下局限性:

  1. 由于单链表是单向的,当我们想进行插入或者删除时,由于无法直接找到前驱结点,导致我们还需再使用一个指针遍历链表找到前一个结点的位置。这就导致了进行插入和删除的时间复杂度为O(N),时间效率较低。
  2. 由于我们需要再使用一个指针指向链表前一个结点,这也可能在一些情况下导致出错,例如链表只有一个结点。(详情请见上一期,含动图分析)
  3. 由于其不带头结点,头指针直接指向第一个有效结点,所以在进行头插等可能改变头指针的操作时我们如果传一级指针就会出错。

2.带头双向循环链表

        1.逻辑结构

        那么,我们要如何解决以上劣势呢?这就不得不说到另一种最为常见的链表结构:带头双向循环链表

        头结点:所谓头结点,其作用就是标识链表的有效部分。我们之前实现的无头结点的链表,都是通过头指针直接指向链表的有效数据部分。而带头结点的链表,则是用头指针指向一个不存放有效数据的结点,这个结点就称作头结点。这个结点的next指针存放的下一个结点才是链表的有效结点部分。图示如下:

双向链表动画演示,数据结构,链表,数据结构,c语言,学习

          带头双向循环链表:其结构是8种结构中最复杂的,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。此链表的结点在单向链表的基础上,添加了前驱指针prev指向上一个结点,然后添加了上述所描述的头结点,而循环则是体现在首尾结点相连上。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现起来反而更加简单。逻辑结构如下:

双向链表动画演示,数据结构,链表,数据结构,c语言,学习

注:蓝色箭头代表逻辑上指针的指向,均表示某个结点next或prev指针指向另一个结点,下同。

       2.结点的代码实现

        根据单向链表结点的代码实现和双向链表的结构体,我们可以得出其结点的结构体定义如下:

双向链表动画演示,数据结构,链表,数据结构,c语言,学习

3.双向链表接口的实现

        我们同样先在主函数中定义一个头指针用于指向我们的头结点,后续通过这个指针来完成对链表各种接口的实现。由于头指针并不直接指向有效数据部分,有效数据是从第二个结点开始的,因此当我们对数据进行操作时并不需要改变头指针的内容,只需进行传值调用,用一级指针接收即可,可以有效避免头指针被无意修改。

        1.接口1---初始化

        在使用链表前,我们需要对链表进行初始化。我们可以在初始化接口中创建一个头结点并将其返回给头指针,代码如下:

//用于创建新结点
ListNode* CreatNode(ListDateType x)
{
	ListNode* cur=(ListNode*)malloc(sizeof(ListNode));
	cur->date = x;
	cur->next = NULL;
	cur->prev = NULL;
	return cur;
}

//链表初始化
ListNode* InitList()
{
	ListNode* phead=CreatNode(0); //创建头结点
	phead->next = phead; //前驱指针指向自身
	phead->prev = phead; //后继指针指向自身  
	return phead; //将这个结点返回
}

        2.接口2,3---头插,尾插

        对于头插,根据双向循环链表结构图,我们只需将头结点的next指向新结点,新结点的prev指向头结点,next指向下一结点,下一结点的prev指向新结点即可完成头插。具体过程如下:

双向链表动画演示,数据结构,链表,数据结构,c语言,学习

         代码实现如下:

//头插
void ListPushFront(ListNode* phead, ListDateType x) //不改变头指针,无需传址
{
	assert(phead != NULL); //保证链表有头结点,即完成了初始化
	ListNode* NewNode = CreatNode(x); //创建新结点
	ListNode* frist = phead->next; //找到链表头

    //进行头插
	phead->next = NewNode;
	NewNode->prev = phead;
	NewNode->next = frist;
	frist->prev = NewNode;
}

         对于尾插,由于双向循环链表结构的特殊性,我们不需要向单链表一样遍历链表找到链表尾,直接通过头结点的prev指针就可直接找到链表尾,也不需要再遍历链表找到上一个结点。代码反而变得更加简单,只需要通过改变结点的prev和next指针即可完成尾插,这就是结构带来的优势。其时间复杂度为O(1)。具体过程如下:

双向链表动画演示,数据结构,链表,数据结构,c语言,学习

        具体代码如下: 

//尾插
void ListPushBack(ListNode* phead, ListDateType x)
{
	assert(phead != NULL); //保证链表已经初始化
	ListNode* NewNode = CreatNode(x); //创建新结点
	ListNode* tail = phead->prev; //找到链表尾

    //进行尾插
	tail->next = NewNode; 
	NewNode->prev = tail;
	NewNode->next = phead;
	phead->prev = NewNode;
}

需要注意的是,与单链表不同,这里是双向循环链表,所以链表尾并不是指向NULL,而是指向头结点。同时不会出现对NULL解引用的情况,不需要对单向链表一样进行分类讨论。

        3. 接口4,5---头删,尾删

        对于头删,我们只需要将头结点指向下一个位置,然后将原来指向的空间free()掉即可。如果链表为空,我们就让函数直接返回,具体动态效果如下:

双向链表动画演示,数据结构,链表,数据结构,c语言,学习

         代码实现如下:

//头删
void ListPopFront(ListNode* phead)
{
	assert(phead != NULL); //确保链表初始化
	if (phead->next == phead)
	{
		return; //链表为空直接返回,防止把头结点删除
	}
	ListNode* frist = phead->next; //找到链表头
	ListNode* second = frist->next; //找到链表头下一个结点

    //进行头删
	phead->next = second;
	second->prev = phead;
	free(frist); //释放结点
	frist = NULL;
}

        对于尾删,我们同样通过头结点的prev指针直接找到链表尾,然后进行删除操作,过程与头删类似,时间复杂度为O(1)。具体过程如下:

双向链表动画演示,数据结构,链表,数据结构,c语言,学习

        具体代码如下:

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead != NULL); //确保链表已经初始化
	if (phead->next == phead)
	{
		return; //链表为空直接返回,防止把头结点删除
	}
	ListNode* tail = phead->prev; //找到链表尾
	ListNode* prev = tail->prev;  //找到前驱

    //进行尾删
	phead->prev = prev;
	prev->next = phead;
	free(tail); //释放空间
	tail = NULL;
}

        3. 接口6---查找

        对于查找,其方法与单向链表一样,通过遍历链表的所有结点即可。有一点不同的是我们的双向链表是循环的,因此循环的条件不再是cur!=NULL而是cur!=phead,当cur等于头指针时则说明已经成功遍历一遍了。代码如下:

//查找
ListNode* ListFind(ListNode* phead, ListDateType x)
{
	assert(phead != NULL); //确保已经初始化
	ListNode* cur = phead->next; //指向第一个有效结点,准备遍历
	while (cur != phead) //遍历一圈
	{
		if (cur->date == x)
		{
			return cur; //找到了,返回结点
		}
		cur = cur->next; //指向下一结点
	}

    //找不到,返回空指针
	return NULL;
}

         4. 接口7,8--插入,删除

        对于插入,我们可以实现一个在指定结点前插入一个新结点的接口,而这个指定结点我们可以通过查找接口来获取。由于我们的链表是双向的,我们就可以很容易的得到新结点的前一个与后一个结点的位置,进而实现插入接口,其时间复杂度为O(1)。动态效果如下:

双向链表动画演示,数据结构,链表,数据结构,c语言,学习

//插入
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x)
{
	assert(pos != NULL); //确保已经初始化
	ListNode* NewNode = CreatNode(x); //创建新结点
	ListNode* prev = pos->prev; //前一个结点

    //进行插入
	NewNode->next = pos;
	pos->prev = NewNode;
	prev->next = NewNode;
	NewNode->prev = prev;

}

        对于删除,我们同样可以实现一个删除指定结点的接口,而这个指定结点我们依旧可以通过查找接口来获取。同样的,由于结构上的优势,我们可以很方便的直接对指定位置进行删除,时间复杂度为O(1)。具体过程如下:

双向链表动画演示,数据结构,链表,数据结构,c语言,学习

        具体代码如下: 

//删除
void ListErase(ListNode* phead, ListNode* pos)
{
	assert(pos != NULL); //确保已经初始化
	ListNode* next = pos->next; //后一个结点
	ListNode* prev = pos->prev; //前一个结点

    //进行删除
	prev->next = next;
	next->prev = prev;
	free(pos); //释放空间
	pos = NULL;
}

        5. 接口8---打印

        对于打印,很简单,遍历一圈链表即可,当cur等于头结点地址时停止打印。动图效果如下:

双向链表动画演示,数据结构,链表,数据结构,c语言,学习

        具体代码如下: 

//打印
void ListPrint(ListNode* phead)
{
	assert(phead != NULL); //确保链表已经初始化
	ListNode* cur = phead->next; //指向有效部分
	while (cur != phead) //遍历一圈
	{
		printf("%d ", cur->date); //打印数据
		cur = cur->next; //指向下一结点
	}
	printf("\n");
}

        6. 接口9--销毁

        对于销毁,我们动态内存申请所得到的空间,当我们不需要的时候,需要我们进行手动销毁。因此,我们还需要一个接口对使用完毕的链表进行free(),具体代码如下:

//销毁
void ListDestroy(ListNode* phead)
{
	assert(phead != NULL); //确保已经初始化
	ListNode* cur = phead->next; //指向有效部分
	while (cur != phead) //释放有效结点
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	//释放头结点
	free(phead);
	phead = NULL;
}

通过上面一个个接口的实现,我们发现:

        虽然双向带头循环链表的结构比起单向链表结构复杂太多,但对于各接口的实现反而变得更加方便,并且很多接口时间效率更加地高。因此,一个好的结构不仅可以简化我们的代码量,也可以提高我们代码的效率。

4.完整代码及效果展示 

        我们同样采用多文件编写的形式,将上述接口的定义实现放在List.c文件中,然后将接口的声明和结构体的定义放于List.h头文件中,以达到封装的效果。这样我们如果需要使用双向链表,就只需要在文件中包含对应的头文件List.h就可以使用我们上面定义的各种接口。以下为本文实现的带头双向循环链表完整代码以及效果展示:

//List.h文件,用于声明接口函数,定义结构体
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int ListDateType; //重命名便于维护
typedef struct ListNode
{
	ListDateType date;
	struct ListNode* next; //指向前一个结点
	struct ListNode* prev; //指向后一个结点
}ListNode;

//初始化
ListNode* InitList();
//尾插
void ListPushBack(ListNode* phead, ListDateType x);
//头插
void ListPushFront(ListNode* phead, ListDateType x);
//尾删
void ListPopBack(ListNode* phead);
//头删
void ListPopFront(ListNode* phead);
//查找
ListNode* ListFind(ListNode* phead, ListDateType x);
//删除
void ListErase(ListNode* phead, ListNode* pos);
//插入
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x);
//打印
void ListPrint(ListNode * phead);
//销毁
void ListDestroy(ListNode* phead);
//SList.c文件,用于定义接口函数
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

ListNode* CreatNode(ListDateType x)
{
	ListNode* cur=(ListNode*)malloc(sizeof(ListNode));
	cur->date = x;
	cur->next = NULL;
	cur->prev = NULL;
	return cur;
}
ListNode* InitList()
{
	ListNode* phead = CreatNode(0); //创建头结点
	phead->next = phead; //前驱指针指向自身
	phead->prev = phead; //后继指针指向自身  
	return phead; //将这个结点返回
}

void ListPushBack(ListNode* phead, ListDateType x)
{
	assert(phead != NULL);
	ListNode* NewNode = CreatNode(x);
	ListNode* tail = phead->prev; //找到链表尾
	tail->next = NewNode; 
	NewNode->prev = tail;
	NewNode->next = phead;
	phead->prev = NewNode;
}

void ListPushFront(ListNode* phead, ListDateType x) //不改变头指针,无需传址
{
	assert(phead != NULL); //保证链表有头结点,即完成了初始化
	ListNode* NewNode = CreatNode(x); //创建新结点
	ListNode* frist = phead->next; //找到链表头

	//进行头插
	phead->next = NewNode;
	NewNode->prev = phead;
	NewNode->next = frist;
	frist->prev = NewNode;
}

void ListPopBack(ListNode* phead)
{
	assert(phead != NULL);
	if (phead->next == NULL)
	{
		return; //链表为空直接返回
	}
	ListNode* tail = phead->prev; //找到链表尾
	ListNode* prev = tail->prev;  //找到前驱
	phead->prev = prev;
	prev->next = phead;
	free(tail);
	tail = NULL;

}

void ListPopFront(ListNode* phead)
{
	assert(phead != NULL); //确保链表初始化
	if (phead->next == NULL)
	{
		return; //链表为空直接返回
	}
	ListNode* frist = phead->next; //找到链表头
	ListNode* second = frist->next; //找到链表头下一个结点

	//进行头删
	phead->next = second;
	second->prev = phead;
	free(frist); //释放结点
	frist = NULL;
}

ListNode* ListFind(ListNode* phead, ListDateType x)
{
	assert(phead != NULL); //确保已经初始化
	ListNode* cur = phead->next; //指向第一个有效结点,准备遍历
	while (cur != phead) //遍历一圈
	{
		if (cur->date == x)
		{
			return cur; //找到了,返回结点
		}
		cur = cur->next; //指向下一结点
	}

	//找不到,返回空指针
	return NULL;
}

void ListErase(ListNode* phead, ListNode* pos)
{
	assert(pos != NULL); //确保已经初始化
	ListNode* next = pos->next; //后一个结点
	ListNode* prev = pos->prev; //前一个结点

	//进行删除
	prev->next = next;
	next->prev = prev;
	free(pos); //释放空间
	pos = NULL;
}

void ListInsert(ListNode* phead, ListNode* pos, ListDateType x)
{
	assert(pos != NULL); //确保已经初始化
	ListNode* NewNode = CreatNode(x); //创建新结点
	ListNode* prev = pos->prev; //前一个结点

	//进行插入
	NewNode->next = pos;
	pos->prev = NewNode;
	prev->next = NewNode;
	NewNode->prev = prev;

}

void ListPrint(ListNode* phead)
{
	assert(phead != NULL); //确保链表已经初始化
	ListNode* cur = phead->next; //指向有效部分
	while (cur != phead) //遍历一圈
	{
		printf("%d ", cur->date); //打印数据
		cur = cur->next; //指向下一结点
	}
	printf("\n");
}

void ListDestroy(ListNode* phead)
{
	assert(phead != NULL); //确保已经初始化
	ListNode* cur = phead->next; //指向有效部分
	while (cur != phead) //释放有效结点
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	//释放头结点
	free(phead);
	phead = NULL;
}

       最后, 我们在text.c文件调用双向循环链表各个接口进行测试,如下:

//text.c文件,用于测试
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void ListText()
{
	ListNode* plist = NULL;
	//初始化
	plist = InitList();
	printf("链表起始数据:\n");
	ListPrint(plist);
	//尾插
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	printf("尾插后数据:\n");
	ListPrint(plist);
	//头插
	ListPushFront(plist, 4);
	ListPushFront(plist,5);
	ListPushFront(plist, 6);
	printf("头插后数据:\n");
	ListPrint(plist);
	//尾删
	ListPopBack(plist);
	printf("尾删后数据:\n");
	ListPrint(plist);
	//头删
	ListPopFront(plist);
	printf("头删后数据:\n");
	ListPrint(plist);

	//修改数据为5的结点为50
	ListNode* cur1 = ListFind(plist, 5); //找数据为5结点
	if (cur1)
	{
		cur1->date = 50; //查找附带着修改的作用
	}
	printf("修改数据为5的结点为50后\n");
	ListPrint(plist);

	//在date为4的结点前插入数据为7的结点
	ListNode* cur2 = ListFind(plist,4); //找数据为4结点
	if (cur2) 
	{
		ListInsert(plist, cur2, 7); //插入
	}
	printf("在4前插入7后数据:\n");
	ListPrint(plist);
	//删除数据为1的结点
	ListNode* cur3 = ListFind(plist, 1); //找数据为1结点
	if (cur3) 
	{
		ListErase(plist, cur3); //删除
	}
	printf("删除1后数据:\n");
	ListPrint(plist);
	//销毁
	ListDestroy(plist);
}
int main()
{
	ListText();
	return 0;
}

        以下就是测试的最终效果:

双向链表动画演示,数据结构,链表,数据结构,c语言,学习


 以上,就是本期的全部内容。

制作不易,能否点个赞再走呢qwq文章来源地址https://www.toymoban.com/news/detail-819143.html

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

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

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

相关文章

  • 数据结构:详解【链表】的实现(单向链表+双向链表)

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

    2024年03月26日
    浏览(65)
  • 数据结构之双向链表详解

    😽博主CSDN主页:小源_😽 🖋️个人专栏:《数据结构》🖋️ 😀努力追逐大佬们的步伐~ 上一篇文章中我们重点讲解了无头单向非循环链表的模拟实现,现在我们来讲解LinkedList(无头双向链表实现 )的模拟实现。 本章重点: 本文着重讲解了LinkedList(无头双向单链表)的实现

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

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

    2024年02月04日
    浏览(67)
  • 数据结构 - 链表详解(二)—— 带头双向循环链表

    链表的结构一共有 八种 :带头单向循环链表、带头单向非循环链表、带头双向循环链表、带头双向非循环链表、无头单向循环链表、无头单向非循环链表、无头双向循环链表、无头双向非循环链表。 今天我们来详解带头双向循环链表 带头双向循环链表是一种数据结构,它通

    2024年04月26日
    浏览(57)
  • 数据结构:线性表之-循环双向链表(万字详解)

    目录 基本概念 1,什么是双向链表 2,与单向链表的区别 双向链表详解 功能展示: 1. 定义链表 2,创建双向链表 3,初始化链表 4,尾插 5,头插 6,尾删 判断链表是否被删空 尾删代码 7,头删 8,pos位置之前插入 优化后的头插 优化后的尾插 9,删除pos位置的节点 优化后的尾删 优

    2024年02月09日
    浏览(51)
  • 数据结构:图文详解双向链表的各种操作(头插法,尾插法,任意位置插入,查询节点,删除节点,求链表的长度... ...)

    目录 一.双向链表的概念 二.双向链表的数据结构 三.双向链表的实现 节点的插入 头插法 尾插法 任意位置插入 节点的删除 删除链表中第一次出现的目标节点 删除链表中所有与相同的节点 节点的查找 链表的清空 链表的长度 四.模拟实现链表的完整代码 前言: 在上一

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

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

    2024年02月04日
    浏览(47)
  • 【数据结构】双向奔赴的爱恋 --- 双向链表

    关注小庄 顿顿解馋๑ᵒᯅᵒ๑ 引言:上回我们讲解了单链表(单向不循环不带头链表),我们可以发现他是存在一定缺陷的,比如尾删的时候需要遍历一遍链表,这会大大降低我们的性能,再比如对于链表中的一个结点我们是无法直接访问它的上一个结点,那有什么解决方法呢

    2024年04月08日
    浏览(95)
  • 数据结构—双向链表

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

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

    Hello,好久不见,今天我们讲链表的双向链表,这是一个很厉害的链表,带头双向且循环,学了这个链表,你会发现顺序表的头插头删不再是一个麻烦问题,单链表的尾插尾删也变得简单起来了,那废话不多说,让我们开始我们的学习吧! 首先我们要了解它的物理和逻辑结构

    2024年02月11日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包