双向链表的实现

一.概念与结构

双向链表区别于单链表不同的地方在于，双链表多出于一个指针能指向前面结点，使得整个链表得以首位相连。带头链表里的头结点称为哨兵位，哨兵位结点不储存任何有效元素，只是放哨功能。

二.实现双链表

2.1双链表结构

 由前后指针和保存的数据构成。

下面是将要实现的功能

 2.2申请节点与初始化

首先我们需要开辟一个空间，使用malloc为节点开辟一个空间，存入数据x，将前后指针指向自己，最后返回一个结点。注意malloc的时候需要指明节点的类型，以及节点的大小。

接着我们到初始化，运用上面的申请节点的方法，设置一个哨兵位节点。返回即可。

 2.3头插尾插

相关的头插和尾插都要先处理新插入进来的结点，再处理前后两节点。这样不会存在找不到前后节点的情况，同时能减少代码量。

尾插头插，首先先申请一个结点。接着先处理新节点的前后指针，将其插入。随后再断开前后两个节点的指针重新串联。

 相关细节处理，所传的指针不能为空。

2.4打印

将所传的指针重新用一个结点接受，这样不会影响原先的指针，随后通过while循环逐一遍历链表，直到节点的下一个指针为null。

 2.5头删与尾删

在头删和尾删之前需要对所传的链表进行判断判断是否为空。若不为空方可进行下面的步骤。与插入相反，头删和尾删需要先将所删结点的前后节点先建立好关系，最后再删除需要删的结点，若是先进行删除操作，会导致找不到前后节点，链表就不连续。

 这里通过申请一个del节点，作为中间桥梁，减少了代码的繁琐不宜出错，在最后也要将delfree掉并且置位空。

2.6查找节点

首先需要查找结点那么我们必定要去遍历链表，那么就会运用到循环，那么循环的条件是什么呢？

这里我们运用一个prev指针，指向哨兵节点的下一个结点，通过循环遍历，直到下一个结点不是哨兵结点才停止，这样我们便可以完整的遍历整个链表。

 若找到了这个结点就返回，若未找到则返回null。

2.7销毁链表

这里传了一个二级指针，用于指向*phead的地址。通过创建一个pcur向后遍历，用next节点保存下一位，然后不断的free，最后将*pphead至为空。