【链表】双向循环带头链表-增-删-查(C语言)

半生瓜的blog

发布于 2023-05-12 21:19:19

2540

发布于 2023-05-12 21:19:19

文章被收录于专栏：半生瓜のblog半生瓜のblog

单链表存在的缺陷：

不能从后往前走,

找不到他的前驱,

指定位置删除增加尾删都要找前一个，时间复杂度都是O(n)

针对上面的这些缺陷的解决方案——双向链表。

实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：

单向、双向
带头、不带头——带哨兵位的头结点，这个结点不存储有效数据，好处是什么？尾插的判断更方便简单，带头就不需要二级指针了，（带头结点，不需要改变穿过来的指针，也就是意味着不需要传二级指针了。）
循环、非循环

无头单向非循环：结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等，另外这种数据结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头循环双向链表，另外，这个结构虽然复杂，但是使用代码代码实现的以后会发现结构带来许多优势，实现反而简单了。

带头双向循环链表

结构体创建

typedef int LSTNodeData;
typedef struct ListNode
{
	LSTNodeData data;
	struct ListNode* next;
	struct ListNode* prev;
}LSTNode;

创建结点

DBLSTNode* DBLSTCreat(DoubleListDataType x)
{
	DBLSTNode* newnode = (DBLSTNode*)malloc(sizeof(DBLSTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

初始化

有个小哨兵位的头结点，并且是一个循环状态。

DBLSTNode* DBLSTInit()
{
	//用一个返回值可以 替代二级指针
	DBLSTNode* phead = DBLSTCreat(0);
	//循环
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

销毁

void DBLSTDestory(DBLSTNode* phead)
{
	//找到第一个结点
	DBLSTNode* cur = phead->next;
	while (cur !=phead)
	{
		//保存下一个结点
		DBLSTNode* curNext = cur->next;
		free(cur);
		cur = curNext;
	}
	free(phead);
}

画图有利于双向链表的理解。

打印

void DBLSTPrint(DBLSTNode* phead)
{
	//如果链表是空的会发生错误吗?
	//不会。因为phead->next还是自己。
	DBLSTNode* cur = phead->next;//这里我容易忘记指向next
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

尾插

双向带头循环链表，结构虽然复杂了，但是更容易操作了。

这就是结构设计的优势。

void DBLSTPushBack(DBLSTNode* phead, DoubleListDataType x)
{
	//创建新结点
	DBLSTNode* newnode = DBLSTCreat(x);
	//找到尾结点
	DBLSTNode* tail = phead->prev;
	//插入-链接
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

头插

如果插入的时候链表是空的同样不会有影响。

有first这几个指针先动谁都行，没有first也可以，就是会有顺序要求。

示例：

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

void DBLSTPushFront(DBLSTNode* phead,DoubleListDataType x)
{
	//创建新结点
	DBLSTNode* newnode = DBLSTCreat(x);
	//拿到第一个结点
	DBLSTNode* first = phead->next;
	//插入-链接
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

头删

void DBLSTPopFront(DBLSTNode* phead)
{
	//保存第一个和第二个结点
	DBLSTNode* first = phead->next;
	DBLSTNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;
}

尾删

void DBLSTPopBack(DBLSTNode* phead)
{
	//找到最后的一个结点
	DBLSTNode* tail = phead->prev;
	//找到最后一个结点的前一个结点
	DBLSTNode* tailPrev = tail->prev;
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
	tail = NULL;
}

查找位置

DBLSTNode* DBLSTFind(DBLSTNode* phead,DoubleListDataType x)
{
	//从第一个结点开始往下寻找，找到返回结点
	DBLSTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

使用：

DBLSTNode* pos = DBLSTFind(phead,x);
if(pos)
{
	printf("找到了");
}
else
{
	printf("没找到");
}

删除pos位置的值

void DBLSTErase(DBLSTNode* pos)
{
	//找到pos的前一个
	DBLSTNode* posPrev = pos->prev;
	//找到pos的后一个
	DBLSTNode* posNext = pos->next;
	//链接pos的前一个和pos的后一个
	posPrev->next = posNext;
	posNext->prev = posPrev;
	//释放pos
	free(pos);
	pos = NULL;
}

在pos前插入x

void DBLSTInsert(DBLSTNode* pos, DoubleListDataType x)
{
	//知道pos前的一个结点
	DBLSTNode* posPrev = pos->prev;
	//创建新的结点
	DBLSTNode* newnode = DBLSTCreat(x);
	//将新的结点插入
	newnode->data = x;
	newnode->prev = posPrev;
	posPrev->next = newnode;
	newnode->next = pos;
	pos->prev = newnode;
}

返回链表的结点数量

int DBLSTSize(DBLSTNode* phead)
{
	//其实就是遍历一遍，找一个计数的
	int count = 0;
	DBLSTNode* cur = phead->next;
	while (cur != phead)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

判断链表是否为空

bool DBLSTEmpty(DBLSTNode* phead)
{
	//定义一个cur指向第一个结点，如果第一个结点就是phead,说明链表为空
	DBLSTNode* cur = phead->next;
	if (phead == cur)
	{
		//空
		return true;
	}
	else
	{
		//不为空
		return false;
	}
}

优化

为了更快的实现一个双向循环的带头链表，我们可以直接利用Insert和Erase。

如果Erase的pos位置是第一个结点，那就代表着头删，如图：

所以头删还可以这样写：

void DBLSTPopFront(DBLSTNode* phead)
{
    DBLSTErase(phead->next);
}

尾删同理：

void DBLSTPopBack(DBLSTNode* phead)
{
	DBLSTErase(phead->prev);
}

头插：

void DBLSTPushFront(DBLSTNode* phead,DoubleListDataType x)
{
	DBLSTInsert(phead->next,x);
}

尾插：

其实就是插到头结点phead的前面。

void DBLSTPushBack(DBLSTNode* phead, DoubleListDataType x)
{
	DBLSTInsert(phead, x);
}

总结

带头双向循环链表，任意位置插入和删除数据，时间复杂度都是O(1)。

查找最优的结构不是这个，查找就得遍历，时间复杂度还是O(N)。

查找的最优结构有三种：

平衡搜索树（AVL树和红黑树）
哈希表
B树 & B+树系列 (数据库底层核心引擎)

全部代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DoubleListDataType;
typedef struct DoubleListNode
{
	DoubleListDataType data;
	struct DoubleListNode* next;
	struct DoubleListNode* prev;
}DBLSTNode;
//创建结点
DBLSTNode* DBLSTCreat(DoubleListDataType x)
{
	DBLSTNode* newnode = (DBLSTNode*)malloc(sizeof(DBLSTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
//初始化
DBLSTNode* DBLSTInit()
{
	//用一个返回值可以 替代二级指针
	DBLSTNode* phead = DBLSTCreat(0);
	//循环
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
//销毁链表
void DBLSTDestory(DBLSTNode* phead)
{
	//找到第一个结点
	DBLSTNode* cur = phead->next;
	while (cur !=phead)
	{
		//保存下一个结点
		DBLSTNode* curNext = cur->next;
		free(cur);
		cur = curNext;
	}
	free(phead);
}
//打印结点
void DBLSTPrint(DBLSTNode* phead)
{
	//如果链表是空的会发生错误吗?
	//不会。因为phead->next还是自己。
	DBLSTNode* cur = phead->next;//这里我容易忘记指向next
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//尾插
void DBLSTPushBack(DBLSTNode* phead, DoubleListDataType x)
{
	//创建新结点
	DBLSTNode* newnode = DBLSTCreat(x);
	//找到尾结点
	DBLSTNode* tail = phead->prev;
	//插入-链接
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
	//或者
	//DBLSTInsert(phead, x);
}
//头插
void DBLSTPushFront(DBLSTNode* phead,DoubleListDataType x)
{
	//创建新结点
	DBLSTNode* newnode = DBLSTCreat(x);
	//拿到第一个结点
	DBLSTNode* first = phead->next;
	//插入-链接
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
	//或者
	//DBLSTInsert(phead->next,x);
}
//头删
void DBLSTPopFront(DBLSTNode* phead)
{
	//保存第一个和第二个结点
	DBLSTNode* first = phead->next;
	DBLSTNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;
	/或者
	//DBLSTErase(phead->next);
}
//尾删
void DBLSTPopBack(DBLSTNode* phead)
{
	//找到最后的一个结点
	DBLSTNode* tail = phead->prev;
	//找到最后一个结点的前一个结点
	DBLSTNode* tailPrev = tail->prev;
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
	tail = NULL;
	//或者
	//DBLSTErase(phead->prev);
}
//查找位置
DBLSTNode* DBLSTFind(DBLSTNode* phead,DoubleListDataType x)
{
	//从第一个结点开始往下寻找，找到返回结点
	DBLSTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
//删除pos位置的值
void DBLSTErase(DBLSTNode* pos)
{
	//找到pos的前一个
	DBLSTNode* posPrev = pos->prev;
	//找到pos的后一个
	DBLSTNode* posNext = pos->next;
	//链接pos的前一个和pos的后一个
	posPrev->next = posNext;
	posNext->prev = posPrev;
	//释放pos
	free(pos);
	pos = NULL;
}
//在pos前插入x
void DBLSTInsert(DBLSTNode* pos, DoubleListDataType x)
{
	//知道pos前的一个结点
	DBLSTNode* posPrev = pos->prev;
	//创建新的结点
	DBLSTNode* newnode = DBLSTCreat(x);
	//将新的结点插入
	newnode->data = x;
	newnode->prev = posPrev;
	posPrev->next = newnode;
	newnode->next = pos;
	pos->prev = newnode;
}
//返回链表的结点数量
int DBLSTSize(DBLSTNode* phead)
{
	//其实就是遍历一遍，找一个计数的
	int count = 0;
	DBLSTNode* cur = phead->next;
	while (cur != phead)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
//判断链表是否为空
bool DBLSTEmpty(DBLSTNode* phead)
{
	//定义一个cur指向第一个结点，如果第一个结点就是phead,说明链表为空
	DBLSTNode* cur = phead->next;
	if (phead == cur)
	{
		//空
		return true;
	}
	else
	{
		//不为空
		return false;
	}
}
void Test1()
{
	DBLSTNode* phead = DBLSTInit();
	DBLSTPushBack(phead, 1);
	DBLSTPushBack(phead, 2);
	DBLSTPushBack(phead, 3);
	DBLSTPushBack(phead, 4);
	DBLSTPushFront(phead, 0);
	DBLSTPrint(phead);
	//DBLSTNode* pos = DBLSTFind(phead, 3);
	//if (pos)
	//{
	//	DBLSTErase(pos);
	//}
	DBLSTPrint(phead);
	int Count = DBLSTSize(phead);
	printf("%d", Count);
	DBLSTEmpty(phead);
	if (DBLSTEmpty(phead) == 0)
	{
		printf("不为空\n");
	}
}

int main(void)
{
	Test1();
	return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2021-06-01，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构