首页 > 其他分享 >数据结构:双向链表（Doubly Linked List篇）手把手带你入门数据结构~

数据结构:双向链表（Doubly Linked List篇）手把手带你入门数据结构~

时间：2024-09-24 23:19:55浏览次数：3  
标签：List next 链表 LTNode phead 双向 数据结构 plist

文章目录

前言

在这里插入图片描述

上次介绍了不带头单向不循环链表，接下来我们一起看看双向带头循环链表。

一、双向链表的概念

双向带头循环链表是一种特殊的双向链表，具有以下特点：

  1. 双向链表： 每个节点有两个指针，一个指向前驱节点（_prev），一个指向后继节点（_next）。因此，从任意节点可以沿链表向前或向后遍历。

  2. 带头节点： 链表中有一个特殊的头节点（通常不存储实际数据，称为哨兵节点）。头节点的主要作用是简化操作，如插入和删除。它提供统一的起始点，使得链表的头尾操作更加方便。

  3. 循环链表： 链表的最后一个节点的 _next 指向头节点，头节点的 _prev 指向最后一个节点。因此，链表是循环的，没有明确的开始和结束，方便从任意节点进行循环遍历。

1. 结构特点：

  • 头节点作为链表的起始和终止标记，解决了普通链表操作时需要判断空链表或链表尾部的问题。
  • 空链表时，头节点的 _next 和 _prev 都指向自己。

2. 优点：

  • 统一操作： 无论链表是否为空，头节点总是存在，插入和删除操作不需要特殊处理空链表或只有一个节点的情况。
  • 双向遍历： 可以从任意节点向前或向后遍历，非常灵活。
  • 循环结构： 链表没有明确的尾部，方便处理循环场景。

双向带头循环链表常用于需要频繁插入和删除操作的场景，能够高效地处理这些操作。
在这里插入图片描述

二、双向链表的实现

1.双向链表的结构

typedef int LTDataType;

typedef struct ListNode
{
	LTDataType date;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

双向链表有三个数据，保存它自身数据，他的前驱指针，以及他的后继指针。
在这里插入图片描述

2. 双向链表初始化

//双向链表初始化
void LTInit(LTNode** pphead);

因为初始化要创造头节点，而且为了方便后续插入操作创造节点，我们要先写出创造节点的方法

创造出的节点本身自己也必须是双向循环的才可以，他的prev以及next都指向他自己，自身成环。
在这里插入图片描述

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->date = x;
	newnode->next = newnode;
	newnode->prev = newnode;
	return newnode;
}

//双向链表初始化
void LTInit(LTNode** pphead)
{
	*pphead = LTBuyNode(-1);
}

3. 双向链表销毁

//双向链表销毁
void LTDesTory(LTNode** pphead);

销毁的时候要遍历链表，将链表中的每一个节点都销毁，这里我们传的是二级指针，头节点会被会被销毁，但后面为了统一接口需要手动释放。

//双向链表销毁
void LTDesTory(LTNode** pphead)
{
	assert(pphead && *pphead);
	LTNode* pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		LTNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	free(*pphead);
	*pphead = NULL;
	pcur = NULL;
}

4. 双向链表打印

//双向链表打印
void LTPrint(LTNode* phead)；

和单链表一样，打印链表就是遍历链表.

注意，当时我们的循环条件是pcur != NULL，但是双链表是循环的，还这样写的话就成了死循环，因此需要让循环条件变成 pcur != phead

//双向链表打印
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d -> ", pcur->date);
		pcur = pcur->next;
	}
	printf("\n");
}

5. 双向链表尾插

//双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x);

我们来看下面这张图，看一下尾插涉及到了哪些节点。
在这里插入图片描述

//双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

6. 双向链表头插

//双向链表头插
void LTPushFront(LTNode* phead, LTDataType x);

我们来看下面这张图，看一下头插涉及到了哪些节点。
在这里插入图片描述

//双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

7. 双向链表尾删

//双向链表尾删
void LTPopBack(LTNode* phead);

删除操作要判断当前链表是不是空链表，如果为空就不进行删除。

为空就是链表只有头节点。

//双向链表是否为空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

我们来看这张图。
在这里插入图片描述

//双向链表尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	LTNode* prev = del->prev;
	prev->next = phead;
	phead->prev = prev;
	free(del);
	del = NULL;
}

