下载掌阅APP，畅读海量书库
立即打开
双向链表也称作双链表，是链表的一种。双向链表是有前后两个方向的。与单链表不同的是，双向链表带有两个引用：一个是指向后一个结点（通常称作后继结点）的引用；另一个是指向前一个结点（通常称作前驱结点）的引用。
双向链表第一个结点称作头结点，可以从头结点开始向后正向遍历双向链表中的元素。头结点无前驱结点。双向链表的最后一个结点称作尾结点，可以从尾结点开始向前逆向遍历双向链表中的元素。尾结点无后继结点。双向链表如图2-15所示。
图2-15 双向链表示意图
单链表只能从一个方向访问链表中的元素（通常是从前向后依次访问）。与单链表相比，双向链表的明显优势在于，双向链表可以方便地从两个方向（从前向后和从后向前）访问其中的元素。
向双向链表中添加元素需要修改前一个结点的后继结点的引用和后一个结点的前驱结点的引用。
双向链表添加元素前如图2-16所示。
图2-16 双向链表添加元素之前示意图
在双向链表第i个位置添加元素后的示意图如图2-17所示。
图2-17 双向链表添加元素之后示意图
双向链表的查找可以分为两种情况：一种是从头向尾查找元素；另一种是从尾向头查找元素。双向链表查找元素的示意图如图2-18所示。
图2-18 双向链表查找元素示意图
双向链表删除元素是双向链表添加元素的反向操作。
双向链表删除element元素之前如图2-19所示。
图2-19 双向链表删除元素之前示意图
双向链表删除element元素之后的示意图如图2-20所示。
图2-20 双向链表删除元素之后示意图
从双向链表可以看出，双向链表的头结点没有前驱结点，双向链表的尾结点没有后继结点。为了解决头尾结点的问题，诞生了双向循环链表。双向循环链表在双向链表的基础上将头结点和尾结点进行首尾相连。双向循环链表如图2-21所示。
图2-21 双向循环链表示意图
双向链表只是在单链表的基础上增加了一个“反向单链表”。双向循环链表是在双向链表的基础上使双向链表首尾相连。读者可以参考单链表的实现，自行开发实现双向链表和双向循环链表。
（1）双向链表的概念：双向链表可以看成是由两个方向相反的单链表组成的。双向链表既可以从前向后遍历，又可以从后向前遍历。
（2）双向链表的存储：双向链表是使用离散的存储结构存储数据的。双向链表中每个结点都有一个指向前驱结点的引用和指向后继结点的引用。
（3）双向链表的优点：
· 双向链表不需要使用连续的存储空间存储数据。
· 双向链表没有固定的容量。
· 添加或删除单链表中的元素只需修改相关结点的引用，无须移动其他元素。
· 双向链表可以从正反两个反向进行遍历。
· 双向循环链表相比于双向链表，每个结点的属性都是完整的，没有需要单独处理的结点（不存在前驱结点或者后继结点为空的结点）。
（4）双向链表的缺点：
· 访问双向链表中的元素必须从第一个结点或者从最后一个结点开始遍历，依次访问下一个结点，直至找到所需的元素位置。因此，访问双向链表的时间复杂度为O(n)。
· 双向链表每个结点保存了前驱结点和后继结点的引用，每个结点占用更多的存储空间。
（5）JDK中的实现：JDK中的LinkedList实现了双向链表，并提供更多高级特性，详情可参见4.3节。