【数据结构初阶】四、线性表里的链表（带头+双向+循环链表 -- C语言实现）

=========================================================================

相关代码gitee自取：

C语言学习日记: 加油努力 (gitee.com)

=========================================================================

接上期：

【数据结构初阶】三、线性表里的链表（无头+单向+非循环链表 -- C语言实现）-CSDN博客

=========================================================================

引言

通过上期对单链表（无头+单向+非循环链表）的介绍和使用

我们可以知道顺序表和链表的区别：





顺序表和链表的一些区别：



单链表（无头+单向+非循环链表）只有一个后继指针next指向下一个结点，
而双向链表不仅有后继指针next还有一个前驱指针prev指向上一个结点

上篇单链表只能顺着往后遍历，不能倒着往回走，
会造成一些操作很困难（回文、逆置等操作），
而双向链表能顺着往后遍历也能倒着往回遍历

更多区别图示：

不同点（方面）顺序表链表

存储空间上物理上一定连续逻辑上连续，但物理上不一定连续

随机访问支持 -- O(1) 不支持 -- O(N)

任意位置插入或者删除可能需要搬移元素，效率低 -- O(N) 只需修改指针指向

插入时的容量（空间）动态顺序表，空间不够时需要扩容没有容量的概念（分成一个个结点）

应用场景元素高效存储+频繁访问频繁在任意位置插入和删除

缓存利用率高低

注：缓存利用率参考存储体系结构以及局部原理性



回顾上期中提到的带头双向循环链表：

带头双向循环链表

简介：

结构最复杂，一般用在单独存储数据。

实际中使用的链表数据结构，都是带头双向循环链表。

另外这个结构虽然结构复杂，

但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了

图示：

不同点（方面）	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持 -- O(1)	不支持 -- O(N)
任意位置插入或者删除	可能需要搬移元素，效率低 -- O(N)	只需修改指针指向
插入时的容量（空间）	动态顺序表，空间不够时需要扩容	没有容量的概念（分成一个个结点）
应用场景	元素高效存储+频繁访问	频繁在任意位置插入和删除
缓存利用率	高	低

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

1 . 双向链表的实现
（带头+双向+循环链表）

（详细解释在图片的注释中，代码分文件放最后）


实现具体功能前的准备工作

包含之后会用到的头函数

创建双向链表数据类型 -- 链表结点中数据域里存储的数据的类型

创建双向链表结点结构体(类型) -- 结点中应有数据域和指针域

图示





---------------------------------------------------------------------------------------------



BuyLTNode函数 -- 创建双向循环链表结点

为创建结点开辟动态空间，并检查是否开辟成功


开辟成功后，初始化结点数据域和指针域

最后返回开辟的空间地址

图示





---------------------------------------------------------------------------------------------



LTInit函数 -- 带头双向循环链表初始化函数

初始化时先使用BuyLTNode函数创建哨兵位


因为要实现循环，
所以让哨兵位后继指针next和前驱指针prev都指向自己


初始化后返回链表哨兵位

图示





---------------------------------------------------------------------------------------------



LTPrint函数 -- 打印双向链表各结点数据域数据

assert断言头指针（哨兵位地址）不为空


创建结点指针cur进行遍历


使用while循环进行遍历打印

图示

测试 -- LTPrint函数





---------------------------------------------------------------------------------------------



LTPushBack函数 -- 向链表尾部插入一个结点（尾插）

assert断言头指针（哨兵位地址）不为空


通过哨兵位配合前驱指针prev获得尾结点地址


调用BuyLTNode函数为尾插操作创建尾插结点newnode

将尾插结点和原尾部结点连接

将尾插结点和哨兵位进行连接

图示

测试 -- LTPushBack函数





---------------------------------------------------------------------------------------------



LTPopBack函数 -- 删除链表尾部结点（尾删）

assert断言头指针(哨兵位地址)不为空和双向链表不为空链表


通过哨兵位的前驱指针prev获得尾结点tail，
再通过尾结点tail获得倒数第二个结点tailPrev


释放（删除）尾结点tail

让倒数第二个结点tailPrev成为新的尾结点，
为保持循环，把tailPrev和哨兵位连接起来

图示

测试 -- LTPopBack函数





---------------------------------------------------------------------------------------------



LTPushFront函数 -- 向链表头部插入一个结点（头插）

