【数据结构】带头双向链表的简单实现

前言

该篇博客主要讲解了带头双向链表的实现和一些细节，相对于单链表，带头双向链表代码实现是更为简单的，而在物理结构上是更为复杂的。它可以帮助我们快速的对链表的头尾进行操作，单就链表而言，带头的双向链表无疑是其中最为实用的。

链表的实现

List.h

#pragma once
#include
#include

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

ListNode* ListCreate();//创建返回链表的头节点
void LTInit(ListNode** phead);//初始化头节点

void ListDestroy(ListNode* plist);//双向链表销毁

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

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

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

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

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

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

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

void ListErase(ListNode* pos);//双向链表删除pos位置的结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

对各实现方法进行声明，使包含头文件后的各个文件都可以调用其他包含相同头文件的文件内定义的函数。
该链表的实现思路为：List.h声明，List.c实现各函数，test.c对各函数进行调用。

List.c

ListCreate()

功能：创建一个结点并返回

//创建返回链表的头节点
ListNode* ListCreate(LTDataType x)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (!newNode)
	{
		perror("malloc fail:");
	}
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;

	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LTInit()

功能：初始化头结点

//初始化头节点
void LTInit(ListNode** phead)
{
	*phead = ListCreate(-1);
	(*phead)->next = *phead;
	(*phead)->prev = *phead;
}
1
2
3
4
5
6
7

对头节点的操作有两种方法，
一：使用ListNode作为返回的类型，直接返回创建好的结点的地址。
二：使用二级指针，二级指针指向包含头结点的指针的地址，一次解引用后即为包含头节点的指针本身。
两种方法各有所长，使用第一种可以更简单一些，但是实现的时候页面会不美观，使用第二种在不熟悉的情况下容易出现错误。

ListPushBack()

功能：该函数进行尾插操作

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

	ListNode* Node = ListCreate(x);
	Node->next = plist;
	Node->prev = plist->prev;
	plist->prev->next = Node;
	plist->prev = Node;
}
1
2
3
4
5
6
7
8
9
10
11

首先判断是否进行断言（判断所给参数是否为空），判断是否需要断言的依据为所给参数是否一定不为空，若一定不为空，则需要断言，防止传入空指针，该函数的主要功能为对链表进行尾插，传入的参数为指向头结点的指针，若为空则该链表不存在，所以所传的参数一定不为空，需要进行断言。

该操作必须先对新的结点进行操作，使它指向它的尾结点和头结点后在对它的相邻结点进行操作，如果直接对相邻结点进行操作，将头节点指向的上一个指针改为新节点，在想将尾结点指向的下一个结点指向新结点就无法轻易做到，必须要先对链表进行遍历后找到尾结点才能操作。

ListPopBack()

功能：对尾结点进行删除

