目录

一.前言

二.双向带头循环链表的结构

三.接口实现

A.初始化 ListNodeinit 和销毁 Listdestroy

1.ListNodeinit

2.Listdestroy

B.插入

1.头插  ListNodepushfront

2.尾插 ListNodepushback

3.插入 ListNodeinsert

C.删除

1.头删 ListNodepopfront

2.尾删 ListNodepopback

3.删除 ListNodeerase

D.打印  ListNodeprint

四.源码

List.h

List.c

test.c

---

一.前言

在前面的博客中，我们学习了顺序表和结构最简单的链表——单链表，但是单链表存在在着一些不足，比如单链表的插入和删除的操作，总是要找到指定节点的前驱或是后继，这样就会比较麻烦。

那么本篇文章所讲述的双向带头循环链表（以后简称双链表），就可以很好解决这个问题。

二.双向带头循环链表的结构

1.该链表有一个哨兵位节点，即头节点；

2.每个节点都包含一个prev 指针和 next 指针，分别指向当前节点的前驱和后继；

3.头节点的 prev 指向的是尾节点，尾节点的next 指向的是头节点，这样就实现了循环。

请看图示：

 别看结构这么复杂，但其实它是一个很厉害的结构，代码实现会很简单。

三.接口实现

A.初始化 ListNodeinit 和销毁 Listdestroy

1.ListNodeinit

这个接口用来创建哨兵位头节点，并使该节点的 prev 和 next 都指向自己以实现循环的目的。

LNode* Buynewnode(DLdatatype x)   //定义一个 malloc 新节点的函数，以便后续需要
{
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	assert(newnode);
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->data = x;
	return newnode;
}
LNode* ListNodeinit()
{
	LNode* phead = (LNode*)malloc(sizeof(LNode));
	assert(phead);
	phead->prev = phead;  //使其都指向自己
	phead->next = phead;
	phead->data = -1;
	return phead;
}

2.Listdestroy

我们需要遍历链表，并定义一个next 来保存 cur 的下一个节点，在链表都free 完后，再销毁头节点；

注意：应该是从头节点的 next 开始遍历。

void ListNodedestroy(LNode* phead)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur != phead)
	{
		LNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	phead = NULL;
}

B.插入

1.头插  ListNodepushfront

1.这里要头插就太简单了，但是我们最好保存一下头节点的 next ，这样就不应考虑链接时的顺序问题；

2.使头节点的 next 指向新节点，然后新节点的 prev 指向头节点；

3.新节点的 next 指向保存的节点，保存的节点的 prev 指向新节点；

这里并不需要考虑链表为空的情况，这就是双链表的强大之处。

void ListNodepushfront(LNode* phead, DLdatatype x)
{
	assert(phead);

	LNode* newnode = Buynewnode(x);

	LNode* first = phead->next;  //保存头节点的下一个

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

2.尾插 ListNodepushback

1.尾插就需要找尾；

2.这里的找尾很简单，就是头节点的 prev；

3.将尾节点与新节点链接起来。

void ListNodepushback(LNode* phead, DLdatatype x)
{
	assert(phead);

	LNode* newnode = Buynewnode(x);
	LNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;

}

3.插入 ListNodeinsert

1.再插入前需要写一个 find 函数，用来寻找指定的位置 pos；

2.找到 pos 的前驱 prev ；

3.将前驱，pos，新节点链接起来。

LNode* ListNodefind(LNode* phead,DLdatatype x)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;

	}

	return NULL;
}

void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x)
{
	assert(phead);
	assert(pos);

	LNode* newnode = Buynewnode(x);
	LNode* prev = pos->prev;

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

总结：其实可以用一个插入接口就可以实现头插和尾插这两个接口。

C.删除

1.删除时要注意的点是不能把头节点也给删了，如果删了就破坏了双链表的结构；

2.如果是空链表也不能删除。

1.头删 ListNodepopfront

1.删除时保存其下一个节点；

2.链接头节点 phead 和 保存的下一个节点；

3.删除 phead 的next。

void ListNodepopfront(LNode* phead)
{
	assert(phead);
	assert(ListNodeempty(phead));
	if (phead->next == phead)
	{
		perror("ListNodepopfront");
		return;
	}

	LNode* first = phead->next;
	LNode* second = first->next;
	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;

	
}

2.尾删 ListNodepopback

1.找尾，即：phead的prev；

2.找尾节点的前驱 prev ，使其next指向phead，phead的prev指向该前驱；

void ListNodepopback(LNode* phead)
{
	assert(phead);
	assert(ListNodeempty(phead));

	if (phead->next == phead)
	{
		perror("ListNodepopback");
		exit(-1);
	}

	LNode* tail = phead->prev;
	LNode* prev = tail->prev;

	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;
}

3.删除 ListNodeerase

1.调用 find 函数找到要删除的节点pos；

2.找到 pos 的前驱和后继；

3.链接其前驱，后继；

4.删除pos。

void ListNodeerase(LNode* pos, LNode* phead)
{
	assert(phead);
	assert(pos);

	if (phead->next == phead)
	{
		perror("ListNodeerase");
		exit(-1);
	}
	LNode* prev = pos->prev;
	LNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);
	pos = NULL;
}