assert断言头指针（哨兵位地址）不为空


调用BuyLTNode函数为头插操作创建头插结点newnode


创建一个first指针保存原本第一个结点地址

哨兵位后继指针next指向头插结点newnode，
头插结点newnode前驱指针prev指向哨兵位

头插结点newnode后继指针next指向原本头结点first，
原本头结点first前驱指针prev指向头插结点newnode

图示

测试 -- LTPushFront函数





---------------------------------------------------------------------------------------------



LTPopFront函数 -- 删除链表头部结点（头删）

assert断言头指针(哨兵位地址)不为空和双向链表不为空链表


通过哨兵位后继结点next获得头结点地址，
再通过first结点获得第二个结点


释放头结点first

让哨兵位后继结点next指向第二个结点second，
第二个结点的前驱指针prev指向哨兵位

图示

测试 -- LTPopFront函数





---------------------------------------------------------------------------------------------



LTSize函数 -- 求链表有效结点个数（求链表长度）

assert断言头指针（哨兵位地址）不为空


创建变量size存放链表长度，
创建结点指针cur进行遍历


使用while循环遍历链表，计算链表长度

最后返回链表长度size

图示

测试 -- LTSize函数





---------------------------------------------------------------------------------------------



LTFind函数 -- 在双向链表中查找数据域数据为x的结点地址

assert断言头指针（哨兵位地址）不为空


创建遍历指针cur，保存第一个结点地址


使用while循环进行遍历查找

未找到则返回空指针

图示

测试 -- LTFind函数





---------------------------------------------------------------------------------------------



LTInsert函数 -- 在pos结点之前插入数据域数据为x的结点

assert断言头指针（哨兵位地址）不为空


通过pos结点获得前一个结点posPrev地址


使用BuyLTNode函数为插入结点开辟空间

posPrev结点的后继指针next指向newnode，
newnode前驱指针prev指向posPrev

newnode后继指针next指向pos，
pos结点前驱指针prev指向newnode

图示

测试 -- LTInsert函数





---------------------------------------------------------------------------------------------



LTErase函数 -- 删除pos结点

assert断言删除位置结点pos不为空


保存要删除结点pos的前一个结点posPrev地址，
保存要删除结点pos的后一个结点posNext地址


释放掉pos结点

将pos前结点posPrev的后继指针指向posNext，
将pos后结点posNext的前驱指针指向posPrev

图示

测试 -- LTErase函数





---------------------------------------------------------------------------------------------



LTDestroy函数 -- 销毁链表

assert断言头指针（哨兵位地址）不为空


创建遍历指针cur，保存第一个结点地址


使用while循环遍历释放有效结点

最后释放哨兵位

图示

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

2 . 对应代码

List.h -- 双向链表头文件

#pragma once

//双向链表头文件：

//包含之后需要用到的头文件：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义双向链表数据域数据类型：
typedef int LTDataType;

//创建双向链表结点类型：
typedef struct ListNode
{
	//数据域：
	LTDataType data;

	//双向链表指针域：
	 //后继指针--指向后一个结点：
	struct ListNode* next;
	 //前驱指针--指向前一个结点：
	struct ListNode* prev;

}LTNode; //类型简称LTNode



//函数声明：

//创建链表结点--创建双向循环链表结点
//接收要插入创建结点数据域的数据
//返回创建结点的地址
LTNode* BuyLTNode(LTDataType x);

//双向链表初始化--带头双向循环链表初始化函数
//返回初始化结点的地址
LTNode* LTInit();

//打印链表--打印双向链表各结点数据域数据
//接收链表头指针（phead）
LTNode* LTPrint(LTNode* phead);

//双向链表尾插函数--向链表尾部插入一个结点（尾插）:
//接收链表头指针（phead）、要尾插进链表的值（x）
void LTPushBack(LTNode* phead, LTDataType x);

//双向链表尾删函数--删除链表尾部结点（尾删）
//接收链表头指针（phead）
void LTPopBack(LTNode* phead);

//双向链表头插函数--向链表头部插入一个结点（头插）:
//接收链表头指针（phead）、要头插进链表的值（x）
void LTPushFront(LTNode* phead, LTDataType x);

//双向链表头删函数--删除链表头部结点（头删）
//接收链表头指针（phead）
void LTPopFront(LTNode* phead);