//双向链表尾删
void ListPopBack(ListNode* plist)
{
	assert(plist);
	ListNode* temp = plist->prev;
	if (temp != plist)
	{
		temp->prev->next = temp->next;
		plist->prev = temp->prev;
		free(temp);
		temp = NULL;
	}
	else
		printf("该链表只有头节点，无法删除。");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

首先判断是否需要断言（assert：判断所给参数是否为空），该函数的主要任务是进行尾删操作，若链表为空，无法进行该操作，所以链表一定不为空。
将尾结点前的那个结点与头结点相连，利用一个临时的结点存储尾结点的地址，完成删除后，对临时结点进行释放，将空间还给内存。

ListPrint()

功能：打印链表

//双向链表打印
void ListPrint(ListNode* plist)
{
	assert(plist);
	ListNode* cur = plist->next;

	while (cur != plist)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13

从头节点后的第一个结点开始打印、遍历，知道遇到头节点，打印停止。

ListPushFront()

功能：进行双向链表的头插

//双向链表头插
void ListPushFront(ListNode* plist, LTDataType x)
{
	assert(plist);
	ListNode* Node = ListCreate(x);
	Node->prev = plist;
	Node->next = plist->next;
	plist->next->prev = Node;
	plist->next = Node;
}
1
2
3
4
5
6
7
8
9
10

首结点不能为空，需要进行断言。
双向链表头插与尾插做法相同。

ListPopFront()

功能：对链表头结点后的第一个结点进行删除操作

//双向链表头删
void ListPopFront(ListNode* plist)
{
	assert(plist);
	ListNode* temp = plist->next;
	if (temp != plist)
	{
		plist->next = temp->next;
		temp->next->prev = plist;
		free(temp);
		temp = NULL;
	}
	else
		printf("该双向链表只有头节点，无法删除!/n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

对链表进行删除结点操作，该链表一定不为空，需要进行断言。
先用一个指针接收头节点下的第一个结点查看是否为头节点，若是为头节点表示该链表没有数据，直接退出。
否则，将头节点指向的下一个结点改为临时结点的下一个结点，将连续结点的下一个结点指向的上一个结点改为头结点，删除临时结点即可。

ListFind()

功能：查找链表中存储元素为x的第一个结点，并返回该结点

//双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x)
{
	assert(plist);
	ListNode* cur = plist->next;

	while (cur != plist)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

链表不能为空，否则查找结点无意义。
使用临时变量cur接收头节点下第一个结点的地址，进行循环判断，当遇到x时，返回该结点的地址，当循环完毕，cur指向头节点的位置时，表示已经遍历了一遍，没有找到给元素所存储的结点，返回NULL

ListInsert()

功能：在pos结点前插入存储元素为x的新结点。

//双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* Node = ListCreate(x);
	Node->next = pos;
	Node->prev = pos->prev;
	pos->prev->next = Node;
	pos->prev = Node;
}
1
2
3
4
5
6
7
8
9
10

pos参数若是空将毫无意义，必须要断言
该链表为双向链表，可以根据给出的一个结点找到他的上一个结点和下一个结点，所以我们对pos指针进行操作即可。
如果首先对pos指针进行操作，那它的上一个结点将无法找到，应该使新建的新结点分别对pos结点和它的上一个节点进行操作后，断开pos结点和它上一个结点的链接即可。
当我们有了这个操作后，那我们可以改动链表的首插和尾插

//尾插
void ListPushBack(ListNode* plist, LTDataType x)
{
	assert(plist);
	ListInsert(plist->prev,x);
}

//首插
void ListPushFront(ListNode* plist, LTDataType x)
{
	assert(plist);
	ListInsert(plist->next,x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

ListErase()

功能：删除双向链表中给出的参数结点。

//双向链表删除pos位置的结点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* Node = pos->prev;
	Node->next = pos->next;
	pos->next->prev = Node;
	free(pos);
	pos = NULL;
}
1
2
3
4
5
6
7
8
9
10

同上可得，pos结点一定不为空。
使用两个局部变量分别接收pos结点指向的上一个结点和下一个结点，方便进行操作，不使用其他变量直接删除也可。这里使用一个变量Node接收上一个结点操作。将Node结点指向的下一个结点给为pos指向的下一个结点，pos指向的下一个结点指向的上一个节点指向Node，最后释放pos结点，完成删除操作。
当我们完成这个函数后，我们可以将链表的首删和尾删可以修改的更加简单

//尾删
void ListPopBack(ListNode* plist)
{
	assert(plist);
	ListErase(plist->prev);
}

//头删
void ListPopFront(ListNode* plist)
{
	assert(plist);
	ListErase(plist->next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

ListDestroy()

功能：对创建的链表进行销毁操作

//双向链表销毁
void ListDestroy(ListNode** plist)
{
	assert(*plist);

	ListNode* cur = (*plist)->next;
	while (cur != (*plist))
	{
		ListNode* temp = cur->next;
		free(cur);
		cur = temp;
	}
	free(*plist);
	*plist = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

若链表为空，销毁操作无意义，必须断言。
链表的销毁要对链表的头节点进行操作，若是传递的是头节点的地址，在VS中对该地址进行释放后链表中的数据变为随机值，但无法对其进行置空，打印头节点依然可以打印出数据，如果传递存储头结点的指针的地址，对其进行操作，即可解决这个问题，对头结点进行操作必须使用二级指针。
从链表头结点下的第一个结点开始，进行释放操作，最后对头节点进行释放和置空即可完成对链表销毁的操作。

test.c

对各个接口进行实现，这里我简单的测试了一下，并没有写成菜单的形式，若是感兴趣可以自行改写

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

void text(ListNode* phead)
{
	LTInit(&phead);

	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPushBack(phead, 4);
	ListPushBack(phead, 5);
	ListPrint(phead);

	ListPopBack(phead);
	ListPopBack(phead);
	ListPrint(phead);

	ListPopBack(phead);
	ListPopBack(phead);
	ListPrint(phead);

	ListPushFront(phead, 2);
	ListPushFront(phead, 3);
	ListPushFront(phead, 4);
	ListPushFront(phead, 5);
	ListPrint(phead);

	//ListPopFront(phead);
	ListPopFront(phead);
	ListPopFront(phead);
	ListPopFront(phead);
	ListPrint(phead);

	ListNode* pos = ListFind(phead, 3);
	if (pos)
	{
		printf("[%d|%p]\n", pos->data, pos);
		ListInsert(pos, 8);
		ListErase(pos);
		ListPrint(phead);
	}
}

int main()
{
	ListNode phead;
	text(&phead);

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51