3. 双向链表¶
3.1. 双向链表¶
单链表 只允许从线性表结点直接访问线性表中的下一个结点。 双向链表 则允许从线性表结点方便地访问下一个结点， 以及线性表中的前一个结点。 双向链表结点以显而易见的方式实现了这一点： 存储两个指针，一个指向后继结点（与单链表相同）， 另一个指向前驱结点。
使用双向链表最常见的原因是它比单链表更容易实现。
尽管双向链表实现的代码比单链表版本稍长，
但它的意图往往更加"直白"，因而更易于实现和调试。
线性表实现采用双向还是单向链接，
对 List 类的使用者应当是不可见的。
与我们的单链表实现一样，
双向链表实现也使用了 头结点 。
我们还会在线性表末尾添加一个尾部结点（tailer node）。
尾部结点与头结点类似：
它是一个不包含任何值的结点，并且始终存在。
双向链表初始化时会创建头结点和尾部结点。
数据成员 head 指向头结点， tail 指向尾部结点。
这些结点的目的是简化 insert 、 append 和 remove 方法——
当线性表为空，或者在表头、表尾处插入时，
都无需任何特殊情况的代码。
在我们的实现中， curr 将指向 当前位置
（若当前位置位于线性表末尾，则指向 尾结点 ）。
下面是用于双向链表的 Link 类的完整实现。
由于双向链表结点多了一个数据成员，
这段代码比单链表结点实现的代码稍长。
class Link<E> { // Doubly linked list node
private E e; // Value for this node
private Link<E> n; // Pointer to next node in list
private Link<E> p; // Pointer to previous node
// Constructors
Link(E it, Link<E> inp, Link<E> inn) { e = it; p = inp; n = inn; }
Link(Link<E> inp, Link<E> inn) { p = inp; n = inn; }
// Get and set methods for the data members
public E element() { return e; } // Return the value
public E setElement(E it) { return e = it; } // Set element value
public Link<E> next() { return n; } // Return next link
public Link<E> setNext(Link<E> nextval) { return n = nextval; } // Set next link
public Link<E> prev() { return p; } // Return prev link
public Link<E> setPrev(Link<E> prevval) { return p = prevval; } // Set prev link
}
class Link { // Doubly linked list node
private Object e; // Value for this node
private Link n; // Pointer to next node in list
private Link p; // Pointer to previous node
// Constructors
Link(Object it, Link inp, Link inn) { e = it; p = inp; n = inn; }
Link(Link inp, Link inn) { p = inp; n = inn; }
// Get and set methods for the data members
public Object element() { return e; } // Return the value
public Object setElement(Object it) { return e = it; } // Set element value
public Link next() { return n; } // Return next link
public Link setNext(Link nextval) { return n = nextval; } // Set next link
public Link prev() { return p; } // Return prev link
public Link setPrev(Link prevval) { return p = prevval; } // Set prev link
}
3.1.1. 插入¶
下面的幻灯片演示了双向链表的 insert 和 append 方法。
双向链表类的类声明和其余成员函数与单链表版本几乎完全相同。
尽管这些方法的代码可能比单链表的对应版本稍长
（因为每个结点都要多处理一个指针），
但它们通常更易于理解。
3.1.2. 追加¶
3.1.3. 删除¶
3.1.4. 前移¶
与单链表相比，双向链表唯一的缺点是占用了更多的空间。 双向链表每个结点需要两个指针， 因此在上述实现中，它的空间开销是单链表的两倍。
3.1.5. 指针的杂糅¶
有一种节省空间的技术可以消除这部分额外的空间需求，
但它会使实现复杂化，速度也稍慢。
因此，这是空间/时间折中的一个例子。
它基于这样一个观察：如果存储两个值之和，
那么用这个和减去其中一个值，就能得到另一个值。
也就是说，若把 \(a + b\) 存入变量 \(c\) ，
则 \(b = c - a\) ， \(a = c - b\) 。
当然，要从存储的和值中恢复出其中一个值，必须提供另一个值。
指向线性表第一个结点的指针，
连同它的两个链接字段之一的值，
便可以按顺序访问线性表中其余的全部结点。
这是因为指向某结点的指针，
必定与后继结点的 prev 指针的值相同，
也与前驱结点的 next 指针的值相同。
这样便可以沿着线性表前行，
逐个拆开相加后的链接字段，就像拉开一条拉链。
这一技术背后的原理值得牢记，因为它有许多应用。 下面的代码片段无需使用临时变量即可交换两个变量的内容 （代价是三次算术运算）。
a = a + b;
b = a - b; // Now b contains original value of a
a = a - b; // Now a contains original value of b
a = a + b;
b = a - b; // Now b contains original value of a
a = a - b; // Now a contains original value of b
使用异或运算符也能达到类似的效果。 这一事实在计算机图形学中应用广泛： 对屏幕某一区域周围的方框轮廓做异或运算即可高亮该区域； 再次对方框轮廓做异或运算即可恢复屏幕的原始内容。