//求链表结点个数函数--求链表有效结点个数（求链表长度）
//接收链表头指针（phead）
int LTSize(LTNode* phead);

//双向链表查找函数--在双向链表中查找数据域数据为x的结点地址
//接收链表头指针（phead）、要在链表中查找的值（x）
LTNode* LTFind(LTNode* phead, LTDataType x);

//双向链表插入函数--在pos结点之前插入数据域数据为x的结点
//接收插入位置(pos)、要插入链表的值（x）
void LTInsert(LTNode* pos, LTDataType x);

//双向链表删除函数--删除pos结点
//接收要删除结点地址（pos）
void LTErase(LTNode* pos);

//双向链表销毁函数--销毁链表
//接收要销毁链表头系欸但（phead）
void LTDestroy(LTNode* phead);

---------------------------------------------------------------------------------------------

文章来源地址https://uudwc.com/A/aYDJG

List.c -- 双向链表函数实现文件

#define _CRT_SECURE_NO_WARNINGS 1

//双向链表函数实现文件：

//包含双向链表头文件：
#include "List.h"

//函数实现：

//创建链表结点--创建双向循环链表结点
//接收要插入创建结点数据域的数据
LTNode* BuyLTNode(LTDataType x)
{
	//为创建结点开辟动态空间：
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	//检查是否开辟失败：
	if (node == NULL)
		//返回NULL，开辟失败
	{
		//打印错误信息：
		perror("malloc fail");
		//终止程序：
		exit(-1);
	}

	//把x放入结点数据域：
	node->data = x;
	//设置双向链表指针域：
	node->next = NULL;
	node->prev = NULL;
	
	//开辟成功则返回开辟空间地址
	return node;
}



//链表初始化--带头双向循环链表初始化函数
//接收链表头指针（phead）
LTNode* LTInit()
{
	//初始化时先使用BuyLTNode函数创建哨兵位：
	LTNode* phead = BuyLTNode(-1); //返回哨兵位指针

	//因为要实现循环，
	//所以让哨兵位后继指针next和前驱指针prev都指向自己：
	phead->next = phead;
	phead->prev = phead;
	//这样即使链表为空，它也是有头有尾的，即哨兵位phead

	//初始化后返回链表哨兵位：
	return phead;
}



//打印链表--打印双向链表各结点数据域数据
//接收链表头指针（phead）
LTNode* LTPrint(LTNode* phead)
{
	//assert断言头指针（哨兵位地址）不为空:
	assert(phead != NULL);

	//创建结点指针cur进行遍历：
	//指针cur应该从哨兵位（头指针）下一个结点开始
	LTNode* cur = phead->next;
	
	printf("phead <==> ");
	//因为是循环链表，不是以NULL空指针结尾
	//所以应该是当指针cur遍历回到哨兵位就终止遍历：
	while (cur != phead)
	//如果只用哨兵位，链表为空，
	//phead->next还是phead，不会进行打印
	{
		//打印数据域内容：
		printf("%d <=> ", cur->data);

		//打印完当前结点数据域数据后cur移向下个结点：
		cur = cur->next;
	}

	//打印完一个链表后换行：
	printf("\n");
}



//向链表尾部插入一个结点（尾插）:
//接收结点头指针（phead）、要尾插进链表的值（x）
void LTPushBack(LTNode* phead, LTDataType x)
{
	//assert断言头指针（哨兵位地址）不为空:
	assert(phead != NULL);

	//通过哨兵位找到尾结点：
	//因为是循环链表：
	//所以哨兵位（带头链表）的前一个结点就是尾结点
	LTNode* tail = phead->prev; 
	//调用前驱指针获得尾结点

	//调用BuyLTNode函数为尾插创建尾插结点newnode：
	LTNode* newnode = BuyLTNode(x);

	//尾插结点前驱指针prev指向原本的尾结点：
	newnode->prev = tail;
	//原本尾结点后继指针next指向尾插结点：
	tail->next = newnode;

	//尾插结点后继指针next指向头结点：
	newnode->next = phead;
	//头结点前驱指针指向尾插结点：
	phead->prev = newnode;

	//带头+双向+循环 链表:
	//对比单链表，因为有哨兵位不用考虑链表为空的情况，
	//且不需要二级指针，通过操纵哨兵位这个结构体，
	//替换用二级指针操作头指针的操作


	/*
	//第二种方法：复用LTInsert函数
	//在哨兵位前插入一个值x就是尾插了：
	LTInsert(phead, x);
	*/
}