8. 双向链表头删

//双向链表头删
void LTPopFront(LTNode* phead);

在这里插入图片描述

//双向链表头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}

9. 双向链表查找

//双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x);

查找遍历链表，返回结点。

//双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->date == x)
		{
			//找到了
			return pcur;
		}
		pcur = pcur->next;
	}
	//没找到
	return NULL;
}

10. 双向链表指定位置插入

//双向链表指定位置插入
void LTInsert(LTNode* pos, LTDataType x);

在这里插入图片描述

//双向链表指定位置插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

11. 双向链表指定位置删除

//双向链表指定位置删除
void LTErase(LTNode* pos);

在这里插入图片描述

//双向链表指定位置删除
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

三、双线链表优化

因为有哨兵位的存在，我们不用改变头结点，因此就可以传一级指针

1. 初始化优化接口

将接口改为一级指针，因为形参无法影响实参，因此需要手动接收所创造出来的结点。

//优化让接口统一为 LTNode* phead
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

这样来接收~

	LTNode* plist = LTInit();

2. 销毁优化接口

将接口改为一级指针，因为形参无法影响实参，因此创造的plist需要手动释放，将plist放置为NULL。

//优化接口统一为 LTNode* phead，但是需要手动释放让 *plist=NULL;!!!
void LTDesTory2(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = (phead)->next;
	while (pcur != phead)
	{
		LTNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	free(phead);
	phead = NULL;
	pcur = NULL;
}

像这样置空~

//LTDesTroy(&plist);
LTDesTroy2(plist);
plist = NULL;

总结

到这里相信大家对双向链表有一个深入的了解了，最后的总结双向链表实现的源码奉上需要的小伙伴们自取哦~

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

typedef int LTDataType;

typedef struct ListNode
{
	LTDataType date;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

//双向链表初始化
//void LTInit(LTNode** pphead);

//优化让接口统一为 LTNode* phead
LTNode* LTInit();

//双向链表销毁
void LTDesTory(LTNode** pphead);

//优化接口统一为 LTNode* phead，但是需要手动释放让 *plist=NULL;
void LTDesTory2(LTNode* phead);

//双向链表打印
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);

//双向链表指定位置插入
void LTInsert(LTNode* pos, LTDataType x);

//双向链表指定位置删除
void LTErase(LTNode* pos);


//Lish.c
#include"List.h"

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->date = x;
	newnode->next = newnode;
	newnode->prev = newnode;
	return newnode;
}

//双向链表初始化
//void LTInit(LTNode** pphead)
//{
//	*pphead = LTBuyNode(-1);
//}

//优化让接口统一为 LTNode* phead
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

//双向链表销毁
//void LTDesTory(LTNode** pphead)
//{
//	assert(pphead && *pphead);
//	LTNode* pcur = (*pphead)->next;
//	while (pcur != *pphead)
//	{
//		LTNode* Next = pcur->next;
//		free(pcur);
//		pcur = Next;
//	}
//	free(*pphead);
//	*pphead = NULL;
//	pcur = NULL;
//}

//优化接口统一为 LTNode* phead，但是需要手动释放让 *plist=NULL;!!!
void LTDesTory2(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = (phead)->next;
	while (pcur != phead)
	{
		LTNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	free(phead);
	phead = NULL;
	pcur = NULL;
}

//双向链表打印
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d -> ", pcur->date);
		pcur = pcur->next;
	}
	printf("\n");
}

//双向链表是否为空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

//双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

//双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

//双向链表尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	LTNode* prev = del->prev;
	prev->next = phead;
	phead->prev = prev;
	free(del);
	del = NULL;
}

//双向链表头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}

//双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->date == x)
		{
			//找到了
			return pcur;
		}
		pcur = pcur->next;
	}
	//没找到
	return NULL;
}

//双向链表指定位置插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

//双向链表指定位置删除
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

//测试样例
#include"List.h"

