带头节点双向循环链表

| 分类于

前言

此处介绍一种以头节点为维护方式的双向循环链表，这也是在日常生活工作中使用比较频繁的一种链表结构。因为此种链表是双向的且循环，首尾相连，所以在对链表进行一些操作的时候和单向链表相比较就会方便很多。

链表的基本结构（图示）


next指针和单链表相似，由头节点开始，依次指向下一个节点，不同之处在于链表最后一个节点的指针指向头节点；prev指针称为前驱，他总是指向当前节点的上一个节点，头节点的prev指针指向最后一个节点。所以在双向循环链表中可以通过头节点的prev指针找到链表的最后的一个节点，也正是这个优点让双向循环链表变得方便简单

双向循环链表节点的定义

1
2
3
4
5
6
7
typedef int DataType;

typedef struct Node{
	struct Node *prev;  //指向当前节点的前驱
	struct Node *next;  //指向当前节点的后一个节点
	DataType data;
}Node;

链表的初始化

不同于单向链表的初始化，双向链表的初始化是指链表中只有头节点这一个节点，故也可以说是头节点的初始化.头节点中的数据域我们是不用的，所以也可以在头节点的数据域中存放一些关于该链表的信息

使两个指针都指向他自己，在这里注意不同于单链表的头指针维护方式，这里我们需要先创建一个节点来当头节点，借此来维护整个链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Node *creatNode(DataType data)
{
	Node *node = (Node *)malloc(sizeof(Node));
	node->data = data;
	node->next = node->prev = NULL;
	return node;
}

//初始化头节点
Node *InitDSList(Node **psHead) 
{
	assert(psHead != NULL);
	Node *newNode = creatNode(0); //此处0没实际用处，可以当成是size来记录链表插入了多少个节点
	newNode->next = newNode;
	newNode->prev = newNode;
	*psHead = newNode;
}

链表的清空

释放链表中的所有节点，除了头节点，后将头节点指针初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
//清空链表（保留头节点）
void ClearDSList(Node *head)
{
	Node *del = NULL;
	Node *cur = head->next;
	while (cur != head)
	{
		del = cur;
		cur = cur->next;
		free(del);
	}
	head->next = head->prev = head;
}

销毁链表

包括头节点在内全部释放

1
2
3
4
5
6
//销毁链表
void DestroyDSList(Node *head)  
{
	ClearDSList(head);
	free(head);
}

任意位置插入新的节点

1
2
3
4
5
6
7
8
9
10
// 插入到 pos 的前面	（pos一定在链表中）
void DListInsert(Node *head, Node *pos, DataType data) //三个参数，分别是链表的头节点，插入的位置，数据
{
	Node *node = creatNode(data);

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

头插

1
2
3
4
5
6
7
8
9
10
11
12
13
//头插
void DSListPushFront(Node *head,DataType data)
{
	DListInsert(head, head->next, data);   //我们可以直接调用任意位置插入的函数
#if 0    //不调用自己写也可以
	Node *node = creatNode(data);  

	node->prev = head;
	node->next = head->next;
	head->next = node;
	head->next->prev = node;
#endif
}

尾插

1
2
3
4
5
6
7
8
9
10
11
12
13
//尾插
void DSListPushBack(Node *head, DataType data)
{
	DListInsert(head,head,data); 
#if 0
	Node *node = creatNode(data);

	node->next = head;
	head->prev->next = node;	
	node->prev = head->prev;
	head->prev = node;
#endif
}

任意位置节点删除

1
2
3
4
5
6
7
8
//删除节点pos  pos是链表中的任意一个结点（头结点）
void DSListErase(Node *head, Node *pos)  //head为链表头节点，pos为所要删除节点位置
{
	assert(head);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}

头删

1
2
3
4
5
6
7
8
9
10
11
void PopFront(Node *head)
{
	assert(head->next != head);
	Node *del = head->next;
	head->next = head->next->next;
	head->next->next->prev = head;
	free(del);
#if 0
	DSListErase(head, head->next);
#endif
}

尾删

1
2
3
4
5
6
7
8
9
10
11
void PopBack(Node *head)
{
	Node *del = head->prev;
	assert(head != NULL);
	head->prev->prev->next = head;
	head->prev = head->prev->prev;
	free(del);
#if 0
	DSListErase(head, head->prev);
#endif
}

测试代码及运行结果

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
void test()
{
	Node *list;  //定义出链表中的头节点
	InitDSList(&list); //初始化头节点
	printf("尾插五个元素：\n");
	DSListPushBack(list, 5);
	DSListPushBack(list, 4);
	DSListPushBack(list, 3);
	DSListPushBack(list, 2);
	DSListPushBack(list, 1);
	PrintDSList(list);
	printf("指定位置插入,在第二个节点前插入: \n");
	DListInsert(list, list->next->next, 10);
	PrintDSList(list);
    DSListErase(list, list->next->next);
	printf("指定位置删除,删除第二个节点: \n");
	PrintDSList(list);
	printf("头删：\n");
	PopFront(list);
	PrintDSList(list);
	printf("尾删: \n");
	PopBack(list);
	PrintDSList(list);
    ClearDSList(list);   //清空链表
	DestroyDSList(list);  //销毁链表
	/*printf("头插四个元素：");
    DSListPushFront(list, 3);
	DSListPushFront(list, 2);
	DSListPushFront(list, 1);
	DSListPushFront(list, 0); 
	PrintDSList(list);*/	
}

int main()
{
	test();
	system("pause");
	return;
}

运行结果：