【数据结构】双向链表超详细（含：何时用一级指针或二级指针；指针域的指针是否要释放）

一、简介

二. 双链表的实现

1.准备工作及其注意事项

1.1 先创建三个文件

1.2 注意事项：帮助高效记忆

1.3 关于什么时候用一级指针接收，什么时候用二级指针接收？

1.4 释放节点时，要将节点地址置为NULL，难道节点内部的指针域的指针就不用置为 NULL吗？

2.双链表的基本功能接口

2.1 初始化哨兵位

2.2 链表的创建新节点接口

2.3 打印

3. 插入接口

3.1 尾插法

3.2 头插法

3.3 在 pos 位置之后插入数据

4. 查找

5.删除接口

5.1 尾删法

5.2 头删法

5.3 删除 pos 位置的数据

6. 销毁链表接口

6.1 二级指针版

6.2 一级指针版

7. 总代码概览

List.h

List.c

test.c

三. 顺序表和双向链表的优缺点分析

一、简介

单向链表在解决那些需要大量查找前趋节点的问题时，效率较为低下，因为单向链表适合“从前往后”查找，并不适合“从后往前”查找。

（若想要看单链表，可以点击跳转：【数据结构】单向链表实现超详细）

如果要提高链表的查找效率，那双向链表（双链表）无疑是首选。

双向链表：即为字面上的意思是“双向”的链表，如下图所示。

双向指各个节点之间的逻辑关系是双向的，该链表通常有一个头节点 -- 称为 哨兵位 。
概念: 当链表中只有哨兵位节点的时候，我们称该链表为空链表，即哨兵位是不能删除的
从上图还可以看出，双向链表中每个节点包括一下3个部分，分别是：
指针域（前驱节点 prev ）、
数据域（用于存储数据元素 data）
指针域（后继节点 next)。

二. 双链表的实现

1.准备工作及其注意事项

1.1 先创建三个文件

解释这三个文件的作用
1、头文件List.h 是来声明接口函数，定义链表，将几个公共用到的库函数集合起来
2、源文件List.c 是用来具体实现接口
3、源文件test.c 用于接口的测试工作，即具体的使用场景

1.2 注意事项：帮助高效记忆

1. 传递指针，都要断言不能为 NULL ，指针不能为空：assert(phead);
2. 存在关系到前趋节点prev 或后继节点next 的情况，

可以直接定义变量 Prev = .... Next = .... 便于理清思路，不易乱
3. 所有的删除接口都需要断言链表不能只有哨兵位： assert(phead->next != phead);
4. 尾删法: 记得双链表的找尾不像单链表需要循环去找尾！！ptail = phead->prev;

5. 初始化创建头节点：推荐使用调用创建节点接口的方法
5. 销毁接口：推荐使用传一级指针的方法

1.3 关于什么时候用一级指针接收，什么时候用二级指针接收？（不看水话，可以直接看下面总结部分）

（有点水话，实在不明白思路的可以看一下详细解说的 ”水话“）

在 单向链表 中，有一个指向第一个节点的指针 plist，由于头插法等操作，可能会改变第一个节点，则 plist 要对应进行更新，而要想直接改变一个变量（plist是指针变量）的值，需要传地址，plist 的 &plist 是一级指针的地址，就要用二级指针来接收

在 双向链表 中，存在头节点 head ，即哨兵位，哨兵是不用进行改变本身这个节点的地址的！！

那就有铁铁要问了，不是还要改变头节点 head（哨兵位）的指向，要指向第一个节点或尾节点吗？

回答：因为我们要改变的是 双链表节点结构 中的 结构体成员变量：prev 和 next ，改变结构体的成员变量 只需要利用结构体指针 p->prev = .... 或 p->next = .... 就达到修改双链表节点指向问题了，而你本身并不需要改变一个节点的地址 p

总结

总结：修改双链表节点的指向，是通过 修改节点结构体内部的两个成员变量来实现的，只需要用到结构体指针（即该节点的地址 p），找到两个成员变量，即可完成修改，因而传递一级指针就好，不用像单链表那样还要传递一级指针的地址

1.4 释放节点时，要将节点地址置为NULL，难道节点内部的指针域的指针就不用置为 NULL吗？

回答：不用因为节点的空间已经还给操作系统了那个指针域的指针所占据的空间也还回去了操作系统后续分配内存就会把那块空间覆盖掉就不会又啥影响

2.双链表的基本功能接口

2.1 初始化哨兵位

初始化哨兵位第一种方法：传入指针，进行"加工" 成哨兵位

