【数据结构初阶】双向链表

各位读者老爷好，很高兴你又来读本鼠鼠的博客。鼠鼠我呀基于C语言实现一下双向链表，有兴趣的读者老爷可以瞅瞅哈！

目录

1.定义双向链表节点

2.初始化哨兵位

3.双向链表销毁

4.双向链表打印

5.双向链表在pos的前面进行插入

6.双向链表删除pos位置的节点 

7.双向链表尾插

8.双向链表尾删

9.双向链表头插 

10.双向链表头删 

11.双向链表查找

12.双向链表的小应用

12.1.list.h

12.2.list.c

12.3.test.c:

13.ending 

好哈，我们上篇文章浅谈过链表的分类，其中讲到：

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

那咱们上篇文章实现过了无头单向非循环链表 ，那这篇博客自然要实现带头双向循环链表了。

对于带头双向循环链表，好像听起来挺难的，但其实实现起来比无头单向非循环链表简单不是一星半点儿，咱们可以在接下来的代码中体会到，我们可以先来看看带头双向循环链表的逻辑结构如下图：

咱们可以看到有一个指针plist指向哨兵位（也就是头），所有节点均有三个数据域，分别存储所需存储的数据、前一个节点的地址和后一个节点的地址，我们通过地址即可找到想要的节点。这里讲的前后节点只是逻辑上的“前后”，实际上在内存中这些个节点通过保存的地址形成了循环，没有所谓的前后之分，那这个链表改重哪里开始呢？

其实就是从哨兵位开始的，让plist指向哨兵位，让哨兵位当“头”，也就在逻辑上形成了“前后”。

带头双向循环链表带哨兵位是有优势的，虽然哨兵位不存储有效数据，好似浪费了一个节点的空间，但是因为无论什么时候该链表都不可能为空，对于该链表的增删改等操作不用另外考虑空链表的情况 。带头双向循环链表的哨兵位是不能删除的。

以下带头双向循环链表简称双向链表。我们实现双向链表以下功能：

typedef int LTDataType;

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


//初始化哨兵位
ListNode* LTInit(void);

// 双向链表销毁
void ListDestory(ListNode* pHead);

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

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);

// 双向链表尾删
void ListPopBack(ListNode* pHead);

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);

// 双向链表头删
void ListPopFront(ListNode* pHead);

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);

1.定义双向链表节点

typedef int LTDataType;

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

由上分析可知，该链表节点需要包含三个数据域，所以我们定义结构体，结构体成员data用来存储需存储数据、结构体成员next用来存储后一个节点地址、结构体成员prev用来存储前一个节点地址。至于为什么要把int重命名成LTDataType，那是因为如果需存储数据的类型如果有所变化的话，我们只需更改此处的int更改成需存储数据的类型即可，极大方便后续的代码维护。

2.初始化哨兵位