总结：这里可以复用删除函数去实现头删和尾删。

D.打印  ListNodeprint

注意是从头节点的下一个节点开始遍历，且循环终止条件是看是否等于 phead，因为双链表没有 NULL。

void ListNodeprint(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d <=> ", cur->data);
		cur = cur->next;
	}

	printf("\n");

	
}

四.源码

List.h

#pragma once


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int DLdatatype;

typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	DLdatatype data;
}LNode;

LNode* ListNodeinit();

void ListNodeprint(LNode* phead);

void ListNodepushback(LNode*phead,DLdatatype x);

void ListNodepushfront(LNode* phead, DLdatatype x);

void ListNodepopback(LNode* phead);

void ListNodepopfront(LNode* phead);

LNode* ListNodefind(LNode* phead,DLdatatype x);

void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x);

void ListNodeerase(LNode* pos, LNode* phead);

void ListNodedestroy(LNode* phead);

List.c

#define _CRT_SECURE_NO_WARNINGS

#include "List.h"

LNode* Buynewnode(DLdatatype x)
{
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	assert(newnode);
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->data = x;
	return newnode;
}

LNode* ListNodeinit()
{
	LNode* phead = (LNode*)malloc(sizeof(LNode));
	assert(phead);
	phead->prev = phead;
	phead->next = phead;
	phead->data = -1;
	return phead;
}

void ListNodeprint(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d <=> ", cur->data);
		cur = cur->next;
	}

	printf("\n");

	
}

void ListNodepushback(LNode* phead, DLdatatype x)
{
	assert(phead);

	/*LNode* newnode = Buynewnode(x);
	LNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;*/

	ListNodeinsert(phead, phead, x);

	
}

void ListNodepushfront(LNode* phead, DLdatatype x)
{
	assert(phead);

	/*LNode* newnode = Buynewnode(x);

	LNode* first = phead->next;

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;*/

	ListNodeinsert(phead->next, phead, x);
}

bool ListNodeempty(LNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

void ListNodepopback(LNode* phead)
{
	assert(phead);
	//assert(ListNodeempty(phead));

	if (phead->next == phead)
	{
		perror("ListNodepopback");
		exit(-1);
	}

	/*LNode* tail = phead->prev;
	LNode* prev = tail->prev;

	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;*/

	ListNodeerase(phead->prev, phead);
}

void ListNodepopfront(LNode* phead)
{
	assert(phead);
	//assert(ListNodeempty(phead));
	if (phead->next == phead)
	{
		perror("ListNodepopfront");
		return;
	}

	/*LNode* first = phead->next;
	LNode* second = first->next;
	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;*/

	ListNodeerase(phead->next, phead);
}

LNode* ListNodefind(LNode* phead,DLdatatype x)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;

	}

	return NULL;
}

void ListNodeinsert(LNode* pos, LNode* phead, DLdatatype x)
{
	assert(phead);
	assert(pos);

	LNode* newnode = Buynewnode(x);
	LNode* prev = pos->prev;

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

void ListNodeerase(LNode* pos, LNode* phead)
{
	assert(phead);
	assert(pos);

	if (phead->next == phead)
	{
		perror("ListNodeerase");
		exit(-1);
	}
	LNode* prev = pos->prev;
	LNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);
	pos = NULL;
}

void ListNodedestroy(LNode* phead)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur != phead)
	{
		LNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	phead = NULL;

}

test.c

至于test.c 就不贴出来了，这里面主要是一些测试接口的代码，没必要贴出来。

---

😽本篇文章到此就结束了，若有错误或是建议，欢迎小伙伴们指出；😻

😍请多多支持博主哦~🥰

🤩谢谢你的阅读~😃