当前位置：首页 > article >正文

让双向链表不在云里雾里

article 2025/3/20 3:05:09

又来博客留下我的足迹了，哈哈哈，这次是对于双向链表的理解

创建双向链表：

申请结点：

双向链表初始化：

双向链表插入结点：

双向链表删除结点：

双向链表的打印：

双向链表的查找：

双向链表的销毁：

结语：

在双向链表中有头双向循环，无头双向循环，有头双向不循环，无头双向不循环，而我将要介绍的是有头双向循环，别看名字长，其实就是只纸老虎，只要我们理解它的结构，问题自然迎刃而解了结构图如下：

创建双向链表：

从上面的结构图我们不然发现，我们创建需要定义什么指针域和数据域

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;//指针域
	struct ListNode* next;//指针域
	LTDataType data;//数据域
}LTNode;

申请结点：

与单链表代码差不多，将其指针域置空，就不再过多赘述

LTNode* BuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//申请空间
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;//赋值
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;//返回创建的结点
}

双向链表初始化：

我们只需将自己连向自己，下一个指向上一个，上一个指向下一个，如图：

LTNode* LTInit()
{
	LTNode* phead = BuyNode(-1);//传空，为phead申请空间
	phead->next = phead->prev;
	phead->prev = phead->next;
	return phead;//返回头结点
}

双向链表插入结点：

头插：

我们先将新结点的后指针指向第一个结点的数据域，第一个结点的前指针指向新结点的数据域，新结点的前指针亦然，可能文字可能形容有点模糊，所以我们看下图：

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyNode(x);
	LTNode* Next = phead->next;//保存下一个结点的地址，防止丢失
	//新结点与后结点链接
	newnode->next = Next;
	Next->prev = newnode;
	//新结点与头节点链接
	newnode->prev = phead;
	phead->next = newnode;
}

温馨提示：如果没有保存下一个结点的地址，则需先跟后结点链接，在与头结点相连

尾插：

双链表尾插相对于单链表的尾插来说要容易许多，因为我们可以轻松找到尾，然后改变指针指向即可，如下图：

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyNode(x);//创建新结点
	LTNode* tail = phead->prev;//找尾
	//尾结点与新结点相连
	newnode->prev = tail;
	tail->next = newnode;
	//新结点与头结点相连
	newnode->next = phead;
	phead->prev = newnode;
}

在指定位置插入：

我们通常会在指定位置之前插入，找到指定位置前一个，然后改变指针方向即可，如图：

void LTInsert(LTNode* phead, LTNode* pos, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyNode(x);
	LTNode* front = pos->prev;//找到指定位置前一个结点
	//新结点与指定结点相连
	newnode->next = pos;
	pos->prev = newnode;
	//新节点与指定结点前一个结点相连
	front->next = newnode;
	newnode->prev = front;
}

双向链表删除结点：

头删：

我们先要判断链表是否为空，如果为空就不用删除了；因为之后要释放删除的结点，所以我们还需保存一下，这样就可以了

bool LTEmpty(LTNode* phead)
{
	return phead == phead->next;
}
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));//判断链表是否为空
	LTNode* del = phead->next;
	LTNode* Next = phead->next->next;
	//第一结点的下一个结点与头结点相连
	Next->prev = phead;
	phead->next = Next;
	free(del);//释放掉这个结点
	del = NULL;
}

尾删：

尾删就比较容易了，将尾结点释放，然后改变指针指向，就这样完成了^ - ^

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	//或assert(!LTEmpty(phead))
	LTNode* tail = phead->prev;
	LTNode* Pretail = tail->prev;
	//头节点与尾结点的前一个结点相连
	Pretail->next = phead;
	phead->next = Pretail;
	free(tail);//释放尾结点
	tail = NULL;
}

在指定位置删除：

找到要删除结点的前一个和后一个，然后两个结点相互链接，这样就能够删除了，如图：

void LTErase(LTNode* phead, LTNode* pos)
{
	assert(phead);
	LTNode* front = pos->prev;//找到前结点
	LTNode* back = pos->next;//找到后结点
	//前结点和后结点相连
	front->next = back;
	back->prev = front;
	free(pos);//释放指定节点
	pos = NULL;
}

双向链表的打印：

提到打印，我们会用到遍历循环，那循环结束的标志是什么呢？有一个好主意，我们可以先从第一个结点开始打印，然后向后循环遍历，直至遍历到头结点，循环结束^_^，如下图：

void LTPrint(LTNode* phead)
{
	LTNode* begin = phead->next;
	while (begin != phead)//循环继续条件
	{
		printf("%d<=>", begin->data);
		begin = begin->next;
	}
	printf("\n");
}

双向链表的查找：

遍历一遍链表，然后找要查找的元素

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

双向链表的销毁：

将动态申请的空间释放掉，并循环释放每一个结点，防止内存泄漏的风险

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	LTNode* next = cur->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;//防止找不到下一个结点
		free(cur);
		cur = next;
	}
	free(phead);//释放头结点
}