//双向链表尾删函数--删除链表尾部结点（尾删）
//接收链表头指针（phead）
void LTPopBack(LTNode* phead)
{
	//assert断言头指针（哨兵位地址）不为空:
	assert(phead != NULL);
	
	//assert断言双向链表不是空链表：
	assert(phead->next != phead);
	//如果哨兵位的下一个结点还是哨兵位说明是空链表

	//通过哨兵位的前驱指针prev获得尾结点tail：
	LTNode* tail = phead->prev;

	//再通过尾结点tail获得倒数第二个结点tailPrev：
	LTNode* tailPrev = tail->prev;

	//释放（删除）尾结点tail：
	free(tail);

	//这时就让倒数第二个结点tailPrev成为新的尾结点
	//为保持循环，把tailPrev和哨兵位连接起来：
	tailPrev->next = phead; //tailPrev后继指针指向哨兵位
	phead->prev = tailPrev; //哨兵位前驱指针指向tailPrev

	//带头+双向+循环 链表:
	//对比单链表，这里双向链表在尾删时因为有哨兵位的存在
	//即使链表只剩一个结点，也不用进行判断单独处理进行置空
	//这一个结点删掉后，还有哨兵位存在

	/*
	//第二种方法：复用LTErase函数
	//传尾结点地址给LTErase函数即可：
	LTErase(phead->prev);
	*/
}



//双向链表头插函数--向链表头部插入一个结点（头插）：
//接收链表头指针（phead）、要头插进链表的值（x）
void LTPushFront(LTNode* phead, LTDataType x)
{
	//第二种方法：多定义一个指针
	
	//assert断言头指针（哨兵位地址）不为空:
	assert(phead != NULL);

	//调用BuyLTNode函数为头插创建头插结点newnode：
	LTNode* newnode = BuyLTNode(x);

	//创建一个first指针保存原本第一个结点地址：
	LTNode* first = phead->next;

	//哨兵位后继指针next指向头插结点newnode：
	phead->next = newnode;

	//头插结点newnode前驱指针prev指向哨兵位：
	newnode->prev = phead;

	//头插结点newnode后继指针next指向原本头结点first:
	newnode->next = first;

	//原本头结点first前驱指针prev指向头插结点newnode：
	first->prev = newnode;


	/*
	//assert断言头指针（哨兵位地址）不为空:
	assert(phead != NULL);
	
	//第一种方法：需要注意连接的顺序
	
	//调用BuyLTNode函数为头插创建头插结点newnode：
	LTNode* newnode = BuyLTNode(x);
	
	//先将头插结点的后继节点next连接上原本头结点：
	newnode->next = phead->next;
	//哨兵位的后继指针指向的就是头结点
	
	//再将原本头结点的前驱指针prev指向头插结点newnode：
	phead->next->prev = newnode;
	
	//哨兵位连接上头插节点newnode：
	phead->next = newnode;
	
	//头插结点newnode的前驱指针指向哨兵位：
	newnode->prev = phead;
	*/


	/*
	//第三种方法：复用LTInsert函数
	//在哨兵位后一个结点前插入一个值x就是头插了：
	LTInsert(phead->next, x);
	*/
}



//双向链表头删函数--删除链表头部结点（头删）
//接收链表头指针（phead）
void LTPopFront(LTNode* phead)
{
	//assert断言头指针（哨兵位地址）不为空:
	assert(phead != NULL);

	//assert断言双向链表不是空链表：
	assert(phead->next != phead);
	//如果哨兵位的下一个结点还是哨兵位说明是空链表

	//通过哨兵位后继结点next获得头结点地址：
	LTNode* first = phead->next;

	//再通过first结点获得第二个结点：
	LTNode* second = first->next;

	//释放头结点first：
	free(first);

	//让哨兵位后继结点next指向第二个结点second：
	phead->next = second;

	//第二个结点的前驱指针prev指向哨兵位：
	second->prev = phead;

	//带头+双向+循环 链表:
	//对比单链表，这里双向链表在头删时因为有哨兵位的存在
	//即使链表只剩一个结点，也不用进行判断单独处理进行置空
	//这一个结点删掉后，还有哨兵位存在
	
	/*
	//第二种方法：复用LTErase函数
	//传第一个结点地址给LTErase函数即可：
	LTErase(phead->next);
	*/
}



