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

【数据结构】带头双向循环链表（小白入门必备知识）

9月前 作者：Dream_Chaser～ 分类：Toy博客 阅读(35) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】带头双向循环链表（小白入门必备知识）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言:

💥🎈个人主页:​​​​​​Dream_Chaser～ 🎈💥

✨✨专栏:http://t.csdn.cn/oXkBa

⛳⛳本篇内容:c语言数据结构--带头双向循环链表

目录

一.带头双向循环链表

 A.带头双向循环链表概念

B.带头双向循环链表的实现

1.带头双向循环链表的结构

2.动态申请节点函数

3.链表的初始化

4.链表打印

5.链表尾部插入节点

6.链表头部插入节点

7.链表尾删节点 

8.链表头删节点

9.链表查找/修改某个值

10.在链表pos位置之前插入值

LTInsert实现尾插操作:

LTInsert实现头插操作:

11.在链表pos位置处删除此节点

LTErase实现尾删:

LTErase实现头删

12.求链表的长度函数

13.释放链表动态申请的空间

Test.c

List.h

List.c

一.带头双向循环链表

链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

怎么算出8种情况:每次两种情况，三次，所以是2*2*2=8。

1. 单向或者双向

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 2. 带头或者不带头

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 3. 循环或者非循环

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

1.  无头单向非循环链表： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结
构的子结构 ，如哈希桶、图的邻接表等等。另外这种结构在 笔试面试 中出现很多。

 【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

2. 带头双向循环链表： 结构最复杂 ，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了，后面我们代码实现了就知道了。

 A.带头双向循环链表概念

        带头双向循环链表（Doubly Circular Linked List with a Head）是一种链表数据结构，它具有以下特点：

  1. 头节点：带头双向循环链表包含一个头节点，它位于链表的起始位置，并且不存储实际数据。头节点的前驱指针指向尾节点，头节点的后继指针指向第一个实际数据节点。

  2. 循环连接：尾节点的后继指针指向头节点，而头节点的前驱指针指向尾节点，将链表形成一个循环连接的闭环。这样可以使链表在遍历时可以无限循环，方便实现循环操作。

  3. 双向连接：每个节点都有一个前驱指针和一个后继指针，使得节点可以向前和向后遍历。前驱指针指向前一个节点，后继指针指向后一个节点。

        总结:带头双向循环链表可以支持在链表的任意位置进行插入和删除操作，并且可以实现正向和反向的循环遍历。通过循环连接的特性，链表可以在连续的循环中遍历所有节点，使得链表的操作更加灵活和高效。

B.带头双向循环链表的实现

1.带头双向循环链表的结构

typedef int LTDataType;//代码中将int定义为LTDataType是为了提供代码的可读性和可维护性，并增加代码的灵活性。

typedef struct ListNode
{
	struct ListNode* next;//存储下一个节点的地址
	struct ListNode* prev;//存储上一个节点的地址
	LTDataType data;
}LTNode;//重新命名结构体类型

通过将int定义为LTDataType，可以在代码中使用LTDataType作为数据类型，而不是直接使用int。这样做的好处有以下几点：

  1. 可读性：使用LTDataType作为数据类型可以使代码更具可读性。LTDataType作为一个自定义的数据类型名称，可以更好地表达代码中数据的含义和用途，提高代码的可理解性。
  2. 可维护性：将int定义为LTDataType可以方便地在代码中统一修改数据类型。如果将来需要将数据类型更改为其他类型，只需修改typedef语句中的定义，而不需要在整个代码中逐个修改具体的数据类型，减少了修改的工作量和出错的可能性。
  3. 灵活性：通过使用LTDataType，可以在代码中轻松更改数据类型，而不会对代码的其他部分产生影响。这种抽象化的方式可以使代码更具通用性，便于在不同的场景中重用。

2.动态申请节点函数

函数代码:

        此函数是关于一个结点动态申请的实现，包含两个指针域，一个数据域。如果分配成功，它会返回指向该内存块起始位置的指针。你可以使用这个指针来访问和操作所分配的内存。如果分配失败，malloc会返回NULL指针，表示内存分配未成功。

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    
    //刚申请下的堆区空间有可能开辟失败，所以要进行检查
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

    //开辟好后就赋值
	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;

	return newnode;
}

3.链表的初始化

        链表的初始化就是要创建哨兵位的头节点,此头节点不存储有效数据，并且因一开始不知道指向谁，所以根据双向链表循环的特性，就让该结点的两个指针自己指向自己。

//初始化--因为要改动指向结构体的指针，所以要么就取地址，用二级指针接收。
//要么就像下面这样，用返回值接收。
LTNode* LTInit()// 由于形参phead是实参plist的拷贝
{
	LTNode* guard = BuyLTNode(-1);
	guard->next = guard;
	guard->prev = guard;
	
	return guard;
}
int main()
{
    LTNode* plist = LTInit();
}

