C——双向链表

一.链表的概念及结构

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。什么意思呢？意思就是链表在物理结构上不一定是连续的，但在逻辑结构上一定是连续的。链表是由一个一个的节点连接而成的。

我们借助这个图来理解链表的物理结构上的不连续和逻辑结构上的连续。这上面的6个节点在内存空间的地址不是连续的，但是他们在逻辑上却是连续的，1->2->3->4->5->6。

与链表相似的还有顺序表，顺序表与链表相同都是线性表的一种。而顺序表的底层其实就是数组，所以顺序表在物理结构上是连续的，在逻辑结构上也是连续的。 

二.链表的分类

我们从上图可以得知，链表一共有2*2*2种。

 分别为：

单向带头循环链表、单向带头不循环链表、单向不带头循环链表、单向不带头不循环链表、双向带头循环链表、双向带头不循环链表、双向不带头循环链表、双向不带头不循环链表。

而在这么多种的链表中，最常用的只有单向不带头不循环链表（也称单链表），以及双向带头循环链表（也称双向链表）。我们今天来了解这两种之一的双向链表。

三.双向链表的结构

双向链表全称为：双向带头循环链表。怎么理解这里面的每一个修饰词呢？我们先来看一下双向链表的结构。

四.实现双向链表 

我们在实现双向链表的时候可以将所有的链表所需的函数的声明都放到一个List.h中，将函数的定义放到一个List.c中，我们还需要一个test.c用来测试我们的双向链表中的方法。

4.1链表的元素——节点的创建

节点是链表的组成元素，而对于双向链表来说，每一个节点不仅要存储数据还要存储前一个节点的地址和后一个节点的地址，没有哪一种内置类型可以同时包含这三种，所以我们节点的创建要用到自定义类型——结构体。

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

这样的结构体就可以表示一个节点了嘛？难道我们的节点只能存储整型嘛？当然不是，我们的节点可以存储任意数据，但是我们如果直接这样写的话，等到代码量大了，如果我们想要该链表存储字符型，我们到时候要修改的地方非常多。所以我们有一个一劳永逸的方法：

typedef int ListValType;

我们可以给int类型利用typedef关键字起一个新名字ListValType，我们结构体内部定义 int类型的成员时不再使用int a；而使用ListValType a；这两种的效果是一样的。以后我们想修改链表存储数据的类型的时候只需要将最前面的重命名语句中的int类型改为其他类型即可。

我们在创建节点的时候要写struct ListNode这么长一串，我们也可以利用typedef关键字给该结构体类型起一个新名字，避免了结构体名太长的问题。

所以我们节点的定义最终为：

typedef int ListValType;

typedef struct ListNode
{
	ListValType val;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;

4.2双向链表的初始化

双向链表是带头链表，而这个头就是头节点（哨兵位）。所以双向链表的初始化其实就是创建一个头节点。头节点也是节点，所以双向链表的初始化其实就是创建一个节点，只不过这个节点没有有效的值。

//创建节点
ListNode* Buynode(ListValType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	node->val = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

//双向链表的初始化
ListNode* ListInit()
{
	//创建一个头节点（哨兵位）
	ListNode* phead = Buynode(-1);
	return phead;
}

上面的代码可以完成双向链表的初始化嘛？不行！

修改后的代码为： 

 我们来写一个测试函数，来判断我们的链表的初始化是否正确。

我们调试看到，头节点的next指针和prev指针都指向了他自己，并且val = -1，说明我们的初始化没有问题。

4.3尾插 

我们创建好了新节点后想要将该节点插入到链表的尾部，怎么插入呢？插入的时候我们要注意指针指向的改变。我们来画图分析尾插的过程。

第一步：先将新节点连接到链表中

第二步：改变链表中指针的指向 

我们发现，将newnode作为新节点插入到链表中后，原链表中有的指针的指向需要改变。我们继续来画图分析哪些改变了，要怎么修改？

通过上面两幅图的分析，我们已经了解了尾插的规则，现在我们来实现双向链表的尾插方法：

//尾插
void ListPushBack(ListNode* phead,ListValType x)
{
	assert(phead);//判断该双向链表是否有效

	ListNode* newnode = Buynode(x);
	//head head->prev newnode
	newnode->prev = phead->prev;
	newnode->next = phead;

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

我们通过调试来判断一下我们的尾插是否正确。 观察上图，我们的尾插已经实现了。但是这样并不好观察，我们可以先实现双向链表的打印方法，这样就可以明显的看出尾插是否正确了。

4.4双向链表的打印

 双向链表的打印也就是遍历该链表就行了，我们只需要注意遍历时的起始位置和结束条件就行了。

//双向链表的打印
void ListPrint(ListNode* phead)
{
	assert(phead);

	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->val);
		pcur = pcur->next;
	}
	printf("\n");
}

我们现在来利用打印方法来测试尾插方法： 我们看到，尾插和打印方法都没有问题。

4.5头插

头插往哪插呢？头节点的前面吗？头插插的地方是头节点后面的位置。

头插的分析与尾插的分析相同，我们先将newnode连接到链表中，在判断那些指针的指向需要改变。

第一步：先将newnode连接到链表中

第二步：改变链表中指针的指向 

头插代码为： 

//头插
void ListPushFront(ListNode* phead, ListValType x)
{
	assert(phead);

	ListNode* newnode = Buynode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;

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

我们测试一下头插代码： 

经过测试，我们看到头插方法没有问题。

4.6尾删 

尾删就是删除该链表中的最后一个节点，即head->prev。删除该节点后，链表中有的指针指向就要发生改变。

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead && phead->next != phead);//删除的链表必须是有效链表，即不能只包含头节点

	ListNode* del = phead->prev;//要删除的尾节点

	//phead del->prev del
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}

