数据结构入门 — 链表详解_双向链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构入门 — 链表详解_双向链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

数据结构入门 — 双向链表详解
博客主页链接：https://blog.csdn.net/m0_74014525
关注博主，后期持续更新系列文章
文章末尾有源码
*****感谢观看，希望对你有所帮助*****

系列文章

第一篇：数据结构入门 — 链表详解_单链表
第二篇：数据结构入门 — 链表详解_双向链表
第三篇：数据结构入门 — 链表详解_循环链表

什么是双向链表

双向链表（Doubly Linked List）是一种链表数据结构，它的每个节点都含有两个指针，一个指向前一个节点，一个指向后一个节点。相比较于单向链表，双向链表可以双向遍历，即可以从头到尾或从尾到头遍历链表。在双向链表中，每个节点包含两个指针域和一个数据域。其中，一个指针指向前驱节点，另一个指针指向后继节点。这两个指针使得双向链表的插入、删除等操作不需要像单向链表那样需要遍历整个链表来寻找前驱节点，提高了链表的操作效率。

概念与结构（图文）

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

双向链表与单链表的区别

双向链表和单链表是两种不同的链表结构。

单向链表是一种链表，在每个节点中包含指向下一个节点的指针。这意味着在单向链表中，节点只能从头开始遍历到尾部。在单向链表中，每个节点只存储指向下一个节点的指针，而不存储指向前一个节点的指针。

双向链表是一种链表，在每个节点中包含指向下一个节点和前一个节点的指针。这意味着在双向链表中，节点可以被从头到尾或从尾到头遍历。在双向链表中，每个节点存储指向前一个节点和下一个节点的指针。

因此，双向链表可以更方便地进行双向遍历，但是需要更多的内存空间来存储每个节点的两个指针。相比之下，在单向链表中，只需要一个指针来指向下一个节点，因此内存占用量更小。

带头双向循环链表接口实现（代码演示）

带头+双向+循环链表增删查改实现

1. 动态存储结构

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

双向链表打印

void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("phead<->");
	//跳过哨兵位
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

增删查改接口

根据增删查改顺序编排
双向链表头插：

//头插
void  LTPushFront(LTNode* phead, STDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;
	newnode->next = first;
	first->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;

}

双向链表尾插：

//尾插
void LTPushBack(LTNode* phead, STDataType x)
{
	assert(phead);
	
	LTNode* newnode = BuyLTNode(x);
	//找到最后一个
	LTNode* tail = phead->prev;
	
	
	newnode->prev = tail;
	tail->next = newnode;
	

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

双向链表头删：

//头删
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;

}

双向链表尾删:

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;

	free(tail);
	
	phead->prev = tailprev;
	tailprev->next = phead;

}

查找：

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

	return NULL;
}

在指点位置插入：

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

}

在指点位置删除：

// 把pos删除
void LTErase(LTNode* pos)
{
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	free(pos);
	posprev->next = posnext;
	posnext->prev = posprev;
}

双向链表销毁

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

	free(phead);
	phead = NULL;
}