图解:

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

4.链表打印

        打印链表就是,遍历链表的每一个结点的数据域，开始时用assert断言传过来的结点地址是否为NULL。接着cur用phead->next赋值的原因是，phead传过来的是哨兵位的头节点，它的下一位才是链表真正的头节点（有数据域），接着遍历链表，当cur指针回到哨兵位时，遍历结束。

图解:

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

函数代码: 

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

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

5.链表尾部插入节点

与单链表有两个不一样的点:

情况一:

1.单链表尾插结点需要遍历全链表，当指针走到链表最后一个结点的时候，判断tail->next是否为NULL，若为NULL，则跳出遍历的循环，尾插新结点。然而带头双向循环链表不需要遍历链表，只需要对哨兵位的头节点的prev域解引用，直接找到带头双向循环链表的尾节点，尾插新节点。

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 

情况二:

2.头指针的区别:带头双向循环链表不需要判断头指针是否指向NULL，因为哨兵位的头节点也是有它的地址的,添加新节点时只需要直接在尾节点尾插。然而单链表却需要判断头指针是否指向NULL，而且需要用到二级指针，比较棘手。

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 

函数代码: 

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	
	LTNode* tail = phead->prev;//通过哨兵位的头节点的prev找到链表最后一个结点，并用tail指向
	LTNode* newnode = BuyLTNode(x);
	
	tail->next= newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

测试案例:

        知识点:要改变一个变量的值，特别是传参传过去的，一定要注意是传值还是传址。如果是传值调用，那么传过去的函数(自定义的函数)参数就是形参，不会改变实参(main函数里面的就是实参)。如果传址调用，一般是取这个变量的地址，函数那边要用二级指针接收，并且函数(自定义函数)里面要有一层解引用，才能操作实参的值，给实参赋值，或者其它改变实参的操作。

        malloc如果分配成功，它会返回指向该内存块起始位置的指针，意味着返回的是在堆上分配指定大小的内存块的地址，相等于取出内存块的地址，然后用一级指针接收，传一级指针过去，然后用结构体指针访问结构体成员的方式改变节点的值。

//初始化和尾插
void TestList1()
{
	LTNode* plist = LTInit();//相等于取出内存块的地址，然后用一级指针接收，传一级指针过去，然后            
                               用结构体指针访问结构体成员的方式改变节点的值。
    LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
}
int main()
{
	TestList1();
}

实现思路:依旧是数字代表顺序

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 代码执行：

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 

6.链表头部插入节点

请先看错误操作，请多注意！:

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

正确方法:

方法1：无需创建变量

图上的数字代表顺序

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 代码实现:

//方法一,不需要创建变量
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);

	newnode->next = phead->next;//把头结点后面的d1的地址赋值给新结点的next
	phead->next->prev = newnode;//d1指向新节点
	
	phead->next = newnode;//改变头节点的next，让它指向新结点
	newnode->prev = phead;//新结点的prev指向phead头插完毕.
}

方法2：创建变量first

图上的数字代表顺序

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 代码实现:

//方法二创建一个first变量
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;

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

}

代码执行:

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 

7.链表尾删节点 

图解:

当链表不止一个节点时:

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 当链表只有一个节点（哨兵位不算）时:

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

若链表为NULL(只剩哨兵位就是链表为NULL)时，再尾删就会出错

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

检查链表是否为空,进行函数封装:

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

	return phead->next == phead;
}

函数解析: 

        LTEmpty(LTNode* phead)是一个函数调用，它将链表头节点phead作为参数传递给LTEmpty函数。LTEmpty函数的作用是判断循环链表是否为空，如果为空则返回true，否则返回false。

       如果LTEmpty(phead)返回true，即链表为空，那么!LTEmpty(phead)将为false。如果LTEmpty(phead)返回false，即链表不为空，那么 !LTEmpty(phead)将为true

        assert 宏用于在运行时进行断言检查。它接受一个表达式作为参数，如果表达式的结果为false,则会触发断言失败，程序可能会终止执行。如果表达式的结果为true，则断言通过，程序继续执行。

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail= phead->prev;
	LTNode* tailPrev=tail->prev ;
	
	free(tail);	//先删除再链接
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

代码执行:
【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 

8.链表头删节点

链表不止一个结点时:

图解:

数字代表顺序

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

链表为一个结点时:

数字代表顺序

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

函数代码: 

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

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

代码执行:

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 

9.链表查找/修改某个值


LTNode* STFind(LTNode* phead, LTDataType x)
{
	//assert(phead);
	LTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
		if (cur->data == phead->data)//若重新回到哨兵位，则说明链表遍历完毕，找不到x值，返回NULL
		{
			break;
		}
	}
	return NULL;
}

 代码执行:

找到了:

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 找不到:

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

