前言

链表的结构有很多种，其中用的比较多的就是单向不带头不循环链表和双向带头循环链表，这两种链表都有各自应用的场合。
双向带头循环链表结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。今天就用C语言来实现一下带头双向链表的增删查改。

一、双向带头循环链表

1.双向带头循环链表结构

首先：来看一下双向带头循环链表的结构

可以看到双向带头循环链表的每一个节点都与前后相连接，因此组成了一个循环，要实现该结构，需要先创造一个头结点，该头结点的尾指针指向自己，头指针也指向自己，在此基础上实现其他节点的插入和删除。

1.双向带头循环链表实现代码

以下是代码部分：
头文件
ListNode.h

#define pragama once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

//typedef方便修改结构体变量的类型
typedef int LTDataType;

//构建链表结构体，结构体变量包括头指针，尾指针及data值
typedef struct ListNode {
	
	struct ListNode* pre;
	struct ListNode* next;
	LTDataType data;

}ListNode;

//创建新节点
ListNode* BuyListNode(LTDataType x);
//链表初始化->创造头结点
ListNode* InitListNode();
//打印链表
void ListPrint(ListNode* phead);
//销毁链表
void ListDistory(ListNode* phead);

//增删查改
void ListPushBack(ListNode* phead, LTDataType x);
void ListPushFront(ListNode* phead, LTDataType x);
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);
ListNode* ListFind(ListNode* phead, LTDataType x);
void ListInsert(ListNode* pos, LTDataType x);
void ListErase(ListNode* pos);
void Listchange(ListNode* pos, LTDataType x);

主体
ListNode.c

#include"ListNode.h"



ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->pre = NULL;


	return newnode;
}


ListNode* InitListNode()
{
	//构造头结点
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	phead->next = phead;
	phead->pre = phead;

	return phead;
}

void ListPrint(ListNode* phead)
{
	assert(phead);

	//从头结点后开始，到头结点结束
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void ListDistory(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		ListErase(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

//以下注释掉的代码段和留下的代码功能是一样的
void ListPushBack(ListNode* phead, LTDataType x)
{
	/*assert(phead);

	ListNode* newnode = BuyListNode(x);
	ListNode* tail = phead->pre;

	tail->next = newnode;
	newnode->pre = tail;
	newnode->next = phead;
	phead->pre = newnode;*/
	ListInsert(phead, x);
}

void ListPushFront(ListNode* phead, LTDataType x)
{
	/*assert(phead);

	ListNode* next = phead->next;
	ListNode* newnode = buyListNode(x);

	newnode->next = next;
	next->pre = newnode;
	phead->next = newnode;
	newnode->pre = phead;*/
	ListInsert(phead->next, x);

}

void ListPopBack(ListNode* phead)
{
	/*assert(phead);
	assert(phead->next != phead);
	
	ListNode* tail = phead->pre;
	ListNode* tailpre = tail ->pre;
	
	tailpre->next = phead;
	phead->pre = tailpre;
	
	free(tail);*/
	ListErase(phead->pre);
}

void ListPopFront(ListNode* phead)
{
	/*assert(phead);
	assert(phead->next != phead);
	
	ListNode* next = phead->next;
	ListNode* newnext = next ->next;
	
	phead->next = newnext;
	newnext->pre = phead;

	free(next);*/
	ListErase(phead->next);
}

ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);

	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* pospre = pos->pre;
	ListNode* newnode = BuyListNode(x);
	
	pospre->next = newnode;
	newnode->pre = pospre;
	newnode->next = pos;
	pos->pre = newnode;

}
//pos不能是phead！ 否则会破坏双向链表的结构;
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* pospre = pos->pre;
	ListNode* posnext = pos->next;

	pospre->next = posnext;
	posnext->pre = pospre;
	free(pos);
}
void Listchange(ListNode* pos, LTDataType x)
{
	assert(pos);
	pos->data = x;
}

测试代码
test.c

#include"ListNode.h"


void test()
{
	ListNode* phead = InitListNode();
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPushBack(phead, 4);
	ListPushBack(phead, 5);
	ListPushFront(phead, 6);
	ListPrint(phead);

	ListNode* pos = ListFind(phead, 2);
	ListInsert(pos, 8);
	ListErase(pos);
	ListPrint(phead);
	ListNode* pos2 = ListFind(phead, 4);
	Listchange(pos2, 9);

	//ListDistory(phead);
	ListPrint(phead);

}
int main()
{
	test();
	return 0;
}

运行结果

二、双向带头循环链表优缺点

以下双向循环列表的优缺点都是与顺序表和单向不循环链表相比较的，因此同时总结了了下顺序表的优缺点。

1.双向带头循环链表优缺点

• 优点：支持任意位置时间复杂度为O(1)的插入和删除，不需要扩容、不存在空间浪费。
• 缺点：不支持随机访问，缓存命中率相对低。

