数据结构——双链表

(一).双链表的概念和结构

首先我们来认识一下什么是双链表呢？

双链表其实就是在单链表的基础上增加了一个前驱指针用来存储上一个节点的地址，同样这次在双链表中我们也增加了哨兵位，也就是头节点，但在双链表的实现其实比单链表简单得多，只要对单链表掌握的通透那么双链表就不在话下，接下来我们通过一张图纸来了解双链表。

双链表的结构就是如图所示了，带头双链表中头里面是不存放数据的，只有两个存放地址的指针，这里我们了解了双链表的概念之后我们来进行一下代码实现。 

(二).双链表的实现

在进行双链表代码实现之前我们来先进行结构体的创建，

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

这里注意每个节点有两个指针，就是指向上一个节点地址和指向下一个节点的地址的指针。 

2.1双链表的初始化

//申请新节点
LTNode* LTbuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	while (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

// 双链表的初始化
void LTInit(LTNode** phead)
{
	//给双链表创建一个哨兵位
	*phead = LTbuyNode(-1);//由于哨兵位里面不存放任何地址所以传一个非节点值过去
}

这里我们要注意的是创建的哨兵位要让它的的next和prev指向自己让链表循环起来。

2.2双链表的打印

//双链表的打印
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)//这里哨兵位里面是没有存放任何值的，由于双链表是循环链表所以让它循环到
		                 //等于哨兵位是就退出
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

2.3双链表的尾插

//申请新节点
LTNode* LTbuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	while (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}
//双链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	LTNode* newnode = LTbuyNode(x);
	newnode->prev = phead->prev;
	newnode->next = phead;

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

}

这里面我们需要注意的是phead->prev->next = newnode和phead->prev = newnode;不能交换顺序因为如果交换了的话phead->prev就被改变了，前面的一个式子就不成立了。 

2.4双链表的头插

//双链表的头插
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;
}

进行头插之前我们要先判断是否存在除了哨兵位以外的节点。 

2.5双链表的尾删

//双链表的尾删
void LTPopBack(LTNode* phead)
{
	assert(phead&&phead->next);
	LTNode* del = phead->prev;

	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

这里我们需要注意的是尾删必须要断言节点必须存在，我们可以用del来代替phead->prev这样能降低代码复杂性让我们更容易理解。

2.6双链表的头删

//双链表的头删
void LTPopFront(LTNode* phead)
{
	//断言双链表和哨兵位的下一个节点不为空
	assert(phead && phead->next);
	LTNode* del = phead->next;
	phead->next = del->next;
	del->next = phead;
}

2.7双链表中数据的查找

//双链表中节点的查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

 这里查找要遍历整个链表，当走到哨兵位就退出。

2.8双链表中在pos位置之后插⼊数据

//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTbuyNode(x);
	newnode->prev = pos;
	newnode->next = pos->next;

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

 这里同样又和上面一样的问题，最下面的两个式子的顺序不能改变。

2.9双链表中删除pos节点

//删除pos节点
void LTErase(LTNode* pos)
{
	//理论上来说pos节点是不能等于哨兵位的，但没有参数phead，无法校验
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

2.10双链表的销毁

//双链表的销毁
void LTDestroy(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

注意：理论上LTErase和LTDestroy要用二级指针来接收，因为我们要用但是为了让实参影响实参，但我们为了保持接口的一致性，所以才传的一级指针，传一级指针问题是，当形参phead置为NULL后，实参plist不会置为NULL，我们需要手动将plist置为NULL ，将plist手动置为NULL的前提是我们后面不使用plist了。

(三).代码汇总

List.h:

#pragma once
//双链表的实现
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//双链表是节点是由指向上一节点指针+存储的数据+指向下一节点的指针组成
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;


//双链表的打印
void LTPrint(LTNode* phead);
//双链表的初始化
void LTInit(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);

//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
//双链表的销毁
void LTDestroy(LTNode* phead);

List.c:

#include"List.h"
//双链表的打印
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)//这里哨兵位里面是没有存放任何值的，由于双链表是循环链表所以让它循环到
		                 //等于哨兵位是就退出
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

//申请新节点
LTNode* LTbuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	while (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

// 双链表的初始化
void LTInit(LTNode** phead)
{
	//给双链表创建一个哨兵位
	*phead = LTbuyNode(-1);//由于哨兵位里面不存放任何地址所以传一个非节点值过去
}
//双链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	LTNode* newnode = LTbuyNode(x);
	newnode->prev = phead->prev;
	newnode->next = phead;

	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&&phead->next);
	LTNode* del = phead->prev;

	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

//双链表的头删
void LTPopFront(LTNode* phead)
{
	//断言双链表和哨兵位的下一个节点不为空
	assert(phead && phead->next);
	LTNode* del = phead->next;
	phead->next = del->next;
	del->next = phead;
}

//双链表中节点的查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTbuyNode(x);
	newnode->prev = pos;
	newnode->next = pos->next;

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

//删除pos节点
void LTErase(LTNode* pos)
{
	//理论上来说pos节点是不能等于哨兵位的，但没有参数phead，无法校验
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

//双链表的销毁
void LTDestroy(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

test.c: 

#include"List.h"

void Listtest01()
{
	LTNode* plist = NULL;
	LTInit(&plist);

	LTPushBack(plist, 1);
	LTPrint(plist);
	LTPushBack(plist, 2);
	LTPrint(plist);
	LTPushBack(plist, 3);
	LTPrint(plist);
	LTPushBack(plist, 4);
	LTPrint(plist);
	LTPushFront(plist, 66);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTNode* find=LTFind(plist, 2);
	if (find == NULL)
	{
		printf("没找到！\n");
	}
	else
	{
		printf("找到了！\n");
	}
	LTInsert(find, 99);
	LTPrint(plist);
	LTErase(find);
	LTPrint(plist);
	LTDestroy(plist);
	//free(plist);
	//plist = NULL;
	LTPrint(plist);

}




int main()
{
	Listtest01();
	return 0;
}

(四).总结

上面就是双链表的实现全过程了，总的来说双链表在我们掌握了单链表的基础上我们就非常容易实现了，双链表可能在我们就凭空去想的话可能很难想出，但只要我们多去画画图，就会发现它的指向为题很简单，我们先通过画图理清代码思路去实现起来就so easy了，好了上面就是我要与大家分享的关于双链表的全部内容。

希望各位大佬在评论区指正我写的不对的地方我一定会认真改正，大家一起加油！