10.在链表pos位置之前插入值

图解:

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode 

void LTInsert(LTNode* pos,LTDataType x)//输入要删除的数的位置即可
{
	assert(pos);

	LTNode* newnode = BuyLTNode(x);
	LTNode* prev = pos->prev;

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

代码执行: 

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 

LTInsert实现尾插操作:
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead, x);
}
LTInsert实现头插操作:
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead->next);
	LTInsert(phead->next, x);
}

11.在链表pos位置处删除此节点

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

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

代码执行: 

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

LTErase实现尾删:
//LTPopBack链表尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	
    assert(!LTEmpty(phead));
	LTErase(phead->prev);


}
LTErase实现头删
//LTPopFront链表头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->next);

}

12.求链表的长度函数

简单来说就是计算链表的结点个数

void TestList8()//求链表长度
{
	LTNode* plist = LTInit();
	size_t count = LTSize(plist);
	printf("当前链表长度为:%zu\n", count);
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	
	count = LTSize(plist);
	printf("当前链表长度为%zu", count);
}

代码执行：

【数据结构】带头双向循环链表（小白入门必备知识）,C--数据结构,数据结构,链表,c语言,笔记,vscode

 

13.释放链表动态申请的空间

函数代码:

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

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//初始化和尾插
void TestList1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
}
//头插
void TestList2()
{
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);

}
//尾删
void TestList3()
{
	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);
}
//头删
void TestList4()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);
}
void TestList5()//查找/修改
{
	LTNode* plist = LTInit();
	printf("尾插:");
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	printf("请输入你要找的值:");
	int n = 0;
	scanf("%d", &n);
	LTNode* find = STFind(plist,n);
	if (find)
	{
		printf("找到了\n");
		find->data = 300;
		printf("修改节点的值成功\n");
		LTPrint(plist);
	} 
	else
	{
		printf("没找到\n");
	}
}
void TestList6()//pos之前插入值
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTNode* pos = STFind(plist, 3);
	if (pos)
	{
		LTInsert( pos, 30);
	}
	LTPrint(plist);
}
void TestList7()//删除pos位置的值
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTNode* pos = STFind(plist, 3);
	if (pos)
	{
		LTErase(pos);
	}
	LTPrint(plist);
}
void TestList8()//求链表长度
{
	LTNode* plist = LTInit();
	size_t count = LTSize(plist);
	printf("当前链表长度为:%zu\n", count);
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	
	count = LTSize(plist);
	printf("当前链表长度为%zu", count);
}

int main()
{
	//TestList1();//初始化和尾插
	TestList2();//头插
	//TestList3();//尾删
	//TestList4();//头删
	//TestList5();//查找、修改
	//TestList6();pos之前插入值
	//TestList7();//删除pos位置的值
	//TestList8();//求链表长度
}

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);
//判断链表是否为NULL
bool LTEmpty(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//查找
LTNode* STFind(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//pos之前插入
void LTInsert(LTNode* pos, LTDataType x);

//计算链表节点个数
size_t LTSize(LTNode* phead);
//释放链表
void LTErase(LTNode* pos);

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->prev = NULL;
	newnode->next = NULL;

	return newnode;
}

LTNode* LTInit()
{
	LTNode* guard = BuyLTNode(-1);
	guard->next = guard;
	guard->prev = guard;
	
	return guard;
}

//打印
void LTPrint(LTNode* phead)
{
	assert(phead);

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

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* newnode = BuyLTNode(x);
//
//	newnode->next = phead->next;//把头结点后面的d1的地址赋值给新结点的next
//	phead->next->prev = newnode;//d1指向新节点
//	
//	phead->next = newnode;//改变头节点的next，让它指向新结点
//	newnode->prev = phead;//新结点的prev指向phead头插完毕.
//}
//方法二创建一个first变量
//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = BuyLTNode(x);
//	LTNode* first = phead->next;
//
//	phead->next = newnode;
//	newnode->next = first;
//	newnode->prev = phead;
//	first->prev = newnode;
//
//}
//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail= phead->prev;
	LTNode* tailPrev=tail->prev ;
	
	free(tail);	//先删除再链接

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

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



//头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* first = phead->next;
	LTNode* second = phead->next->next;

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


void LTInsert(LTNode* pos,LTDataType x)//输入要删除的数的位置即可
{
	assert(pos);

	LTNode* newnode = BuyLTNode(x);
	LTNode* prev = pos->prev;

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

//INsert尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead, x);
}

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



void LTErase(LTNode* pos)
{
	assert(pos);
	
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	 
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}
//LTPopBack链表尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->prev);

	

}
//LTPopFront链表头删
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->next);

}

size_t LTSize(LTNode* phead)
{
	assert(phead);
	size_t n = 0; 
	LTNode * cur = phead->next;
	while (cur!=phead)
	{
		n++;
		cur = cur->next;
	}
	return n;
}


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

