【数据结构】带头双向循环链表的实现（C语言）

 目录

前言

初始化

增删及打印

查找

指定位置后插入

删除指定位置

销毁

尾言

---

前言

之前我们讲了单链表的实现【数据结构】单链表定义的介绍及增删查改的实现，带头双向循环链表就是在单链表的基础之上增加了一些功能使结构更加完善。可以直接用两个字来形容它，就是无敌。

编辑

增加了头结点使得在插入结点时不再需要对原链表是否为空进行判断，就可以直接插入到头结点之后。增加循环功能实现了链表对前一结点的访问，弥补了单链表只能沿一个方向迭代的缺陷。而增加循环功能则是回避了每次链表访问尾结点都需要遍历一遍链表的弊端。虽然这样的结构看起来可能有些许复杂，但从实际运用上来讲，这个结构确实是无懈可击。

也正是这个结构的优势，在这个链表的实现中不再需要更改头结点，也就是说只要一级指针就可以完成整个链表的实现。

初始化

结点的初始化

 结合上述结构，带头循环双向链表的结点的有一个 prev 指向上一个结点同时有一个 next 指向下一给结点，并在 data 存储数据

先使用malloc开辟结构体的空间，之后对开辟空间成功与否进行判断之后，对其赋值以及指向地址的初始化。 最后返回开辟的地址，完成一个结点的开辟。

 链表的初始化

这是个带头的链表，所以在初始化的时候就要完成头结点的开辟，完成初步的循环。

这样初步循环的意义在于在之后要插入新结点时即便整个链表只有头结点一个但使用的插入方式不用发生变化。即保证循环的进程。

增删及打印

尾插

这边就可以直接感受到这个结构给我们带来的便利，我们只需对头结点进行断言之后通过头结点找到尾节点，并在二者之间插入新节点。值得注意的是，尾插是在尾结点跟头结点之间插入，而不是在尾结点前插入，要避免出现这样的误区。

书接上文，想象一下当我们链表中只有一个头结点时，对头结点的上一个结点访问仍然还是头结点，之后头结点的上一个结点为新的这个结点，由于在这之前头结点的上一个结点还是自己，经过链接头结点上一个跟下一个都是新结点，就相当于是头插，这就是前面头结点初始化时要让头结点的上下结点都指向自己的原因。

尾删

经过结构的升级，原本单链表原本不完善的结构已经完善，尾删一样变得非常简单通过头结点找到尾结点，再寻找到尾结点的上一个结点并将其于头结点链接起来就可以实现。

既然是删除就要保证在链表为空的时候不能继续删除，在这里再用 NULL 判断链表数量已经不管用了，这个链表不断循环根本不会出现空指针，而是通过头结点来判断。即只要链表中至少存在一个非头结点的结点，头指针的下一个结点便不会指向自己。所以以此断言。

打印

 为了方便分块调试，这里就先讲打印，以便于能直接判断前面的代码写得是否正确。

需要注意的也就只有结束循环的条件，通过头结点来判断链表循环一周便可以结束循环。

头插

 头插跟尾插的步骤相差不大，先断言传入的指针，之后需要找到第一个结点，在其于头结点之间插入新节点。

头删

同样考虑一下链表是否只有头结点，之后找到第一跟第二结点，把第一结点释放后把头结点跟第二结点链接起来。

写到这里，各位可能感觉怪怪的，感觉要思考的东西好像变少了，这正是带头双向循环链表带给我们的便利。正如这里，如果链表只有一个结点也不用担心会对空指针进行解引用，因为唯一的那个结点指向的是头指针，即将第一个结点删除后，头结点还会继续跟自己链接起来，这就是前面为什么说这个结构无敌的原因。各各方面都非常完美，简直无懈可击，让我在实现程序的时候都不寒而栗。

查找

对于查找并没有更好的方法，找到就返回目标的地址，没找到就继续迭代直到链表循环一次

编辑

指定位置后插入

从某种层面上来讲，只要实现了这个跟下面两个函数就可以实现前面的增删操作了。

接收一个结点的地址，操作前先判断是否是空指针避免发生错误，因为要在 pos 的下一位插入结点，所以找到 pos 的下一位，新建结点后将其插入到二者之间。若要在 pos 前插入只要 pos 的上一个结点就可以了，这也是单链表十分困难才能做到的操作。

 实现了指定位置插入结点的操作，前面的头插跟尾插就可以变成这样。

删除指定位置

接收一个指针，判断一下删除两件套（传入指针是否为空及链表是否只有一个头结点），然后找到 pos 的前后结点将其链接起来后并将 pos 释放就完成目标。即便只有一个结点也能完成工作。

 这个实现完，头删尾删也可以转换成