void ListTest01()
{
	//创建双向链表变量
	//LTNode* plist = NULL;
	//LTInit(&plist);

	LTNode* plist = LTInit();

	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	//LTPushFront(plist, 1);
	//LTPrint(plist);
	//LTPushFront(plist, 2);
	//LTPrint(plist);
	//LTPushFront(plist, 3);
	//LTPrint(plist);
	//LTPushFront(plist, 4);
	//LTPrint(plist);
	//
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	//LTPrint(plist);

	//LTNode* pos = LTFind(plist, 3);
	//if (pos == NULL)
	//{
	//	printf("没有找到！\n");
	//}
	//else
	//{
	//	printf("找到了！\n");
	//}
	//LTInsert(pos, 11);
	//LTErase(pos);
	//LTPrint(plist);

	//LTDesTroy(&plist);
	LTDesTroy2(plist);
	plist = NULL;
}
int main()
{
	ListTest01();
	return 0;
}

真相永远只有一个！

在这里插入图片描述

标签：List,next,链表,LTNode,phead,双向,数据结构,plist
From： https://blog.csdn.net/Jdxxwu/article/details/142435545

相关文章

  • 【链表操作】前驱和后继
    题目描述设计函数void prevnext(structnode*head,charx);，在以head为头指针的非空链表中，找到数据域值为x的结点，输出该结点的前一个结点和后一个结点的数据域值，如果该结点没有前驱结点(即该结点为第1个结点)，则以-1代替，如果该结点没有后继结点(即该结点为尾结点)，也以-1代替......
  • List Comprehensions, Classe Data
    Assignment#2-ListComprehensions,Classes,CSV,TabularDataThisassignmentconsistsofthreeparts:1.HighestandLowestPotentiallyaffectedvehicles.2.nelta.py3.nelta.pyandRecallswithPotentiallyaffectedvehicles>500,000Clickonthis......
  • 简单易懂理解：数仓——拉链表
    1.什么是拉链表拉链表就像衣服的拉链一样重要，实用性非常强，使用频率非常高。所谓的拉链，就是历史记录，记录一个事物的开始到结束所变化的所有信息。“拉链表是一种针对数据仓库设计中表存储数据的方式而定义的数据模型，它有点类似于快照，‌它通过记录每个数据项的生效日期和失效......
  • Java怎么把多个对象的list的数据合并
    环境idea,java8方法1.使用addAll()方法想简单地想要合并List，直接使用List的addAll()方法是最直接的方式。List<YourType>list1=newArrayList<>();List<YourType>list2=newArrayList<>();//假设list1和list2已经有了数据List<YourType>merged......
  • 16年408-数据结构
    第一题：解析：经过查表可知：a的链接地址是1010H，而1010H正是表中e所在的位置。由题可知f存放的位置是1014H，要将f链接在a和e的中间，则a后面要链接f，f后面要链接e，e的链接地址不变因此答案是1014H，1004H，1010H，答案选D第二题：解析：选D。p->next->prev：p的后一个节点的prev指针......
  • 15年408-数据结构
    第一题解析：栈第一次应该存main的信息。然后进入到main里面，要输出S(1)，将S(1)存入栈内，进入到S(1)中，1>0,所以还要调用S(0)S(0)进入栈中，此时栈内从下至上依次是main(),S(1),S(0)答案选A第二题：解析：先序序列个数为0时，二叉树个数是1：先序序列个数为1时，二叉树个数是1：......
  • 链表的回文结构
    对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。测试样例：1->2->2->1返回：true什么是回文？：回文是指从前向后读和从后向前读都相同的字符......
  • 数据结构算法题
    目录轮转数组原地移除数组中所有元素val删除有序数组中的重复项合并两个有序数组轮转数组思路1：1.利用循环将最后一位数据放到临时变量（n）中2.利用第二层循环将数据往后移一位3.将变量（n）的数据放到数组第一位时间复杂度：O(N^2)空间复杂度：O(1)思路2：1.创建一个空间......
  • 数据结构：单链表
    单链表单链表概念与结构节点链表的性质单链表的打印实现单链表创建新的节点在末尾插入数据在头部插入数据删除尾部数据删除第一个节点在链表中寻找目标数据在指定位置之前插入数据在指定位置之后插⼊数据删除pos结点删除pos之后的结点销毁链表单链表测试单链表概念与......
  • 基础数据结构之链表
    链表1)概述定义在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续Incomputerscience,alinkedlistisalinearcollectionofdataelementswhoseorderisnotgivenbytheirphysicalplacementinmemory.Instead,eachelem......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99