[译]数据结构_双向链表

双向链表和顺序链表99%都是相同的。主要的区别是：每个节点包含两个指针，next指针指向后一个元素（若存在）即a_j指向a_j+1，另一个prev指针指向前一个元素，即a_j指向a_j-1（若存在）。

prev指针是的双向链表能够反向遍历，但同时也增加了内存的消耗。它解决了顺序链表中移除尾元素的低效问题。

注意：在本教学中，双向链表（以及之后的双端队列）的边界是无方向的。

Remove(i) - At Tail(i = N-1) 复习

顺序链表最大的问题是尾元素的移除，即时我们有指向尾元素的指针，因为我们需要将tail指针指向尾元素的前一个。

有了双向链表的反向能力，我可以直接找到前一个元素：

Vertex* temp = tail; // remember tail item
tail = tail->prev; // the key step to achieve O(1) performance :O
tail->next = null; // remove this dangling reference
delete temp; // remove the old tail

example DLL [22 (head)<->2<->77<->6<->43<->76<->89 (tail)]

练习

1. insertHead(50) -
2. insertTail(10)
3. insert(3,4)
4. removeHead()
5. remove(5)