玩转带头双向链表——【数据结构】_带头链表

W...Y的主页

今天我们接着来说数据结构——带头双向链表

目录

带头双向链表的实现

结构体的创建

初始化兵创建哨兵节点

释放链表所以内容 

打印链表函数

尾插

尾删

头插

​编辑

头删

计数函数实现

查找数据相应位置函数

在pos位置之前插入 

在pos位置删除 

顺序表与链表的差别

---

带头双向链表（Doubly Linked List with Head）相对于普通的双向链表，添加了一个头节点（head node），头节点不存储任何实际的数据，仅用于指示链表的起始位置。下面是带头双向链表的一些优点：

1. 链表操作方便：带头双向链表提供了直接访问链表头部和尾部的能力，使得链表的插入、删除等操作更加高效。你可以通过头节点快速插入第一个元素，也可以通过尾节点快速插入新元素。同时，由于链表的双向性，你可以轻松地在链表中的任意位置进行插入和删除操作。

2. 遍历灵活性：带头双向链表可以从头到尾或从尾到头两个方向遍历。这意味着你可以根据需要选择合适的遍历方式，无论是从前向后还是从后向前遍历链表，都能方便地获取元素。

3. 反向查找：带头双向链表的一个重要优点是可以通过后向链接（back link）从任意节点快速访问该节点的前一个节点。这使得在链表中进行反向查找变得高效。与单链表相比，带头双向链表的反向查找时间复杂度从O(n)降至O(1)，这对某些应用程序可能非常重要。

4. 方便的删除节点：在带头双向链表中，删除一个节点不需要访问其前一个节点，只需修改当前节点的前后链接即可。这样，节点的删除操作变得更为方便和高效。

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。

带头双向链表的实现

结构体的创建

typedef int LTDataType;
 
typedef struct ListNode
{
	int data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

创建结构体使用typedef将其改名LTNode方便使用，创建next和prev节点用来保存下一个节点与上一个节点。

初始化兵创建哨兵节点

我们创建哨兵位时，可以在data中间增加-1，创建好后将next与prev全部指向自己。但是这个功能与怎加节点函数内容及其相似，所以我们可以先创建节点函数，然后再初始化哨兵位时将其调用即可，防止冗余现象。

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->data = x;
	node->prev = NULL;
	return node;
}

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
 
	return phead;
}

 我们再创建好两个函数时，让LTInit函数去调用BuyLTNode函数，将哨兵位初始化即可。

释放链表所以内容 

因为链表使用realloc开辟的空间全部在堆区，所以必须将链表开辟的空间全部释放，防止内存泄漏。

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

打印链表函数

在打印链表时，我们要将次链表与单链表区分。单链表只需找到尾NULL即可停止，而双向链表的尾部指向哨兵位，所以我们可以换一种方法进行检测。

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

我们创建一个遍历指针cur，让cur = phead->next指向哨兵位下一个节点。然后进行遍历，如果遍历返回到哨兵位phead停止即可。

尾插

尾插相对于单链表也非常方便，不用遍历找尾节点，只需要访问phead的prev即可找到尾节点。 

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
 
	newnode->prev = tail;
	newnode->next = phead;
	tail->next = newnode;
	phead->prev = newnode;
}

尾删

我们首先得检测phead哨兵位是否为空，如果链表为空我们也不能正常进行删除，所以我们得继续判断phead->next != phead。自己的下一个节点不能指向自己。

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next = phead;
	free(tail);
 
}

删除就非常简单，访问最后一个节点记作tail，将phead连接尾节点的地址切换成尾节点的上一个节点，然后将尾节点上一个节点的next换成哨兵位地址，free掉tail尾节点即可。 

头插

头插与尾插原理基本相同，只需要将哨兵位的内容进行改变即可。

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	/*newnode->next = phead->next; 
	phead->next->prev = newhead;
	phead->next = newhead;
	newhead->prev = phead;*/
	LTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	first->prev = newnode;
	newnode->next = first;
}

 我们可以参照上述代码进行头插，分别有两种方法。第一种(已注释)是不创建任何指针变量进行交换替代，第二种(未注释)即创建变量进行交换。第一种方法再交换次序上必须严谨，先进行尾节点的交互，再进行首节点的交互，否则会交换失败出现错误数据。

头删

在删除时，务必检测链表是否为空，链表是否只有哨兵位方可进行删除操作。

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* first = phead->next;
	LTNode* second = first->next;
	free(first);
	phead->next = second;
	second->prev = phead;
}

计数函数实现

当我们录入数据量过大时，为了方便计数所创建的函数。‘

int LTsize(LTNode* phead)
{
	assert(phead);
	int size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

这里只需遍历链表种的每一个节点直到返回到哨兵位即可。

查找数据相应位置函数

当操作人员想知道某个数据在链表中的位置并进行操作时，我们即可调用此函数来返回相应数据所在节点的地址。

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

这里我们使用暴力查找的算法进行整组链表搜索，找到对应数据即可返回。

在pos位置之前插入 

这里我们就需要与查找位置函数进行联动配合进行调用。

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	posprev->next = newnode;
	newnode->next = pos;
	newnode->prev = posprev;
	pos->prev = newnode;
}

这里其实与头插尾插原理一样，所以我们也可以用此函数进行头插尾插，只需将pos参数传入正确，分别为phead->next(头插)、phead->prev(尾插)。

在pos位置删除 

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	free(pos);
	posprev->next = posnext;
	posnext->prev = posprev;
}

这里也是与头删尾删原理相同，只需将参数传入正确即可变成头删和尾删。

顺序表与链表的差别

所以在不同情况下选择不同的数据结构时是很关键的，我们需要足够了解其中的差别与优势，才能满足各种问题下不同的需求。