在这之前，小编已经讲了数据结构中的顺序表以及单向链表，接下来我们将更进一步，继续来讲双向链表!

结合之前，我们先来复习一下单向链表，单向链表是这样的：

1.概念：相较于顺序表在物理上和逻辑上都是连续的，单链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

2.结构：链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉或加上，不会影响其他车厢，每节车厢都是独⽴存在的。

在单链表中，单链表的每一个节点都是一个结构体，结构体中包含了一个数据以及指向下一个节点的指针，而接下来要讲的双链表与其有略微不同，如下图：

这是一个双向带头链表

注意：这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨的” “哨兵位”存在的意义就是为了方便我们更好的遍历循环链表避免死循环。

接下来就要开始讲解双向链表的实现了！

双向链表的实现

如之前一样，我们也是先创建了三个文件；

1.定义结构体

这里我们在List.h文件中定义了一个结构体，并将其改名为了LTNode，如上图结构体中的两个指针分别用来保存前一个和后一个结构体（节点）的地址，另还有一个date数据用来存储数据。

然后我们再在test.c文件中定义plist指针。随后我们的下一步就是初始化链表了！

2.初始化

在这里，我们的初始化就是创建一个哨兵位，所以我们首先要写一个用来申请节点的函数，如下：

//申请节点
LTNode* LTBuyNode(Type x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	node->data = x;
	node->next = node->prev = node;
	return node;
}

注意，在我们申请完结点之后，我们需要让这个节点的前后指针都指向自己！

申请完节点之后，由于哨兵位只是起”放哨“作用，所以这里我们就将哨兵位结构体中的data数据设为-1；如下

到这里，我们的初始化工作就算完成了！接下来我们就可以开始链表的增删改查工作了！

3.尾插

我们先来看以下代码：

//尾插
void PushBack(LTNode* phead, Type x)
{
	assert(phead);
	LTNode* node = LTBuyNode(x);
	node->prev = phead->prev;
	node->next = phead->next;

	phead->prev->next = node;
	phead->prev = node;

}

看到这个代码，小伙伴们是不是有点疑惑了，不着急，我们我们需要结合图来看

还是这个图，这里我们是尾插，想象我们新创建了一个节点d4，看这个图，再解红我们的代码，很容易就可以看出上面的代码到底指向的是什么。所以小伙伴们，在以后写代码的学习过程中，画图是非常重要的！！

接下来我们就来讲头插！

4.头插

同样先看以下代码：

//头插
void PushFrond(LTNode* phead, Type x)
{
	assert(phead);
	LTNode* node = LTBuyNode(x);
	node->next = phead->next;
	node->prev = phead;

	phead->next->prev = node;
	phead->next = node;

}

头插与尾插差不多，结合代码看图就可以很容易看懂，但这里与前面尾插同样有一个点需要注意，就是在上面代码中phead->next->prev = node;和phead->next = node;这两行的顺序可不能更改，若更改的话，我们就无法找到phead->next->prev这个节点了！

5.尾删

看以下代码：

//尾删
void PopBack(LTNode* phead)
{
	//链表必须有效并且不能为空（只有一个哨兵位）
	assert(phead && phead->next != phead);

	LTNode* p1 = phead->prev;
	p1->prev->next = phead;
	phead->prev = p1->prev;
	//删除p1节点
	free(p1);
	p1 = NULL;
}

尾删比较简单，我们只需要先创建一个节点并将最后节点存在这个节点中，这是为了方便我们后续通过这个节点找到其他节点，并释放这个节点。

这里还有需要注意的是assert(phead && phead->next != phead)，这里assert需要同时判断两个节点因为链表必须有效并且不能为空（只有一个哨兵位）！！

最后就是头删了

6.头删

//头删
void PopFrond(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* p1 = phead->next;
	phead->next = p1->next;
	p1->next->prev = phead;
	//删除节点
	free(p1);
	p1 = NULL;
}

头删与尾删基本差不多，比较简单，它的注意事项也与尾删相同，这里小编就不重复讲述了。

到这里，我们的双拉链表就基本讲完了，当然，还有在指定位置插入数据和删除数据，这个与小编上面讲的插入和删除异曲同工，仅仅只需要我们先找到我们要删除或插入的节点的位置，然后再将他们的地址作为参数上传就可以直接进行更改了！小伙伴们下去后要多多尝试哦！在尝试的过程中大家不要忘了画图，画图可是非常重要的！！

双链表的基本操作已经讲完，大家点个关注，防止迷路，欢迎大家共同学习交流！！！