单向链表和双向链表的数据结构（单向链表和双向链表的数据结构区别）

大家好，我是讯享网，很高兴认识大家。

 <p><span style="color:#0d0016;"><strong>我要扼住命运的咽喉&#xff0c;他却不能使我完全屈服。                      --贝多芬</strong></span></p>

讯享网

一.带头循环的双向链表的特点

二.不带头不循环单向链表和带头循环的双向链表的对比

三.初始化链表，创建哨兵结点

四.双向链表的各种功能的实现

1.双向链表的尾插

2.双向链表的打印

3.双向链表的头插

4.双向链表的头删

5.双向链表的尾删

6.查找函数

7.在pos位置的前面插入一个数

8.删除pos位置的值

9.头插，尾插直接复用插入函数。头删，尾删直接复用删除函数

10.求双向链表的长度

11.最后销毁双向链表

五.双向链表全部的代码

1.List.h:

2.List.c:

3.test.c:

这里的带头就是带一个哨兵位的头结点，这个头结点只是在头位置起一个引导作用，不存放数据。
(后面我们会说头结点具体的作用)循环就是说双向链表是闭合起来的，头尾是相连起来的，双向的意思就是说一个结点有两个指针，一个next指针指向下一个结点，另一个prev指针指向上一个结点。

这是一个逻辑结构，也就是我们想象出来的结构，这大抵就是一个带头循环双向链表的结构。
带头双向循环链表：
结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个链表虽然结构复杂，但是使用代码实现以后会发现能带来很多优势。

带头双向循环链表其实看起来复杂，如果你理解了，其实实现起来要比单链表简单的。等会你就知道了。

带头循环的双向链表的创建:

讯享网

查找效率:单向链表，查找的方向只能是一个方向，从头开始向后查找。而双向链表可以向前或者向后查找。查找到一个结点之后，如果还要查找这个结点的前一个结点时，单链表又只有从前开始遍历链表进行查找，时间复杂度时O(N)。而双链表可以使用前一个指针找到前一个结点，时间复杂度是O(N)，双向链表效率更高。

单向链表不能自我删除，需要靠辅助节点 ，如果要删除中间的某个结点，你还必须要遍历找到你要删除结点的前一个结点。比较麻烦。

而双向链表就可以解决这个问题，如果你要删除某个结点，你只需要把使用prev指针直接找到前一个结点，使用next指针找到后一个结点，然后把它们链接起来，再free掉你要删除的结点，非常的方便。

关于头结点的使用:昨天我们写的单链表没有使用头结点，其实头结点的用处是非常大的。在不带头的单链表中，如果要头插，每次都会改变头结点的指针，所以我们昨天写的头插函数使用的是传址调用，也就是传了双指针。但是今天要学习的带头双链表，因为它带头结点，无论你是什么插入或者删除，头结点一直不会变，也就避免了使用双指针的问题。使用了头结点也不用考虑空指针的问题，它可以把它们统一处理。(这里我们等会会说)。

创建一个函数，在每次需要新的结点时，直接调用这个函数即可。

创建一个哨兵头结点，起一个链表的带头作用。

讯享网

这里为什么要写成phead->next=phead，phead->prev = phead呢?自己指向自己，这里等会会有大用处，可以将NULL的情况统一处理。非常的nice。

1.双向链表的尾插

这里尾插就会体现我们之前设置的头结点的优势和循环的优势，我们在已有的 1 2 3 后面插上4，我们会怎么做呢?我们要先找到尾，然后再尾后面插上4。下面图是原本的链表样子。我们的目的就是在3的后面再链接一个4。

我们先找到链表的尾，因为这个链表是循环的，所以链表的尾就是phead->prev，剩下的就依次把它们链接起来即可。

在上述中是表示的链表有内容的时候尾插，还是比较简单。在单链表尾插的时候，我们还要先判断一下链表是否为空。而这里双链表尾插需要考虑链表为空的情况吗?答案是不用，这里就体现了我们设置头结点好处，和之前设置的phead->next=phead，phead->prev = phead的好处。当链表为空的时候，也就是只有一个头结点。