数据结构：双向链表-EW帮帮网

一，概念及结构

带头链表中的头结点，不存储任何有效数据，只是用来占位置，叫哨兵位。

在前面单链表中，有时候会把第一个结点表述为头结点，这个表述实际上是错误的，只是为了方便大家理解才会那么叫。

补充：链表的分类

组合起来共八种结构。

1，单向或者双向

2，带头或者不带头

3，循环或者不循环

二，双向链表特点

双向不循环链表：

1，双向链表可以通过结点反向访问到上一个结点，存在指向上一个结点的指针。

2，带头双向链表为空链表的时候，头结点的两个指针都指向NULL。

3，带头结点的双向链表为非空链表的时候。

头结点的前驱指针指向NULL，后驱指针指向第一个结点。

最后一个结点的前驱指针指向前一个结点，后驱结点的指针指向NULL。

其他结点的前驱指针指向前一个结点，后驱指针指向后一个结点。

双向循环链表：

1，双向链表可以通过结点反向访问到上一个结点，存在指向上一个结点的指针。

2，带头双向链表为空链表的时候，头结点的两个指针都指向NULL。

3，带头结点的双向链表为非空链表的时候。

头结点的前驱指针指向最后一个结点，后驱指针指向第一个结点。

最后一个结点的前驱指针指向前一个结点，后驱结点的指针指向第一个结点。

其他结点的前驱指针指向前一个结点，后驱指针指向后一个结点。

三，双向链表的实现

1，定义

struct ListNode
{
  int data;
  struct ListNode*next;
  struct ListNode*prev;
}

注意：双向链表为空的情况下只有一个哨兵位，如果连哨兵位结点都没有的话，这不是双向链表而是单链表。

2，申请结点

方法和单链表类似，只不过多了一个前驱指针。

LTNode* buyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
 }

3，初始化

首先，我们有一个问题就是在双向链表初始化当中我们应该传什么参数？

我们可以通过以下两端代码对比选择

// 假设这样声明初始化函数
void LTInit(LTNode* phead) {
    phead = buyNode(-1); // 这只是修改了函数内部的副本phead
    // 函数结束后，副本phead被销毁，外部的实参没有任何变化
}

int main() {
    LTNode* plist = NULL; // 头指针初始为NULL
    LTInit(plist);   // 试图初始化
    // ... 此时 plist 仍然是 NULL！后续操作会出问题（如访问NULL->next导致崩溃）
    return 0;
}

上述代码就是只传一级指针，我们可以发现LTInit(plist)是将plist的值拷贝给phead，由于我们传的是一级指针，相当于函数内部phead被赋值为了plist的地址，函数结束后，phead销毁但是plist的内容未发生任何变化。

那么我们来看一下传二级指针的情况

// 正确的初始化函数
void LTInit(LTNode** pphead) { // 接收头指针的地址
    *pphead = buyNode(-1); // 通过解引用，直接修改外部头指针指向的内容
}

int main() {
    LTNode* plist = NULL; // 头指针初始为NULL
    LTInit(&plist);       // 传递头指针的地址
    // 现在 plist 已经指向新创建的哨兵节点了！初始化成功。
    return 0;
}

调用 LTInit(&plist)，相当于把 plist 的地址传递给了形参 pphead。现在 pphead 是一个指向 plist 的指针。
在函数里，*pphead 就是 plist 本身。执行 *pphead = buyNode(-1); 就相当于直接执行 plist = buyNode(-1);
函数结束后，虽然形参pphead已经被销毁了，但它已经通过解引用完成了使命，函数外部的plist已经成功被修改。

但是，我们还有一种不传参的方法，只需要在函数内部返回新创建的头指针即可实现，就无需使用二级指针了

// 另一种初始化方式：通过返回值
LTNode* LTInit() {
    LTNode* phead = buyNode(-1); // 创建哨兵节点
    return phead; // 返回这个节点的地址
}

int main() {
    LTNode* plist = LTInit(); // 用返回值直接给plist赋值
    // 初始化成功
    // ... 其他操作
    return 0;
}

所以我们的初始化代码为

LTNode* LTInit()
{
	LTNode* phead = buyNode(-1);
	return phead;
}

4，销毁

销毁链表的参数需要一级指针还是二级指针？

这里销毁链表其实只需要接受一级指针就行，因为销毁链表的本质其实就是释放所有结点所占用的内存，我们不需要再去改变头指针本身的值，只需要改变其指向的内存即可。

void LTDesTroy(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}

注意：最后一定要把头结点的指针置为空，否则会出现悬空指针的问题，即在所有结点都被释放以后，头指针仍然指向那块已经被释放的内存地址，如果后续再去调用这个头指针，就会出现未定义行为。

5，遍历以及打印

双向链表是循环结构，我们该如何遍历呢？

我们同样可以借助循环来遍历每个结点，打印其中的数据，只不过循环的终止条件要发生改变为pcur！=phead，避免死循环。

void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;//指向的哨兵位的下一个结点才是真正的开始
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

6，尾插

尾插的时候我们要考虑链表为空或非空的情况

（1）链表为空的时候，我们要将哨兵位的后驱和前驱指针都指向新结点，而新结点的前驱指针和后驱指针也都要指向头结点。

注意：指向哨兵位的指针是不会发生变化的。