到了这里，关于【数据结构】带头双向循环链表（小白入门必备知识）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

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

相关文章

  • 数据结构-带头双向循环链表

    数据结构-带头双向循环链表

    前言： 链表有很多种，上一章结，我复盘了单链表，这一章节，主要针对双链表的知识点进行，整理复盘，如果将链表分类的话，有很多种，我就学习的方向考察的重点，主要针对这两种链表进行整理。 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用

    2023年04月09日
    浏览(49)
  • 数据结构——带头双向循环链表

    数据结构——带头双向循环链表

    在创建带头双向循环链表的节点中比之前单链表节点的创建多了一个struct ListNode* prev;结构体指针，目的在与存储前一个节点的地址，便于将整个链表连在一起。 动态申请内存结点，函数返回的是一个指针类型，用malloc开辟一个LTNode大小的空间，并用node指向这个空间，再判断

    2024年02月09日
    浏览(42)
  • 【数据结构】带头双向循环链表

    【数据结构】带头双向循环链表

      🧑‍🎓 个人主页：简 料   🏆 所属专栏：C++   🏆 个人社区：越努力越幸运社区   🏆 简       介： 简料简料，简单有料~在校大学生一枚，专注C/C++/GO的干货分享，立志成为您的好帮手 ~ C/C++学习路线 (点击解锁) ❤️ C语言阶段(已结束) ❤️ 数据结构与算法(ing) ❤

    2024年01月16日
    浏览(78)
  • 数据结构---带头双向循环链表

    数据结构---带头双向循环链表

    什么是双向带头循环链表? 上面简单的一个非空 带头循环双向链表逻辑图 如何定义一个双向链表？ 根据图和代码可以看双向链表就是单链表的每个结点中，在设置一个指向前驱节点的指针 简单认识之后，对他进行初始化(申请一个头节点，让前驱和后驱指针都指向自己) 代码

    2024年02月07日
    浏览(69)
  • 【数据结构】实现带头双向循环链表

    【数据结构】实现带头双向循环链表

    之前我们已经学习了单链表，有了单链表的基础，现在开始学习带头双向循环链表~ 结构最复杂 ，一般用在单独存储数据。 实际中使用的链表数据结构，都是带头双向循环链表 。另外这个结构虽然结构复杂，但是使用代码实现以后会发现 结构会带来很多优势 ，实现反而简单

    2024年02月10日
    浏览(46)
  • 数据结构之带头双向循环链表

    数据结构之带头双向循环链表

    目录 链表的分类 带头双向循环链表的实现 带头双向循环链表的结构 带头双向循环链表的结构示意图 空链表结构示意图 单结点链表结构示意图  多结点链表结构示意图 链表创建结点 双向链表初始化 销毁双向链表 打印双向链表  双向链表尾插 尾插函数测试 双向链表头插

    2024年02月08日
    浏览(73)

  • 数据结构_带头双向循环链表

    相较于之前的顺序表和单向链表，双向链表的逻辑结构稍微复杂一些，但是在实现各种接口的时候是很简单的。因为不用找尾，写起来会舒服一点。（也可能是因为最近一直在写这个的原因） 在实现接口的时候，除了没有找尾，其他的操作和单向链表是差不多的，这里就不多

    2024年04月14日
    浏览(63)
  • 【数据结构】线性表——带头双向循环链表

    【数据结构】线性表——带头双向循环链表

    带头双向循环链表的优点 1.支持任意位置时间复杂度为O(1)的插入和删除。 2.按照需求申请释放空间，无需担心空间不够用，无需担心浪费。 3.带头可以省去链表为空时的判断，可以使代码更加简约 带头双向循环链表的缺点 1.不可以进行下标随机访问。 2.缓存利用率低 带头双

    2024年02月03日
    浏览(69)
  • 【数据结构】带头双向循环链表及其实现

    【数据结构】带头双向循环链表及其实现

    目录 1.带头双向循环链表 2.带头双向循环链表实现 2.1初始化 2.2销毁 2.3头插 2.4链表打印 2.5头删数据 2.6尾插数据 2.7尾删数据 2.8链表判空  2.9查找一个数据 2.10在pos位置前插入数据 2.11删除pos位置 2.12求链表的长度 2.顺序表和链表的比较 我们已经实现了无头单向循环链表 带头双

    2024年02月10日
    浏览(45)
  • 数据结构-带头双向循环链表的实现

    数据结构-带头双向循环链表的实现

    前言           带头双向循环链表是一种重要的数据结构，它的结构是很完美的，它弥补了单链表的许多不足，让我们一起来了解一下它是如何实现的吧！         它的节点中存储着数据和两个指针，一个 指针_prev 用来记录前一个节点的地址，另一个指针 _next 用来记录后一

    2024年02月13日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包