//创建双向链表节点
ListNode* ListCreate(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail->");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

//初始化哨兵位
ListNode* LTInit(void)
{
	ListNode* head = ListCreate(-1);
	head->next = head;
	head->prev = head;
	return head;
}

创建双向链表的时候我们需要初始化哨兵位，初始化哨兵位就需要创建节点，所以我们需要调用ListCreate函数（LIstCreate函数参数是需存储数据，动态申请一个节点，返回这个节点地址。），将哨兵位的next和prev存储哨兵位自己的地址才符合双向带头循环链表的特点，哨兵位的data随便赋值即可。

大概这样式的啦！

3.双向链表销毁

//双向链表销毁
void ListDestory(ListNode*pHead)
{
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(pHead);
	pHead = NULL;
	cur = NULL;
}

当我们不在使用双向链表的时候，好习惯是主动释放双向链表的空间。我们从哨兵位后一个节点开始遍历释放节点空间，最后再单独释放哨兵位空间。

4.双向链表打印

//双向链表打印
void ListPrint(ListNode* pHead)
{
	ListNode* cur = pHead->next;
	printf("哨兵位<——>");
	while (cur != pHead)
	{
		printf("%d<——>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

大概思想是从哨兵位后一个节点开始遍历打印节点中需存储的数据即可（无需打印哨兵位的数据，因为那是无效数据，上面的写法很完美打印出了所有有效数据，当cur等于pHead时不进入循环内，自然不打印哨兵位的数据了。）。

5.双向链表在pos的前面进行插入

//创建双向链表节点
ListNode* ListCreate(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail->");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = ListCreate(x);
	newnode->prev = pos->prev;
	pos->prev->next = newnode;
	newnode->next = pos;
	pos->prev = newnode;
}

好好好，这个功能的实现来说，只需要通过pos->prev找到pos指向节点的前一个节点，并让新申请节点（调用ListCreate函数）的prev存储前一个节点的地址；让前一个节点的next存储新申请节点的地址；让新申请节点的next存储pos指向节点的地址；让pos指向节点的prev存储新申请节点的地址即可。

读者老爷请看图：

6.双向链表删除pos位置的节点 

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	if (pos->next == pos)
	{
		printf("不可删除哨兵位\n");
	}
	//防止删除哨兵位
	assert(pos->next != pos);
	ListNode* posnext = pos->next;
	ListNode* posprev = pos->prev;
	posnext->prev = posprev;
	posprev->next = posnext;
	free(pos);
	pos = NULL;
}

这个功能的实现也不难！我们只要分别通过pos->next和pos->prev找到pos指向节点的后一个节点和前一个节点；让后一个节点的prev存储前一个节点的地址；让前一个节点的next存储后一个节点的地址；再释放掉pos指向节点的空间。注意要断言防止删除哨兵位（当pos指向哨兵位时，pos->next等于pos，所以assert条件为假就报错了。）！ 

读者老爷请看图：

7.双向链表尾插

//创建双向链表节点
ListNode* ListCreate(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail->");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	//法一
	ListNode* tail = pHead->prev;
	ListNode* newnode = ListCreate(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pHead;
	pHead->prev = newnode;

	//法二
	//ListInsert(pHead, x);
}

对于尾插，因为pHead指向哨兵位，所以通过pHead->prev找到双向链表尾节点；调用ListCreate函数申请一个新节点；让尾节点的next存储新申请节点的地址；让新申请节点的prev存储尾节点地址；让新申请节点的next存储pHead；让pHead的prev存储新申请节点地址即可。

也可以直接调用前面实现过的“双向链表再pos的前面进行插入”函数，将哨兵位的地址(pHead)和所需存储数据传参进去即可。

8.双向链表尾删

//双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	if (pHead->next == pHead)
	{
		printf("不可删除哨兵位\n");
	}
	//防止删除哨兵位
	assert(pHead->next != pHead);

	//法一
	/*ListNode* tail = pHead->prev;
	ListNode* tailprev = tail->prev;
	tailprev->next = pHead;
	pHead->prev = tailprev;
	free(tail);
	tail = NULL;*/

	//法二
	ListErase(pHead->prev);
}

对于双向链表尾删，要注意断言防止删除哨兵位！对于这个功能实现的思想大致来说就是通过pHead->prev找到尾节点；再通过尾节点的prev找到尾节点的前一个节点；让尾节点的前一个节点的next存储pHead；让pHead指向的节点（哨兵位）的prev存储位节点的前一个节点的地址；再释放掉pos指向的节点的空间即可。

也可以直接调用前面实现的“双向链表删除pos位置的节点”函数，传入pHead->prev(尾节点的地址)即可。

9.双向链表头插 

//创建双向链表节点
ListNode* ListCreate(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail->");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	//法一
	ListNode* newnode = ListCreate(x);
	ListNode* head = pHead->next;
	newnode->next = head;
	head->prev = newnode;
	newnode->prev = pHead;
	pHead->next = newnode;

	//法二
	//ListInsert(pHead->next, x);
}

对于双向链表头插，我们是往哨兵位的后一个节点的前面插入，使得插入的新申请节点成为哨兵位后一个节点。具体分析鼠鼠我就不分析了，很简单啦！也可以直接调用前面实现过的“双向链表再pos的前面进行插入”函数哈！

10.双向链表头删 

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	if (pHead->next == pHead)
	{
		printf("不可删除哨兵位\n");
	}
	//防止删除哨兵位
	assert(pHead->prev != pHead);

	//法一
	ListNode* head = pHead->next;
	pHead->next = head->next;
	head->next->prev = pHead;
	free(head);
	head = NULL;

	//法二
	//ListErase(pHead->next);
}

头删的含义也是删除哨兵位后一个节点啦！我们只要做好相应节点的链接再释放哨兵位后一个节点就行了。也可以直接调用前面实现过的“双向链表删除pos位置的节点”函数。很简单，鼠鼠我偷个懒，就不分析了。

11.双向链表查找

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

我们只要遍历查找除了哨兵位之外的所有节点的需存储数据即可，如果有需存储数据与需查找数据一致我们就返回该节点的地址，找不到就返回空指针。简简单单啦！对了，哨兵位的需存储数据本身是无效数据，当然不用查找了。

12.双向链表的小应用

老样子了，鼠鼠我呀写了三个文件，有兴趣的读者老爷可以将这三个文件放到同一个工程下面玩玩，可以更加深刻的理解上面代码的功能！

12.1.list.h

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

typedef int LTDataType;

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


//初始化哨兵位
ListNode* LTInit(void);

// 双向链表销毁
void ListDestory(ListNode* pHead);

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

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);

// 双向链表尾删
void ListPopBack(ListNode* pHead);

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);

// 双向链表头删
void ListPopFront(ListNode* pHead);

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);

12.2.list.c

#define _CRT_SECURE_NO_WARNINGS
#include"list.h"

