【数据结构】双向链表

1.链表分类

我们是知道单链表的，但是你知道他的全称是什么吗？

单向不循环不带头链表；

好！！！问题就来了，什么是单向，什么是循环，什么是带头

链表的分类很多，但大致就分为集中，

带头不带头，单向不单向，循环不循环。

1.1单向不单向

图解：

图例说明：单向在上，双向在下

单向可以理解为，链表只能从一边遍历，一旦遍历无法回到上一个结点 双向可以理解为，一个结点存放着下一个结点的地址，也存放着上一个结点的地址，可以双向访问

1.2循环不循环

图解

循环可以理解为尾结点的存储的下一个结点的地址是头结点或者第一个结点，也就是说循环链表指向不为NULL;

1.3带头不带头

图解：

虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表

1. ⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦ 结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。 2. 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头 双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实 现反⽽简单了，后⾯我们代码实现了就知道了。

2.双向链表（双向带头循环链表）

图解：

接下来我们就一步步实现双向链表

我们可以看下总体头文件，了解一下具体双向链表有什么函数接口。

附加：头文件

包括，定义结构，初始化，销毁，头插，尾插，头删，尾删，指定位置后的插入，删除指定位置结点

#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> //定义双向链表节点的结构 typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode; //为了保持接口的一致性，优化接口都为一级指针 //初始化 //void LTInit(LTNode** pphead); LTNode* LTInit(); //销毁 void LTDesTroy(LTNode** pphead); void LTDesTroy2(LTNode* phead);//传一级，需要手动将plist置为NULL void LTPrint(LTNode* phead); //插入 //第一个参传一级还是二级，要看pphead指向的节点会不会发生改变 //如果发生改变，那么pphead的改变要影响实参，传二级 //如何不发生改变，pphead不会影响实参，传一级 void LTPushBack(LTNode* phead, LTDataType x); void LTPushFront(LTNode* phead, LTDataType x); //删除 void LTPopBack(LTNode* phead); void LTPopFront(LTNode* phead); bool LTEmpty(LTNode* phead); LTNode* LTFind(LTNode* phead, LTDataType x); //在pos位置之后插入节点 void LTInsert(LTNode* pos, LTDataType x); //删除指定位置节点 void LTErase(LTNode* pos);

2.1链表的定义及其初始化

代码

//双向链表的定义
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LT;
//初始化
LT* LTinit()
{
	LT* phead = LTBuyNode(-1);
	return phead;

}

链表的定义：对int重命名以便于后续的修改，定义结构体中的下一个和前一个的指针。

链表初始话，头结点也就是哨兵位。向系统申请结点。

2.2申请结点

代码

LT* LTBuyNode(LTDatatype x)
{
	LT* newnode = (LT*)malloc(sizeof(LT));
	if (newnode == NULL);
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;

}

解析：开辟一个新空间头地址给newnode。如果开辟失败，打印错误信息，开辟成功，赋值x给data，前一个地址和后一个结点地址指向本身。

2.3尾插

代码

void PushBack(LT* phead, LTDatatype x)
{
	LT* newnode = LTBuyNode(x);
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;

}

图解

2.4头插

代码

void PushFront(LT* phead, LTDatatype x)
{
	LT* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
	

}

图解：

2.5头删

void PopFront(LT* phead)
{
	LT* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}

图解：

2.6 尾删

void PopBack(LT* phead)
{
	LT* del = phead->prev;
	LT* tail = del->prev;
	phead->prev = tail;
	tail->next = phead;
	del = NULL;
}

图解

2.7 pos后插入

void LTInsert(LT* pos, LTDatatype x)
{
	LT* newnode = LTBuyNode(x);
	newnode->prev = pos;
	newnode->next = pos->next;
	pos->next->prev = newnode;
	pos->next = newnode;

}

2.8指定结点删除

void LTErase(LT* pos)
{
	
	pos->prev = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;

	
}

2.9结点销毁

void LTDestory(LT* phead)
{
	assert(phead);
	LT* pcur = phead->next;
	while (pcur != phead)
	{
		free(pcur);
		pcur = pcur->next;

	}
	free(phead);
	phead = pcur = NULL;

}

3.顺序表和链表对比解析