2.顺序表优缺点

优点：

• 相对而言空间利用率更高，不需要额外空间，占用空间小（链表需要存指针）。
• 物理空间是连续的。支持随机访问，可以用下标访问（最大优势）；缓存命中率较高。

缺点：

• 头部或中间插入或删除数据，需要一个一个挪动数据，时间复杂度是O(N)。
• 空间不够时需要增容，一般增容是按照倍数增加的、因此可能存在一定内存浪费。

链表介绍

结点的概念：

一个结点包含两个信息，一个是数据域和一个是指针域：

• 数据域存储该结点的数据信息
• 指针域存储其直接后继的位置，其示意图如下：
  

链表的概念：

每个结点的存储单元是独立的，若干个结点通过指针域依次相链接可构成一个链表，这样的结构称为线性表的链式存储，简称链表。其示意图如下：

为了能够表示链表的开始和结束，需要增加头指针L表示链表的开始，而指针域设置为NULL表示结点的结束。

不带头结点的单向链表

不带头结点的单向链表是最原始的链表，其头指针指向第一个数据元素，若是空链表其头指针的值为NULL。

由于不带头结点的链表在第一个元素插入和删除时带来不方便，因此链表初始化时，我们都需要增加一个头结点，并令头指针指向头结点，后续的链表默认都是带头结点的。其区别参见这篇文章 链表头结点和不带头结点的区别。

带头结点的单向链表

在没有特殊指明情况下，我们创建的链表默认都应该带头结点，其初始化状态为如下图所示：

带有数据元素的链表示意图：

循环链表

循环链表是单向链表的一种特殊形式，可以用于解决约瑟夫环问题。循环链表的最后一个结点的后继指向的是头结点，而不是NULL。其空循环链表的示意图如下：

带有数据元素的循环链表示意图如下：

在某些特殊情况下(比如需要频繁以追加方式插入新结点)，我们可以令头指针指向最后一个结点，或者新增加一个尾指针一直指向最后一个结点，其示意图如下：

当头指针指向最后一个结点时或者增加尾指针，可以使得查找链表的开始结点和最后一个结点都方便，其执行时间为O(1). 而在一般情况下，其执行时间为O(n)。

双向循环链表

单向链表存在一个弊端就是，当需要获取某个结点p的前驱时，需要从头指针开始遍历链表，获得“前驱”的执行时间为O(n)，为了克服单向链表的这种缺点，可以利用双向链表。

在双向链表中有两个指针域，一个是指向前驱结点的prev，一个是指向后继结点的next指针。下图是空的双向循环链表示意图：

带有数据元素的双向循环链表示意图如下：

双向循环链表的插入和删除结点执行时间均为O(1),为常量级。和其他结构的链表体现了其优越性。

总结

以下这张是带头结点的单链表、循环链表以及双向循环链表的总结：

数组和链表是我们在开发过程中最常见的数据结构（树：“有被冒犯到！”），面试种惊颤有提到的数组查询快，增删慢；链表查询慢，增删快

那么，为什么哪？我们今天就来一个追根探底。

首先，我们需要明确一点，数组查询快，链表查询慢，这句话表达是不准确的。正确的描述应该是数组支持随机查询，根据首地址+下标的查询，时间复杂度位O(1)，查询效率快，链表不支持随机查询，必须从第一个开始遍历，时间复杂度为0(N)，查询效率慢

在内存中，数组是一整块连续的区域，链表是随机分散在内存中。我们需要知道的是计算机会给每一个内存单元分配一个地址，当我们需要随机查询某个数据时，计算机会根据寻址公式：目标地址=首地址+i*元素大小。

因为数组是连续的，因此我们可以根基首地址+下标得到目标地址，而链表只能根据链表的记录，从首地址进行遍历查询。

其次数组增删慢，链表增删快,这句话表述的也不准确。

链表中的元素会保存两个属性，一个是值，一个是下一个元素的指针，当需要插入或者删除时，只需要更改相信元素的指针就可以了。

数组的增删比较复杂，插入数据时，待插入位置的的元素和它后面的所有元素都需要向后搬移，删除数据时，待删除位置后面的所有元素都需要向前搬移。在尾部插入或者删除元素时，数组的增删和链表的增删速度都是O(1)，另外数组还涉及到扩容。

数组的缺点：需要提前设置好内存大小，如果设置的大小不合适，可能会浪费内存空间。

数组应用场景：
1、数据量可控，大小稳定，变动小；
2、经常做的运算是按序号访问数据元素；
链表应用场景：
1、数据大小位置；
2、频繁做插入删除操作；

链表家族：

单链表：单链表的元素有两个属性，一个是值，一个是指向下一个元素
双向链表：双向链表的元素有三个属性，一个是值，一个是指向下一个元素，一个是指向上一个元素
循环链表：循环链表值得是链表的尾节点指向的下一个元素的地址是链表的首节点