带头循环双向链表是链表中效率最高的，但是由于他里面有两个指针节点，所以也会更浪费空间一些，但是他在任意位置的插入删除的效率很高，所以也就弥补了顺序表的不足。

首先我们来看一下他的逻辑结构是什么样子的

 

 

下面我们看一下如何实现

首先我们先看一下这个带头循环双向链表的每一个节点是怎么样的

 

这里我们可以看到，里面有一个保存数据的变量data，还有两个该结构体类型的指针，其中一个是prev另一个是next分别代表上一个和下一个

在下面我们看一下带头循环双向链表至少需要哪些函数

 

这里是头文件，这里有着函数的声明，我们可以看到我们要实现的函数。

下面我们依次介绍这些函数

首先我们来看一下初始化

 

在初始化函数中，我们需要传过来二级指针，因为这里我们需要有一个头节点，所以我们需要改变外面传过来的变量，这里我们需要断言一下，然后我们就可以new一个节点，然后给给*pphead 这样我们就可以改变他，让他成为头节点，然后把他里面的dada给一个值（该值无任何意义）我们需要将他里面的内容都初始化，然后将他的两个指针都指向自己，因为这里只有他一个节点。

里面提到了一个BuyNode的一个函数，我们这里介绍一下

这里的buynode其实就是new一个节点，然后将该节点指向的空间初始化并赋值，然后返回new出来的节点，该函数会在众多插入中使用

下面我们看一下pushback

我们来看一下，首先我们断言的地方是因为这里绝对不能出现的，就比如不小心将第一个参数传为了空，下面我们来看一下，我们继续new一个节点初始化并赋值，然后我们是尾插入，所以我们可以插入到头节点的前面，这样就是尾插了。

下面我们来看一下 打印函数，我们就知道为什么插入在头节点的前面就相当于是尾插

我们的打印函数，这里我们定义一个cur但是这个指针并不指向头节点，而是头节点的下一个节点，所以当该指针打印完一遍之后又会回到头节点，但是头节点的值实际并没有任何意义，所以我们可以让cur指向头节点时为结束条件，这样我们就可以打印了

 下面我们看一下头插

其实这里的双向带头循环链表，看起来比单链表的结构体更复杂一些，但是实际写起来是要比单链表简单一点点的，而且这里的头插也是特别简单，我们直接记录好头节点的下一个节点，然后new一个几点并赋值，将该节点链接上即可

 下面我们在看一下尾删

这里面以及后面的断言我就不一一阐述了，这里记住，但凡是有绝对不可能出现的情况就需要断言，因为这里的断言可以帮助我们省去很多的麻烦，所以记住该断言的地方就断言，

这里我们可以看到，我们首先就判断了该链表是否为空（IsEmpty下一个说） 如果是空的话返回，表示无法删除，但是这里也可以断言，因为是空的话就不能删除，所以这里也可以使用断言，下面我们就可以开始删除了，我们需要记录头节点前一个位置，自己头节点前前一个位置，因为删掉头节点前一个位置后，是需要保证前前一个位置和头节点的链接的，所以记录好之后再删除掉尾节点，然后再链接好前前一个节点和头节点

上面我们提到了一个IsEmpty函数，该函数用来判断是否为空下面我们看一下

判断是否为空其实不难，我们可以想一下，带头循环双向链表如何为空，或者是在什么情况下为空，或者就是他一个节点都没有的时候他的逻辑结构是什么样子的，是的！当他的next节点指向自己或者prev指向自己的时候表示没有一个节点，所以就为空，我们返回true即可，反之则有数据不为空，返回 false

下面我们来看一下头删

头删其实也并不难，只需要记录头节点下一个的下一个节点的位置然后再删除头节点的下一个位置就可以了，不过这里也需要注意保证好链接关系。

 下面我们可以看一下查找函数

查找函数，当某一个节点的值和x相等时返回该节点的指针，如果查找到头节点了还没有找到则为空。

下面我们来看一下insert和erase是任意位置的插入和删除 

这里我们需要注意的是我们插入的位置是一个该类型的指针，所以这个函数需要和我们的find函数联动，我们记录pos位置前一个节点然后就可以插入了。

 

删除也是一样的，也是pos位置的节点，我们记录pos的前一个和后一个，就可以删除pos。 这里我们还传了一个头节点，其实这里是不需要传头节点的 （因为C语言的需要缺陷，这里我们可以看到，如果我们pos传成头节点话会怎么样？明显会崩溃掉，逻辑结构错误，所以我们需要和头节点比较一下，如果pos和头节点相同的话就不能删除）。

最后我们来看一下销毁函数

关于销毁函数我们就可以删掉所有的节点后在删除头节点，就是销毁，所以我们可以直接调用头删或者尾删，所以while循环可以用isempty判断，这里我忘记用了，不过都是一样的，等删的只剩下头节点后，我们可以free掉头节点，然后就销毁了。

看到这里基本就结束了，但是我们实际上是增删查改，里面没有改，这里是为什么？因为这里我们想一下find函数我们查找到后返回了该节点的指针，所以我们可以 解引用后修改该节点，所以find也可以充当修改。