数据结构：双向链表

目录

一、链表的分类

二、双向链表

2.1 双向链表的结构

2.2 双向链表的实现

2.2.1 头文件

2.2.2 各个功能的实现

初始化

头部/尾部数据插入与删除

    头插

    尾插

    头删

    尾删

 指定位置的插入与删除

 查找数据

打印链表

 销毁链表

 三、顺序表和链表的优缺点分析

---

一、链表的分类

    链表的结构有很多种，以下情况组合就有8中链表结构：

     虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表，上一篇我们已经讲了单链表，今天就来了解一下双向链表并将其实现。

1.无头单向非循环链表：结构简单，⼀般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

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

二、双向链表

2.1 双向链表的结构

     这里的“带头”跟“头节点”是两个概念，带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨 的” ，存在的意义： 遍历循环链表避免死循环。

2.2 双向链表的实现

2.2.1 头文件

   还是老样子，在头文件里写出我们需要功能的函数名以及结构体的成员。

typedef int LTDataType;
typedef struct ListNode
{
 struct ListNode* next; //指针保存下⼀个节点的地址 
 struct ListNode* prev; //指针保存前⼀个节点的地址 
 LTDataType data;
}LTNode;
 
//链表初始化
void LTInit(LTNode** pphead);
//销毁链表
void LTDestroy(LTNode* phead);
//打印链表
void LTPrint(LTNode* phead);
//尾部插入删除数据/头部插入删除数据
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在指定位置之后插⼊数据 
void LTInsert(LTNode* pos, LTDataType x);
//删除指定位置数据
void LTErase(LTNode* pos);
//查找数据
LTNode *LTFind(LTNode* phead,LTDataType x);

2.2.2 各个功能的实现

初始化

    初始化时，我们需要创造一个“哨兵位”，而且后面每一次插入数据都需要先申请一段空间，需要写一个“creat”这样的函数。

LTNode* creat(LTDataType x)
{
	LTNode* a = (LTNode*)malloc(sizeof(LTNode));
	a->data = x;
	a->next = a;
	a->bef = a;
	return a;
}
void LTInit(LTNode** pphead)
{
	*pphead = creat(-1);
}

头部/尾部数据插入与删除

    头插

    注意这里的头插，是指在“哨兵位”后的第一个节点插入，不是在“哨兵位”之前插入。

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* a = creat(x);
	a->next = phead->next;
    a->bef = phead;
	phead->next = a;
	phead->next->bef = a;
}

    尾插

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* a=creat(x);
	a->bef = phead->bef;
	phead->bef->next = a;
	phead->bef = a;
	a->next = phead;
}

    头删

    与头插一个道理，别把“哨兵位”删除了

void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* a = phead->next;
	phead->next = a->next;
	a->next->bef = phead;
	free(a);
	a = NULL;
}

    尾删

void LTPopBack(LTNode* phead)
{
	assert(phead&&phead->next!=phead);
	LTNode* a = phead->bef;
	a->bef->next = phead;
	phead->bef = a->bef;
	free(a);
	a = NULL;
}

 指定位置的插入与删除

void LTInsert(LTNode* pos, LTDataType x)//插入
{
	LTNode* a = creat(x);
	pos->next->bef = a;
	a->next = pos->next;
	pos->next = a;
	a->bef = pos;
}
void LTErase(LTNode* pos)//删除
{
	pos->bef->next = pos->next;
	pos->next->bef = pos->bef;
	free(pos);
	pos = NULL;
}

 查找数据

    查找前先断言一下是否为空指针或者是否只有一个“哨兵位”节点，这样能够在出错时快速发现。

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead && phead->next != phead);
	LTNode* a = phead->next;
	while (a != phead)
	{
		if (a->data = x)
			return a;
		a = a->next;
	}
	return NULL;
}

打印链表

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

 销毁链表

void LTDestroy(LTNode* phead)
{
	LTNode* a = phead->next;
	while (a != phead)
	{
		LTNode* b = a->next;
		free(a);
		a =b;
	}
	free(phead);
	phead = NULL;
}

释放完后的指针不要忘了指向空指针，避免造成野指针。 

     最后还是那句话，写完不要忘记测试，只有测试了才会知道自己的代码是否有误。

三、顺序表和链表的优缺点

    顺序表和链表各有各的优缺点，没有高低之分，根据不同的需求运用在不同的场景

---

     本篇的内容就到这里了，希望对各位有帮助，如果有错误欢迎指出。