//求链表结点个数函数
//接收链表头指针（phead）
int LTSize(LTNode* phead)
{
	//assert断言头指针（哨兵位地址）不为空:
	assert(phead != NULL);

	int size = 0; //存放链表长度

	//创建结点指针cur进行遍历：
	//指针cur应该从哨兵位（头指针）下一个结点开始
	LTNode* cur = phead->next;

	//因为是循环链表，不是以NULL空指针结尾
	//所以应该是当指针cur遍历回到哨兵位就终止遍历：
	while (cur != phead)
		//如果只有哨兵位，链表为空，
		//phead->next还是phead，不会进行打印
	{
		++size; //遍历一遍长度+1

		//cur移向下个结点：
		cur = cur->next;
	}

	//返回链表长度：
	return size;
}



//双向链表查找函数--在双向链表中查找数据域数据为x的结点地址
//接收链表头指针（phead）、要在链表中查找的值（x）
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	//assert断言头指针（哨兵位地址）不为空:
	assert(phead != NULL);

	//创建遍历指针cur，从第一个结点开始：
	LTNode* cur = phead->next;

	//使用while循环进行遍历：
	while (cur != phead)
		//如果只有哨兵位，链表为空，
		//phead->next还是phead，不会进行打印
	{
		if (cur->data == x)
			//找到要找的值了：
		{
			return cur; //返回该值结点
		}

		//调整指针：
		cur = cur->next;
	}

	//未找到则返回空指针：
	return NULL;
}



//双向链表插入函数--在pos结点之前插入数据域数据为x的结点
//接收插入位置(pos)、要插入链表的值（x）
void LTInsert(LTNode* pos, LTDataType x)
{
	//assert断言插入位置pos不为空：
	assert(pos != NULL);

	//通过pos结点获得前一个结点posPrev地址：
	LTNode* posPrev = pos->prev;

	//使用BuyLTNode函数为插入结点开辟空间：
	LTNode* newnode = BuyLTNode(x);

	//posPrev结点的后继指针next指向newnode：
	posPrev->next = newnode;

	//newnode前驱指针prev指向posPrev:
	newnode->prev = posPrev;

	//newnode后继指针next指向pos：
	newnode->next = pos;

	//pos结点前驱指针prev指向newnode:
	pos->prev = newnode;
}



//双向链表删除函数--删除pos结点
//接收要删除结点地址（pos）
void LTErase(LTNode* pos)
{
	//assert断言删除位置结点pos不为空：
	assert(pos != NULL);

	//保存要删除结点pos的前一个结点posPrev地址：
	LTNode* posPrev = pos->prev;

	//保存要删除结点pos的后一个结点posNext地址：
	LTNode* posNext = pos->next;

	//释放掉pos结点：
	free(pos);

	//将pos前结点posPrev的后继指针指向posNext：
	posPrev->next = posNext;

	//将pos后结点posNext的前驱指针指向posPrev：
	posNext->prev = posPrev;
}



//双向链表销毁函数--销毁链表
//接收要销毁链表头系欸但（phead）
void LTDestroy(LTNode* phead)
{
	//assert断言头指针（哨兵位地址）不为空:
	assert(phead != NULL);

	//创建遍历指针cur，从第一个结点开始：
	LTNode* cur = phead->next;

	//使用while循环进行遍历释放：
	while (cur != phead)
	{
		//释放前先存储下一个结点地址：
		LTNode* next = cur->next;

		//释放当前结点：
		free(cur);

		//调整指针：
		cur = next;
	}
	
	//删除完有效结点后，最后再释放哨兵位：
	free(phead);
}

---------------------------------------------------------------------------------------------

Test.c -- 双向链表测试文件

#define _CRT_SECURE_NO_WARNINGS 1

//双向链表函数测试文件：

//包含双向链表头文件：
#include "List.h"

//测试函数--
//LTInit、LTPushBack、LTPrintf函数
void TestList1()
{
	//初始化一个双向链表：
	LTNode* plist = LTInit();

	//初始化后使用尾插函数插入数据：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPushBack(plist, 5);
	  
	//打印当前双向链表：
	LTPrint(plist);
}