// 初始化一个哨兵位：
void LTInit(LTNode** pphead)
{
	*pphead = (LTNode*)malloc(sizeof(LTNode));
	// 开辟空间是否成功的判断：一般malloc不会失败，失败证明内存不够了，写下面的证明算是好习惯，不写一般没问题
	if (*pphead == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	(*pphead)->data = -1;
	(*pphead)->next = (*pphead)->prev = *pphead; // 哨兵位初识化，两个指针都指向自己
}

初始化哨兵位第二种方法：直接一个函数生成一个哨兵位，返回哨兵位就好，不用传指针

LTNode* LTInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	// 开辟空间是否成功的判断
	if (phead == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	phead->data = -1; // data 随便定，反正哨兵位data无效
	phead->next = phead->prev = phead;
	return phead;
}

初始化哨兵位第二种方法的2.0 版本：因为哨兵位的初始化和 2.2 创建新新节点的方法一样，可以合并调用


LTNode* LTInit_2()
{
	LTNode* phead = LTCreatNode(-1);
	return phead;
}

2.2 链表的创建新节点接口

// 创建新节点
LTNode* LTCreatNode(LTDataType x)
{
	LTNode* newNode = (LTNode*)malloc(sizeof (LTNode));
	if (newNode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newNode->data = x;
	newNode->prev = newNode->next = newNode; // 都是 指向自己
	return newNode;
}

2.3 打印

双链表的打印
和单链表打印一样，都需要循环，但是结束条件不一样
单链表以 pcur = NULL 为结束条件，双链表是一种循环链表，头尾相连，不会有 pcur = NULL 的情况
正解：既然哨兵位无有效数据，同时循环一轮还是回到头（哨兵位），干脆：while (pcur != phead)


void LTPrint(LTNode* phead)
{
	assert(phead);// 哨兵位不能为空
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

3. 插入接口

前言：

// 不需要改变哨兵位，则不需要传二级指针
// 如果需要修改哨兵位的话，则传二级指针

3.1 尾插法

双链表的尾插法
双向链表尾插需不需要找尾的操作 ?

不需要：ptail = head->prev; 注意这个等价关系，便于理解下面的代码
尾插法也称作在哨兵位之前插入节点/最后一个有效节点之后插入数据

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);// 哨兵位不能为空
	LTNode* newNode = LTCreatNode(x); 
	LTNode* ptail = phead->prev;
	// 三者关系：phead->prev(即ptail)    newNode      phead
	// 处理顺序：先 newNode，  再 phead->prev(即ptail) ，最后  phead：否则会乱套
	// 先 newNode
	newNode->next = phead;
	newNode->prev = ptail; // 就是  phead->prev
	// 再尾节点 ptail = head->prev  ;   ptail  -> next = head-> prev -> next;
	ptail->next = newNode;
	// 最后头节点 
	phead->prev = newNode; 
}

3.2 头插法

双链表的头插法
注意：头插是在第一个有效位置进行插入，不是在哨兵位前面，由于双链表的循环成环状的特性，若在哨兵位前面，就是尾插了

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newNode = LTCreatNode(x);
	// 三者关系：phead   newNode   phead->next (即 第一个 有效节点，命名为Next) ;
	// 处理顺序：先 newNode，  再 phead->next(即 第一个 有效节点，命名为Next) ，最后  phead：否则会乱套
	LTNode* Next = phead->next; // 这里就是定义了个变量，便于梳理
	// 先 newNode
	newNode->next = Next;
	newNode->prev = phead;
	// 再 phead->next(即 第一个 有效节点) 
	Next->prev = newNode;
	// 最后头节点 
	phead->next = newNode;
}

3.3 在 pos 位置之后插入数据

在 pos 位置之后插入数据：要配合 4.查找接口实现

和头插法思路一样：只是将哨兵的带头作用换成了 pos

pos 是通过  4.查找  的接口找的

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	// 先创建新节点
	LTNode* newNode = LTCreatNode(x);
	// 关系三个节点：pos     newNode    pos->next
	// 先处理newNode，后 pos->next ， 最后 pos 
	// 注意三者的执行顺序 不能换！！ 
	LTNode* Next = pos->next; // 这里将 pos 的下一个节点(pos->next) 命名成 Next （避免和 next 混淆）
	newNode->next = Next;
	newNode->prev = pos;
	Next->prev = newNode;
	pos->next = newNode;
}

4. 查找

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

5.删除接口

5.1 尾删法

// 思路：让倒数第二个节点 next 指向 head ，head 指向倒数第二个节点，最后 free 掉 ptail
// 尾节点前一个节点：ptail->prev = phead->prev->prev
// 尾节点：ptail = phead->prev
// "尾节点前一个节点" 指向 head哨兵位：ptail->prev->next = phead;
// head哨兵位指向 "尾节点前一个节点" ：phead->prev = ptail->prev;
// 最后 free 掉 ptail

// 尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//链表为空：只有一个哨兵位节点
	assert(phead->next != phead);
	
	LTNode* ptail = phead->prev;
	ptail->prev->next = phead;
	phead->prev = ptail->prev; 
	free(ptail);
	ptail = NULL;
}

5.2 头删法

// 被删除的第一个有效节点：pFirst = phead->next;

// 下一个节点 pSecond = pFirst->next;
   // 先下一个节点指向 head ： pSecond->prev = phead;
   // 后 head 指向下一个节点：phead->next = pSecond;
   // 注意：因为对于循环链表来说，第一个节点的下个节点也可以是哨兵位，所以只存在一个有效节点，也是可以直接删除第一个节点的、

// 头删
// 删除的是 第一个有效节点
void LTPopFront(LTNode* phead)
{
	assert(phead); // 地址不能为NULL
	assert(phead->next != phead); // 链表不能只有 哨兵位

	LTNode* pFirst = phead->next;  // 要被删除的 第一个节点
	LTNode* pSecond = pFirst->next;
	pSecond->prev = phead;
	phead->next = pSecond;
	free(pFirst);
	pFirst = NULL;
}

5.3 删除 pos 位置的数据

删除 pos 位置的数据：要配合 4.查找接口实现

void LTErase(LTNode* pos)
{
    assert(pos);
    // 关系三个节点： pos->prev      pos     pos->next     
    LTNode* Prev = pos->prev; //  pos 的前一个 
    LTNode* Next = pos->next; //  pos 的下一个
    Next->prev = Prev;
    Prev->next = Next;
    free(pos);
    pos = NULL;
}