线性表之链表

• 导航
• • 1、带头双向循环链表介绍
  • 2、结构体及接口函数定义
  • 3、接口函数实现
  • • 3.1 头结点初始化
    • 3.2 结点动态内存申请
    • 3.3 双向链表尾插
    • 3.4 双向链表尾删
    • 3.5 双向链表头插
    • 3.6 双向链表头删
    • 3.7 双向链表查找
    • 3.8 在pos位置前插入
    • 3.9 删除pos位置的结点
    • 3.10 打印双向链表
    • 3.11 销毁双向链表
  • 4、顺序表和链表的区别
  • 5、结语

导航

1、带头双向循环链表介绍

在上一篇博客我们讲述了链表的概念和结构，还实现了无头单向非循环链表接口写法，那么这一章节，我们来实现另一种常用的链表组成结构——带头双向循环链表。
如果对前面的链表基本概念还是不了解，可以看作者的上一篇博客：
线性表中链表介绍及无头单向非循环链表接口实现

2、结构体及接口函数定义

首先是结构体的定义
代码如下：

typedef int LTDateType;
typedef struct ListNode
{
	LTDateType data;//结点存储元素
	struct ListNode* next;//下一结点指针
	struct ListNode* prev;//上一结点指针
}LTNode;

然后就是接口函数的定义
代码如下：

void ListInit(LTNode* phead)；//哨兵位头结点初始化
LTNode* BuyListNode(LTDateType x);//动态申请结点
void ListPushBack(LTNode* phead, LTDateType x);//双向链表尾插
void ListPopBack(LTNode* phead);//双向链表尾删
void ListPushFront(LTNode* phead, LTDateType x);//双向链表头插
void ListPopFront(LTNode* phead);//双向链表头删
LTNode* ListFind(LTNode* phead, LTDateType x);//双向链表查找
void ListInsert(LTNode* pos, LTDateType x);//在pos位置前插入
void ListErase(LTNode* pos);//删除pos位置的结点
void ListPrint(LTNode* phead);//打印双向链表
void ListDestroy(LTNode* phead);//销毁双向链表

3、接口函数实现

在上一篇博客中我们讲到不带头的单非循环链表存在一定缺陷，就是无法访问上一结点，但是这一节讲的带头双向循环链表就很好的弥补了这一缺点，带头双向循环链表看来比单链表结构要复杂很多，但其实实现起来要比单链表更简单，更高效；下面我们就来实现带头双向循环链表的接口函数吧！

3.1 头结点初始化

头结点初始化（ListInit）
首先是我们的头结点的定义，它是不存放数据的，起到一个哨兵的作用
代码如下：

void ListInit(LTNode* phead)
{
	// 哨兵位头结点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

第一步当然是先使用malloc函数申请内存空间，然后就是两个指针的建立，尾部指针指向头结点头部，头部指针指向头结点尾部，返回带头结点，头结点初始化完成。

3.2 结点动态内存申请

结点动态内存申请（BuyListNode）
这个函数和上一篇中的单链表的函数类似
代码如下:

LTNode* BuyListNode(LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

第一步也是先使用malloc函数申请内存空间，然后就是初始化这个结点的操作，将元素插入，两个指针指向空，返回新结点，完成结点初始化操作。

3.3 双向链表尾插

双向链表尾插（ListPushBack）
代码如下：

void ListPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);

	LTNode* tail = phead->prev;
	LTNode* newnode = BuyListNode(x);

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

这里我们先是把phead的上一级指针赋给tail
再将要插入的元素赋给临时结点newnode
接着将tail的下一级指针指向newnode
再将newnode上一级指针指向tail
newnode下一级指针指向被插入结点phead
最后将phead的上一级指针再指向newnode完成尾插操作

3.4 双向链表尾删

双向链表尾删（ListPopBack）
代码如下：

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//防止链表中无元素继续删除的断言

	LTNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next = phead;

	free(tail);
}

上述代码中第二个断言是为了防止链表中无元素继续删除
这里我们也是先把phead的上一级指针赋给tail
再将tail的上一级指针赋给phead的上一级指针
也就是指向要删除结点的上一结点
最后将要删除结点的前一个结点的下一级指针指向头结点
然后释放掉tail的内存空间完成尾删

3.5 双向链表头插

