双向链表指的是链表上每个节点有两个指针，分别指向前节点和后节点。在单向链表中若需要查找某一个元素时，都必须从第一个元素开始进行查找；而双向链表每个节点中存储有两个指针，这两个指针分别指向前一个节点的地址和后一个节点的地址，这样无论通过哪个节点都能够寻找到其他的节点（即添加一个尾指针，这样就可以从后向前查找），如下图所示。

　　双向链表删除元素时需要注意，它有一个指向前一个节点的指针和一个指向后一个节点的指针，当节点被删除时，前一个节点的指针会指向被删除节点的后一个节点，而被删除节点的后一个节点的指针会指向被删除节点的前一个节点。注意：如果有尾指针，删除尾节点还要考虑尾指针的指向移动问题。

　　例题１：双向链表的追加和遍历。

　　双向链表的追加和遍历在程序上需要在节点中增加一个指向前一个节点的指针，因为节点可以从后向前回溯，所以在双向链表类中增加一个链表尾指针指向链表的尾节点。其算法逻辑如下：

　　(1)追加操作可以直接通过尾指针找到尾节点，将尾节点的next指针指向新节点，新节点的前驱指针指向原尾节点，再将尾指针指向新节点，使之成为新的尾节点。

　　(2)双向链表的遍历既可以通过头指针向后遍历，也可以通过尾指针向前遍历。

　　程序代码：

　　运行结果：

　　练习１:插入连续10个奇数，然后用两种方法遍历。

　　例题２：双向链表的随机插人和删除。

　　双向链表的随机插入、随机删除与单向链表的操作差不多，区别在于：双向链表由于同时有指向前后的指针，所以可以直接找到待插入或待删除节点本身，在此节点上直接操作。其算法逻辑如下：

　　(1)随机插入：循环到指定下标的节点，在指定节点和指定节点的前节点之间与两节点建立关系，完成插入；头尾节点特殊处理，头节点前驱为空，尾节点后驱为空，插入后还必须让头指针或尾指针指向新节点。

　　(2)随机删除：循环到指定下标的节点，在指定节点的前节点和指定节点的后节点之间建立关系，取出删除节点；头尾节点特殊处理，头尾节点删除后，链表的头尾指针需要移动到被删除节点的后一个节点或前一个节点。随机插入和随机删除算法图解如下。

随机插入如下图所示

随机删除如下图所示

　　程序代码：

　　运行结果：

　　练习２：把上例改为头尾和索引6的地方插入99，然后删除头尾和索引3节点。

　　例题3：双向链表实现插值法排序。

　　所谓插值法排序，是指将待排序的数组中的数据逐个取出，然后在另一个链表中找到合适的位置插入数值，最终使整个链表中的数据成为按顺序排列。链表中执行插值法排序，可以使用前插比较法（用单向链表即可）和后插比较法（必须用双向链表），本例采用后插比较法。

　　链表插值法排序算法：声明一个双向链表，将待排序数列中的元素，逐一与双向链表中的数据从队尾向队头做比较（前插比较法则是从队头向队尾做比较），如果新元素的数值小于前面的元素，则继续与更前一个元素比较，直到找到大于前面元素的位置，然后在此位置执行插入操作。如果整个链表中没有比新元素更小的元素，则插入在链表头部。分解动作解析如下：

　　(1)循环整个数列，逐一取出每个元素。

　　(2)在双向链表中声明一个按排序插入节点的方法。

　　(3)每次插人，均需通过尾指针取出队尾节点，用数组中取出的元素在链表中从尾到头进行逐一比较大小，如果新元素比节点中元素数值小，则继续向更前一个元素比较，如果比某个元素数值大，则在此位置执行链表插入，若比较到尽头则插人到链表头部。双向链表实现插值法排序的算法图解如下图所示。

　　程序代码：

　　运行结果：

　　练习３：利用双向链表的头尾指针２种方法插入排序下面的数列：32,6,81,5,9,44,3,6,143,66,99。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。更多课程请打开“学思营”同步网站：http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社