//创建双向链表节点
ListNode* ListCreate(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail->");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}


//初始化哨兵位
ListNode* LTInit(void)
{
	ListNode* head = ListCreate(-1);
	head->next = head;
	head->prev = head;
	return head;
}


//双向链表销毁
void ListDestory(ListNode*pHead)
{
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(pHead);
	pHead = NULL;
	cur = NULL;
}


//双向链表打印
void ListPrint(ListNode* pHead)
{
	ListNode* cur = pHead->next;
	printf("哨兵位<——>");
	while (cur != pHead)
	{
		printf("%d<——>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}


// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	//法一
	ListNode* tail = pHead->prev;
	ListNode* newnode = ListCreate(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pHead;
	pHead->prev = newnode;

	//法二
	//ListInsert(pHead, x);
}


//双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	if (pHead->next == pHead)
	{
		printf("不可删除哨兵位\n");
	}
	//防止删除哨兵位
	assert(pHead->next != pHead);

	//法一
	/*ListNode* tail = pHead->prev;
	ListNode* tailprev = tail->prev;
	tailprev->next = pHead;
	pHead->prev = tailprev;
	free(tail);
	tail = NULL;*/

	//法二
	ListErase(pHead->prev);
}


// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	//法一
	ListNode* newnode = ListCreate(x);
	ListNode* head = pHead->next;
	newnode->next = head;
	head->prev = newnode;
	newnode->prev = pHead;
	pHead->next = newnode;

	//法二
	//ListInsert(pHead->next, x);
}


// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	if (pHead->next == pHead)
	{
		printf("不可删除哨兵位\n");
	}
	//防止删除哨兵位
	assert(pHead->prev != pHead);

	//法一
	ListNode* head = pHead->next;
	pHead->next = head->next;
	head->next->prev = pHead;
	free(head);
	head = NULL;

	//法二
	//ListErase(pHead->next);
}


// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}


// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = ListCreate(x);
	newnode->prev = pos->prev;
	pos->prev->next = newnode;
	newnode->next = pos;
	pos->prev = newnode;
}


// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	if (pos->next == pos)
	{
		printf("不可删除哨兵位\n");
	}
	//防止删除哨兵位
	assert(pos->next != pos);
	ListNode* posnext = pos->next;
	ListNode* posprev = pos->prev;
	posnext->prev = posprev;
	posprev->next = posnext;
	free(pos);
	pos = NULL;
}

12.3.test.c:

#define _CRT_SECURE_NO_WARNINGS
#include"list.h"
void menu()
{
	printf("******************************\n");
	printf("************0.退出************\n");
	printf("*******1.头插****2.尾插*******\n");
	printf("*******3.头删****4.尾删*******\n");
	printf("*******5.查找****6.打印*******\n");
	printf("*7.双向链表在pos的前面进行插入\n");
	printf("**8.双向链表删除pos位置的节点*\n");
}
int main()
{
	ListNode* plist = LTInit();
	int input = 0;
	do
	{
		menu();
		printf("请输入你想要的操作的代表数字：->");
		scanf("%d", &input);
		printf("\n");
		switch (input)
		{
		case 0:
		{
			ListDestory(plist);
			plist = NULL;
			printf("\n");
			break;
		}
		case 1:
		{
			int i = 0;
			printf("请输入你想头插的数据个数：->");
			scanf("%d", &i);
			int j = 0;
			printf("请输入你想头插的数据：->");
			for (j = 0; j < i; j++)
			{
				LTDataType x = 0;
				scanf("%d", &x);
				ListPushFront(plist, x);
			}
			printf("\n");
			break;
		}
		case 2:
		{

			int i = 0;
			printf("请输入你想尾插的数据个数：->");
			scanf("%d", &i);
			int j = 0;
			printf("请输入你想尾插的数据：->");
			for (j = 0; j < i; j++)
			{
				LTDataType x = 0;
				scanf("%d", &x);
				ListPushBack(plist, x);
			}
			printf("\n");
			break;
		}
		case 3:
		{
			ListPopFront(plist);
			printf("\n");
			break;
		}
		case 4:
		{
			ListPopBack(plist);
			printf("\n");
			break;
		}
		case 5:
		{
			LTDataType x = 0;
			printf("请输入你想查找的数据：->");
			scanf("%d", &x);
			ListNode* ret = ListFind(plist, x);
			if (ret != NULL)
			{
				printf("找到了，该节点地址是%p\n", ret);
			}
			else
			{
				printf("找不到\n");
			}
			printf("\n");
			break;
		}
		case 6:
		{
			ListPrint(plist);
			printf("\n");
			break;
		}
		case 7:
		{
			LTDataType n = 0, x = 0;
			printf("请分别输入你想插入的数据和pos指向节点的数据：->");
			scanf("%d %d", &x, &n);
			ListInsert(ListFind(plist,n), x);
			printf("\n");
			break;
		}
		case 8:
		{
			LTDataType x = 0;
			printf("请输入pos指向节点的数据：->");
			scanf("%d", &x);
			ListErase(ListFind(plist,x));
			printf("\n");
			break;
		}
		}
	} while (input);
	return 0;
}

13.ending 

好好好，看到这里的话，读者老爷如果觉得文章有不好的地方，恳请斧正，谢谢！