带头双向循环链表

在前面我们学习了单链表，发现单链表还是有一些不够方便，比如我们要尾插，需要遍历一遍然后找到它的尾，这样时间复炸度就为O(N),现在我们引入双向带头链表就很方便了，我们先看看它的结构。

通过观察，我们发现一个结构体里面我们存两个指针，一个指向前面的，一个指向后面的，这样就是双向了，头指针指向尾，我们找尾，只需要通过头指针找，很方便，我们找一个指针节点上一个，也很便利，如果是单链表，我们还需要从头开始找。所以是带头双向循环链表真的很方便。

我们先创建一个结构体，接下来就是对它初始化了。

因为我们我们是带头的，这个哨兵位的头需要在初始化的时候创建，后面我们插入数据也需要创建节点，所以我们就将创建节点的过程写成一个函数。

我们利用一个函数创建节点，初始化时结构体里面的指针指向自己

带头双向循环链表也和单链表一样，有头插，尾插，头删，尾删，在某个位置前插入，删除。

我们先来看看插入的操作，头插

头插，我们只需要改连接关系就好。
首先，我们创捷一个节点。
然后，在哨兵的后面插入节点，改变连接关系就可以完成连接。

尾插的插又怎么实现呢？

在之前的单链表，我们还需要找尾，然后在尾的后面插入（改连接关系）

我们的带头双向循环链表的便利之处在于，我们可以快速的找到尾，我们哨兵位的prev就是链表的尾。

在某个位置前面插入我们应该怎么做？

在单链表，我们需要找到pos位置前面的地址，我们要从头开始找。带头双向循环链表的便利在于我们的pos的prev就是我们要找的地址。简单的修改连接关系，就能完成我们的插入。

写着写着，我们发现，我们在某个位置插入元素好像和头插，尾插，有相似的地址。
头插，就是在哨兵位后一个节点的前面插入，我们也可以利用在某处插入元素的函数，这样大大节省书写时间。
尾插，就是在哨兵位的前面插入，这个更加简单。
所以我们的头插，尾插，可以复用我们在某处插入的函数。

插入讲完了，下面我们来说说删除。

尾删，是怎么操作的？

在单链表我们需要找到尾，同时记录尾的前一个，我们将尾释放，将尾前一个的next置尾空指针.

头删的操作。

我们带头双向循环链表，有一个哨兵位，所以我们需要绕开它，然后删除它后面的第一个节点，然后修改连接关系。我们删除前需要判断链表是否为空。

我们发现删除好像都需要判断是否为空，我们前面的尾删也需要，所以我们需要在尾删的地方加上判断。

如何删除某个节点的，我们需要配合一个查找函数，来查找节点。

我们发现删除某个节点位置的函数也可以与头删，尾删复用。

尾删我们传哨兵位的prev

头删我们传哨兵位的next