销毁

首先断言确保不是空指针，通过迭代一个一个释放链表的结点，最后别忘记头结点也要释放掉！！！

尾言

如此带头双向循环链表的实现就完成了，也就只有初始化以及链接时候麻烦一点，其他方面完美胜过其他类型的链表。把源码放在下面，有需要的自取。使用前记得对链表进行初始化，接收头结点之后再使用。

Dlist.h

#pragma once

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

typedef  int LTdatatype;
typedef struct Listnode
{
	struct Listnode* prev;
	LTdatatype data;
	struct Listnode* next;
}Listnode;

Listnode* ListCreate(void);
Listnode* buynewnode(LTdatatype x);
void Listpushback(Listnode* head, LTdatatype x);
void Listprint(Listnode* head);
void Listpopback(Listnode* head);
void Listpushfront(Listnode* head, LTdatatype x);
void Listpopfront(Listnode* head);
Listnode* ListFind(Listnode* head, LTdatatype x);
void ListInsert(Listnode* pos, LTdatatype x);
void ListErase(Listnode* pos);
void Listdestroy(Listnode* pos);

#include"Dlist.h"


Listnode* buynewnode(LTdatatype x)   //开辟新结点
{
	Listnode* newnode = (Listnode*)malloc(sizeof(Listnode));   //开辟空间
	if (newnode == NULL)                        //判断开辟是否成功
	{
		perror(malloc);
		exit(-1);
	}
	newnode->data = x;                          //赋值
	newnode->next = NULL;                       //下一结点初始制空
	newnode->prev = NULL;                       //上一结点初始制空
	return newnode;
}


Listnode* ListCreate()  //链表的初始化
{
	Listnode* head = buynewnode(-1);      //开辟头结点
	head->next = head;                    //下一结点指向自己
	head->prev = head;                    //上一结点也指向自己
	return head;
}

void Listpushback(Listnode* head, LTdatatype x)
{
	assert(head);
	////通过头结点找到尾结点
	//Listnode* back = head->prev;
	//Listnode* newnode = buynewnode(x);

	////三者链接
	//head->prev = newnode;
	//newnode->next = head;
	//back->next = newnode;
	//newnode->prev = back;

	ListInsert(head->prev, x);
}

void Listpopback(Listnode* head)
{
	assert(head);
	assert(head->next != head);  //判断链表是否只有头指针
	//Listnode* back = head->prev; //找尾结点

	//back->prev->next = head;   //跨过尾结点链接
	//head->prev = back->prev;
	//free(back);

	ListErase(head->prev);

}


void Listprint(Listnode* head)
{
	Listnode* cur = head->next;
	while (cur!=head)        //回到头结点说明已经循环一遍结束循环
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void Listpushfront(Listnode* head, LTdatatype x)
{
	//assert(head);
	////找到第一个结点进行头插
	//Listnode* newnode = buynewnode(x);
	//Listnode* first = head->next;

	////三者链接
	//head->next = newnode;
	//newnode->prev = head;
	//newnode->next = first;
	//first->prev = newnode;

	ListInsert(head, x);
}

void Listpopfront(Listnode* head)
{
	assert(head);
	assert(head->next != head);
	//Listnode* first = head->next; //找第一个结点
	//Listnode* sec = first->next; //找第二个结点

	//head->next = sec;
	//sec->prev = head;
	//free(first);

	ListErase(head->next);

}


Listnode* ListFind(Listnode* head, LTdatatype x)
{
	assert(head);
	Listnode* cur = head->next;
	while (cur != head)
	{
		if (cur->data == x)
		{
			break;
		}
		cur = cur->next;
	}
	if (cur == head)
	{
		printf("找不到\n");
	}
	else
	{
		return cur;
	}
	return NULL;
}

void ListInsert(Listnode* pos, LTdatatype x)
{
	assert(pos);
	Listnode* next = pos->next;   //找pos的下一个结点
	Listnode* newnode = buynewnode(x);

	//三点链接
	pos->next = newnode;
	newnode->prev = pos;
	newnode->next = next;
	next->prev = newnode;

}


void ListErase(Listnode* pos)
{
	assert(pos);
	assert(pos->next != pos);
	
	//找到前后
	Listnode* bef = pos->prev;
	Listnode* next = pos->next;

	bef->next = next;
	next->prev = bef;
	free(pos);

}

void Listdestroy(Listnode* head)
{
	assert(head);
	Listnode* cur = head->next;
	while (cur != head)
	{
		Listnode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(head);
}