我们利用测试代码进行测试： 我们删除了4次，所以最后一次删除链表已经为空链表了，而头节点是一个没有值的节点，所以打印出来就是空白。

 4.7头删

我们已经知道了尾删方法，头删方法的分析方式与尾删相似，我们依旧先找到要需要改变指向的指针。我们借助图来分析：

//头删
void ListPopFront(ListNode* phead)
{
	assert(phead && phead->next != phead);

	ListNode* del = phead->next;

	//phead del del->next
	del->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}

写完一个方法之后依旧通过测试方法来判断方法是否正确： 

走到这里，我们头删的方法也是正确的。

4.8在指定位置之后插入数据 

在指定位置之后插入数据，我们首先要保证这个指定的位置是存在的，要不然找不到怎么在它的后面插入呢？所以在插入数据之前我们得先查找这个数据在链表中的位置。

4.8.1查找节点

查找节点我们只需要遍历我们的链表就行了。如果遍历途中找到了就返回该节点，如果遍历完了链表还没有找到该节点，那就说明该链表只能中没有该节点。

//查找节点
ListNode* Find(ListNode* phead, ListValType x)
{
	ListNode* pcur = phead->next;
	//遍历链表
	while (pcur != phead)
	{
		if (pcur->val == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

测试代码： 

4.8.2找到节点后插入数据 

//在指定位置之后插入数据
void ListInsert(ListNode* pos, ListValType x)
{
	assert(pos);
	ListNode* newnode = Buynode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	newnode->prev = pos;

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

测试代码：

4.8.3在指定位置之后插入与尾插的区别  

4.9删除pos节点

删除pos节点也需要查找该节点是否在链表中，只有该节点在链表中我们才能对其删除。

//删除pos节点
void ListErase(ListNode* pos)
{
	assert(pos);
	//pos->prev pos pos->next
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);
	pos = NULL;
}

测试代码： 我们看到，我们调用完该方法后，我又手动将find置为了NULL，为什么要这样呢？在该方法内部不是已经置为NULL了嘛？

因为我们传的参数是一级指针，接收的形参也是一级指针，我们虽然已经将该空间释放掉了也将形参置为了空，但是这种传递方式是值传递，形参的改变不会影响实参，所以我们出了函数之后，最好将find也手动置为空，要不然会有野指针的风险。

4.10销毁链表

我们创建的链表是由一个一个的节点连接起来的，而节点是我们利用动态内存管理申请的空间，我们用完了之后就得还给操作系统，所以我们在使用完链表之后，也要将链表销毁。

//链表的销毁
void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* pcur = phead->next;
	ListNode* next = pcur->next;
	while (pcur != phead)
	{
		free(pcur);
		pcur = next;
		next = pcur->next;
	}
	//到这里，所有的有效节点已经删除了，现在只需要删除头节点
	free(phead);
	phead = NULL;
}

到这里，我们双向链表的全部功能就已经实现了。

五.完整代码

5.1双链表头文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int ListValType;

typedef struct ListNode
{
	ListValType val;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;

//双向链表的初始化
ListNode* ListInit();

//双向链表的打印
void ListPrint(ListNode* phead);

//尾插
void ListPushBack(ListNode* phead,ListValType x);

//头插
void ListPushFront(ListNode* phead, ListValType x);

//尾删
void ListPopBack(ListNode* phead);

//头删
void ListPopFront(ListNode* phead);

//查找节点
ListNode* Find(ListNode* phead , ListValType x);

//在指定位置之后插入数据
void ListInsert(ListNode* pos, ListValType x);

//删除pos节点
void ListErase(ListNode* pos);

//链表的销毁
void ListDestory(ListNode* phead);

5.2双链表源文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

//创建节点
ListNode* Buynode(ListValType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	node->val = x;
	node->next = node;
	node->prev = node;
	return node;
}

//双向链表的初始化
ListNode* ListInit()
{
	//创建一个头节点（哨兵位）
	ListNode* phead = Buynode(-1);
	return phead;
}

//双向链表的打印
void ListPrint(ListNode* phead)
{
	assert(phead);

	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->val);
		pcur = pcur->next;
	}
	printf("\n");
}

//尾插
void ListPushBack(ListNode* phead,ListValType x)
{
	assert(phead);//判断该双向链表是否有效

	ListNode* newnode = Buynode(x);
	//phead head->prev newnode
	newnode->prev = phead->prev;
	newnode->next = phead;

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

//头插
void ListPushFront(ListNode* phead, ListValType x)
{
	assert(phead);

	ListNode* newnode = Buynode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;

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

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead && phead->next != phead);//删除的链表必须是有效链表，即不能只包含头节点

	ListNode* del = phead->prev;//要删除的尾节点

	//phead del->prev del
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}

//头删
void ListPopFront(ListNode* phead)
{
	assert(phead && phead->next != phead);

	ListNode* del = phead->next;

	//phead del del->next
	del->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}

//查找节点
ListNode* Find(ListNode* phead, ListValType x)
{
	ListNode* pcur = phead->next;
	//遍历链表
	while (pcur != phead)
	{
		if (pcur->val == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//在指定位置之后插入数据
void ListInsert(ListNode* pos, ListValType x)
{
	assert(pos);
	ListNode* newnode = Buynode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	newnode->prev = pos;

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

//删除pos节点
void ListErase(ListNode* pos)
{
	assert(pos);
	//pos->prev pos pos->next
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);
	pos = NULL;
}

//链表的销毁
void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* pcur = phead->next;
	ListNode* next = pcur->next;
	while (pcur != phead)
	{
		free(pcur);
		pcur = next;
		next = pcur->next;
	}
	//到这里，所有的有效节点已经删除了，现在只需要删除头节点
	free(phead);
	phead = NULL;
}

5.3测试源文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

void test01()
{
	ListNode* phead = ListInit();
	//测试尾插
	ListPushBack(phead,1);
	ListPrint(phead);
	ListPushBack(phead,2);
	ListPrint(phead);
	ListPushBack(phead,3);
	ListPrint(phead);
	ListPushBack(phead,4);
	ListPrint(phead);
}

void test02()
{
	ListNode* phead = ListInit();
	//测试头插
	ListPushFront(phead, 5);
	ListPrint(phead);
	ListPushFront(phead, 6);
	ListPrint(phead);
	ListPushFront(phead, 7);
	ListPrint(phead);
}

void test03()
{
	ListNode* phead = ListInit();
	//测试尾插
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPushBack(phead, 4);
	ListPrint(phead);

	//链表的销毁
	ListDestory(phead);
	phead = NULL;
	ListPrint(phead);

	//ListNode* find = Find(phead, 1);

	测试删除pos节点
	//ListErase(find);//删除1节点
	//find = NULL;
	//ListPrint(phead);

	测试查找方法
	//ListNode * find = Find(phead, 1);
	if (find == NULL)
	{
		printf("找不到！");
	}
	else
	{
		printf("找到了!");
	}
	//ListInsert(find,99);//在第一个节点之后插入99
	//ListPrint(phead);
	测试头删
	//ListPopFront(phead);
	//ListPrint(phead);
	//ListPopFront(phead);
	//ListPrint(phead);
	//ListPopFront(phead);
	//ListPrint(phead);
	//ListPopFront(phead);
	//ListPrint(phead);

	测试尾删
	//ListPopBack(phead);
	//ListPrint(phead);
	//ListPopBack(phead);
	//ListPrint(phead);
	//ListPopBack(phead);
	//ListPrint(phead);
	//ListPopBack(phead);
	//ListPrint(phead);

}
int main()
{
	//test01();
	//test02();
	test03();
	return 0;
}

完！