（2）链表不为空的时候，我们要将原链表尾结点的后驱指针指向新结点，同时头结点的前驱指针指向尾插的新结点，尾插的新结点的前驱结点要指向原链表的尾结点，后驱结点要指向头结点。

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyNode(x);
	//newnode phead->prev(尾结点） phead
	newnode->prev = phead->prev;//phead->prev指向的就是原链表的尾结点
	newnode->next = phead;

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

7，头插

注意：头插这里的头指的是第一个结点而不是头结点（哨兵位）。

头结点的后驱指针要指向新结点，第一个结点的前驱指针要指向新结点，而新结点的前驱指针要指向头结点，同时新结点的后驱指针要指向第一个结点。

注意头插函数是可以对空链表进行操作的。

void LTPushFront(LTNode* phead,LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyNode(x);
	newnode->prev = phead;
	newnode->next = phead->next;
	phead->next->prev= newnode;
	phead->next = newnode;
}

8，尾删

尾删的思路也很简单，就是先将尾结点保存下来，将原链表的倒数第二个结点的next指针指向头结点，头结点的prev指针指向原链表的倒数第二个结点，同时原链表的尾结点要释放掉，且将保存尾结点的指针置空。

在使用尾删之前，我们先要找一个函数判断一个带哨兵节点的双向循环链表是否为空。

void LTEmpty(LTNode* phead)
{
	assert(phead);//确保传入指针不是空指针
	return phead->next == phead;//判断哨兵位的下一个结点是否指向其自身，返回一个布尔值
}

有了判空函数后就可以进行我们的尾删操作了。

void LTPopBack(LTNode* phead)
{
	//断言链表不为空。如果链表为空（即 LTEmpty(phead) 返回 true），!true 就是 false，会导致 assert(false) 触发，程序终止
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	phead->prev = del->prev;
	del->prev->next = phead;
	free(del);
	del = NULL;
}

9，头删

注意：这里的头删的头指的是第一个结点，而非头结点（哨兵位）。

头删的思路以比较简单，首先要将第二个结点保存下来，然后将头结点的后驱指针指向第二个结点，第二个结点的前驱指针指向头指针，再将第一个结点的内存释放，同时指针置空。

void LTPopFront(LTNode* phead)
{
	assert(!LTEmpty(phead));
	LTNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}

10，在指定位置之后插入数据

首先我们要找到该位置，创建一个新的结点，将该新结点的前驱和后驱指针分别指向前一个结点和后一个结点，与此同时pos位置结点的后驱指针要指向新结点，原来pos位置的下一个结点的前驱指针要指向新结点。

void LTInsert(LTNode* pos,LTDataType x)
{
	assert(pos);
	LTNode* newnode = buyNode(x);
	newnode->prev = pos;
	newnode->next = pos->next;

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

11，删除指定位置的结点

我们先要确定要删除的结点位置，将该结点的前一个结点的next指针指向该结点的后一个结点，同时该结点的后一个结点的prev指针要指向该结点的前一个结点。

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

12，查找数据

遍历链表，判断每个结点的数据是否与要查找的数据一致。

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

13，总结

头文件：

#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;

//
//void LTInit(LTNode* pphead);
//双向链表的初始化   plist  &plist  
//void LTInit(LTNode** pphead);//传地址：形参的改变影响实参
LTNode* LTInit();
//为了保持接口一致性，建议统一参数，都传一级：手动将实参置为NULL
void LTDesTroy(LTNode* phead);
//传二级：未保持接口一致性
//void LTDesTroy(LTNode** pphead);
bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);

.c文件：

#include"TSList.h"
LTNode* buyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
 }

LTNode* LTInit()
{
	LTNode* phead = buyNode(-1);
	return phead;
}

void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;//指向的哨兵位的下一个结点才是真正的开始
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyNode(x);
	//newnode phead->prev(尾结点） phead
	newnode->prev = phead->prev;//phead->prev指向的就是原链表的尾结点
	newnode->next = phead;

	phead->prev->next = newnode;//phead->prev->next指针指的是尾结点的next指针
	phead->prev = newnode;
}
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
void LTPushFront(LTNode* phead,LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyNode(x);
	newnode->prev = phead;
	newnode->next = phead->next;
	phead->next->prev= newnode;
	phead->next = newnode;
}
void LTPopBack(LTNode* phead)
{
	//断言链表不为空。如果链表为空（即 LTEmpty(phead) 返回 true），!true 就是 false，会导致 assert(false) 触发，程序终止
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	phead->prev = del->prev;
	del->prev->next = phead;
	free(del);
	del = NULL;
}
void LTPopFront(LTNode* phead)
{
	assert(!LTEmpty(phead));
	LTNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}

void LTInsert(LTNode* pos,LTDataType x)
{
	assert(pos);
	LTNode* newnode = buyNode(x);
	newnode->prev = pos;
	newnode->next = pos->next;

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

void LTErase(LTNode* pos)
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	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;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

四，顺序表与链表的分析

注意：（1）对于顺序表来说，其底层是数组，尾插的时间复杂度是O（1），头插/指定位置之后插入的时间复杂度为O（N）。

（2）对于链表来说，在指定位置之前插入数据的时间复杂度为O（n），在指定位置之后插入数据的时间复杂度为O（1）。

数据结构：双向链表