双向链表头插（ListPushFront）
代码如下：

void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* next = phead->next;

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

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

这里我们先和尾插一样将要插入的元素值赋给临时结点newnode
将phead下一级指针赋给临时结点next
再将newnode赋给phead下一级指针
也就是把phead的尾部指针指向newnode
把phead赋给newnode的上一级指针
再将next赋给newnode的下一级指针
最后把newnode赋给next的上一级指针，完成头插

3.6 双向链表头删

双向链表头删（ListPopFront）
代码如下：

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//防止链表中无元素继续删除的断言

	LTNode* next = phead->next;
	LTNode* nextNext = next->next;

	phead->next = nextNext;
	nextNext->prev = phead;
	free(next);
}

和尾删一样这里的第二个断言也是为了防止链表中无元素继续删除
头删的第一步就是将phead的下一级指针赋给next
再将next的下一级指针赋给nextNext
再将nextNext赋给phead的下一级指针
最后将phead赋给nextNext的上一指针
把next的内存空间释放完成头删

3.7 双向链表查找

双向链表查找（ListFind）
代码如下：

LTNode* ListFind(LTNode* phead, LTDateType x)
{
	assert(phead);

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

这里的查找就是使用一个while循环遍历链表找到某节点的data符合要查找的值
找到了便返回结点，如果遍历一遍没找到，则返回空（NULL）。

3.8 在pos位置前插入

pos位置前插入（ListInsert）
代码如下：

void ListInsert(LTNode* pos, LTDateType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyListNode(x);

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

插入函数的实现首先创建第一个临时结点posPrev
把pos的上一级指针赋给posPrev
将要插入的元素x赋给newnode
再将newnode赋给posPrev的下一级指针
再将posPrev赋给newnode的上一级指针
再将pos赋给newnode的下一级指针
最后将再将newnode赋给pos的上一级指针完成插入操作
在这里我们可以利用ListInsert函数将前面的尾插和头插进行同义替换
双向链表尾插（ListPushBack）同义替换
代码如下：

void ListPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);
	ListInsert(phead, x);
}

双向链表头插（ListPushFront）同义替换
代码如下：

void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

3.9 删除pos位置的结点

删除pos位置的结点（ListErase）
代码如下：

void ListErase(LTNode* pos)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
	pos = NULL;
}

首先将pos的上一级指针赋给posPrev
再将将pos的下一级指针赋给posNext
再将posNext赋给posPrev下一级指针
最后把posPrev赋给posNext上一级指针
将pos内存空间释放，使pos等于空（NULL），完成删除。
同样的，我们也可以利用这个ListErase函数对尾删和头删进行同义替换
双向链表尾删（ListPopBack）同义替换
代码如下：

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListErase(phead->prev);
}

双向链表头删（ListPopFront）同义替换
代码如下：

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListErase(phead->next);
}

3.10 打印双向链表

打印双向链表（ListPrint）
代码如下：

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

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

这里的打印操作同样是利用while循环进行一遍遍历打印输出

3.11 销毁双向链表

销毁双向链表（ListDestroy）
代码如下：

void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	phead = NULL;
}

和打印函数原理一样，只不过这里是再进行遍历的同时进行逐个删除
最后将phead内存空间释放，令phead等于空（NULL）完成链表销毁操作。
在这里最后讲一下断言，在之前的单链表那一节的接口函数都有，写断言是为了让代码更健壮
一旦出现了编译错误，我们可以立马排查出问题出在哪里，这是一个不错的代码习惯
带头双向循环链表接口代码可能不是那么好理解，但是实现起来时，却更方便，所以带头双向循环链表对于我们来说是非常必要的知识点！

4、顺序表和链表的区别

特征	顺序表	链表
存储空间	物理上一定连续	逻辑上连续物理上不一定连续
随机访问	支持:O(1)	不支持：O(N)
任意位置插入或删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

5、结语

顺序表到这一篇就结束了，这里的带头双向循环链表可能在代码体现上不是那么容易理解，这需要我们不断的去进行学习和实操，如果知识光看，在数据结构这门课的学习上是不会有提高的，最重要的还是练习！！！

制作不易，如有不正之处敬请指出，感谢大家的来访，UU们的观看是我坚持下去的动力，在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！不要忘了一键三连呦！