双向链表

双向链表
术语名称	双向链表
英语名称	doubly linked list
别名	双链表

双向链表(doubly linked list)或双链表指逻辑结构为线性表、存储结构为链式存储结构（即属于链表），且结点间同时存在指向上个结点和下个结点的两个链接（头尾结点除外）。

在编程语言中，通常不直接提供链表结构。如果实际提供，通常都是双向链表而不是简单的单向链表。

在内存中，链表分配和访问内存的方式不符合访问局部性原理，对缓存不友好，执行效率会按照缓存与内存的访问时间比例成数量级地放大，因此通常会使用动态数组代替。但是动态数组中间插入时间复杂度较高，必须要插入中间段时，会使用块状链表作为代替。

外存中，文件间通过文件名的双向链表链接是常见做法，特别是用于文件很多且允许向文件间插入或删除文件的情况。

结构

双向链表中的每个结点可以抽象成如图所示结构。

其中含有数据域和指向上下两个结点的链接，链接通常画在数据域两侧（但是内存排布一般把两个链接放在一起），以便绘制成链。链接成一个链表时如下图所示。

这个结构只需要获取第一个或最后一个结点，就可以顺藤摸瓜地找到整个结构。如果只保存一个能取得第一个结点的数据，保存这个数据的变量通常称为 head ，也称为头指针(head pointer, head reference)。如果也保存用于取得最后一个结点的数据，保存这个数据的变量通常称为 tail 或 rear ，也称为尾指针(tail pointer, tail reference, rear pointer, rear reference)。

类似单向链表，有时也保存一个虚拟结点，称为头结点(head node)。头结点中的链接就相当于上一个方法中的头指针。具有头结点的双向链表往往被实现为双向循环链表，也就是说第一个和最后一个结点都和头结点相连接。