//测试函数--LTPopBack函数
void TestList2()
{
	//初始化一个双向链表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函数插入数据：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印当前双向链表：
	LTPrint(plist);

	//进行尾删：
	LTPopBack(plist);
	//打印当前双向链表：
	LTPrint(plist);

	//进行尾删：
	LTPopBack(plist);
	//打印当前双向链表：
	LTPrint(plist);

	//进行尾删：
	LTPopBack(plist);
	//打印当前双向链表：
	LTPrint(plist);
}


//测试函数--LTPushFront函数
void TestList3()
{
	//初始化一个双向链表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函数插入数据：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印当前双向链表：
	LTPrint(plist);

	//进行头插：
	LTPushFront(plist, 1000);
	//打印当前双向链表：
	LTPrint(plist);
}


//测试函数--LTPopFront函数
void TestList4()
{
	//初始化一个双向链表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函数插入数据：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印当前双向链表：
	LTPrint(plist);

	//进行头删：
	LTPopFront(plist);
	//打印当前双向链表：
	LTPrint(plist);
}


//测试函数--LTSize函数
void TestList5()
{
	//初始化一个双向链表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函数插入数据：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印当前双向链表：
	LTPrint(plist);

	//计算链表长度：
	int size = LTSize(plist);
	//打印当前双向链表：
	printf("链表长度为：%d", size);
}


//测试函数--LTFind函数
void TestList6()
{
	//初始化一个双向链表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函数插入数据：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印当前双向链表：
	LTPrint(plist);

	//使用查找函数：
	LTNode* find = LTFind(plist, 2);
	//打印找到的地址
	printf("0x%xn", find);
}


//测试函数--LTInsert函数
void TestList7()
{
	//初始化一个双向链表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函数插入数据：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印当前双向链表：
	LTPrint(plist);

	//使用插入函数：
	LTInsert(plist->next->next, 100);
	//打印当前双向链表：
	LTPrint(plist);
}


//测试函数--LTErase函数
void TestList8()
{
	//初始化一个双向链表：
	LTNode* plist = LTInit();
	//初始化后使用尾插函数插入数据：
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	//打印当前双向链表：
	LTPrint(plist);

	//使用删除函数：
	LTErase(plist->next->next);
	//打印当前双向链表：
	LTPrint(plist);
}

//主函数：
int main()
{
	//调用测试函数：
	//TestList1();
	//TestList2();
	//TestList3();
	//TestList4();
	//TestList5();
	//TestList6();
	//TestList7();
	TestList8();

	return 0;
}

【数据结构初阶】四、线性表里的链表（带头+双向+循环 链表 -- C语言实现）

引言

顺序表和链表的一些区别：

更多区别图示：

注：缓存利用率 参考 存储体系结构 以及 局部原理性

带头双向循环链表

简介：

图示：

1 . 双向链表的实现 （带头+双向+循环 链表）

（详细解释在图片的注释中，代码分文件放最后）

实现具体功能前的准备工作

图示

BuyLTNode函数 -- 创建双向循环链表结点

图示

LTInit函数 -- 带头双向循环链表初始化函数

图示

LTPrint函数 -- 打印双向链表各结点数据域数据

测试 -- LTPrint函数

LTPushBack函数 -- 向链表尾部插入一个结点（尾插）

图示

测试 -- LTPushBack函数

LTPopBack函数 -- 删除链表尾部结点（尾删）

图示

测试 -- LTPopBack函数

LTPushFront函数 -- 向链表头部插入一个结点（头插）

图示

测试 -- LTPushFront函数

LTPopFront函数 -- 删除链表头部结点（头删）

图示

测试 -- LTPopFront函数

LTSize函数 -- 求链表有效结点个数（求链表长度）

图示

测试 -- LTSize函数

LTFind函数 -- 在双向链表中查找数据域数据为x的结点地址

图示

测试 -- LTFind函数

LTInsert函数 -- 在pos结点之前插入数据域数据为x的结点

图示

测试 -- LTInsert函数

LTErase函数 -- 删除pos结点

图示

测试 -- LTErase函数

LTDestroy函数 -- 销毁链表

图示

2 . 对应代码

List.h -- 双向链表头文件

List.c -- 双向链表函数实现文件

Test.c -- 双向链表测试文件

【数据结构初阶】四、线性表里的链表（带头+双向+循环链表 -- C语言实现）

注：缓存利用率参考存储体系结构以及局部原理性

1 . 双向链表的实现
（带头+双向+循环链表）