链表是基本的数据结构，尤其双向链表在应用中最为常见，LinkedList 就实现了双向链表。今天我们一起手写一个双向链表。
文中涉及的代码可访问 GitHub:https://github.com/UniqueDong/algorithms.git
上次我们说了「单向链表」的代码实现，今天带大家一起玩下双向链表，双向链表的节点比单项多了一个指针引用 「prev」。双向链表就像渣男，跟「前女友」和「现女友」，还有一个「备胎』都保持联系。前女友就像是前驱节点，现女友就是 「当前 data」，而「next」指针就像是他套住的备胎。每个 Node 节点有三个属性，类比就是 「前女友」+ 「现女友」 + 「备胎」。
使用这样的数据结构就能实现「进可攻退可守」灵活状态。
接下来让我们一起实现『渣男双向链表』。
定义Node节点分别保存现女友、前女友、跟备胎的联系方式，这样就能够实现一三五轮换运动（往前看有前女友，往后看有备胎），通过不同指针变可以找到前女友跟备胎。就像渣男拥有她们的联系方式。
private static class Node<E> { //现女友 E item; // 备胎 Node<E> next; // 前女友 Node<E> prev; public Node(Node<E> prev, E item, Node<E> next) { this.prev = prev; this.item = item; this.next = next; } } 代码实现定义好渣男节点后，就开始实现我们的双向链表。类似过来就是一个渣男联盟排成一列。我们还需要定义两个指针分别指向头结点和尾节点。一个带头大哥，一个收尾小弟。
public class DoubleLinkedList<E> extends AbstractList<E> implements Queue<E> { transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last; } 头节点添加新的渣男进群了，把他设置成群主带头大哥。首先构建新节点，prev = null，带头大哥业务繁忙，不找前女友，所以 prev = null；next 则指向原先的 first。
如果链表是空的，则还要把尾节点也指向新创建的节点。
若果链表已近有数据，则把原先 first.prev = newNode。
@Override public void addFirst(E e) { linkFirst(e); } /** * 头结点添加数据 * * @param e 数据 */ private void linkFirst(E e) { final Node<E> f = this.first; Node<E> newNode = new Node<>(null, e, f); // first 指向新节点 first = newNode; if (Objects.isNull(f)) { // 链表是空的 last = newNode; } else { // 将原 first.prev = newNode f.prev = newNode; } size++; } 尾节点添加将新进来的成员放在尾巴。
第一步构建新节点，把 last 指向新节点。
第二步判断 last 节点是否是空，为空则说明当前链表是空，还要把 first 指向新节点。否则就需要把原 last.next 的指针指向新节点。
@Override public boolean add(E e) { addLast(e); return true; } private void addLast(E e) { final Node<E> l = this.last; Node<E> newNode = new Node<>(l, e, null); last = newNode; if (Objects.isNull(l)) { // 链表为空的情况下，设置 first 指向新节点 first = newNode; } else { // 原 last 节点的 next 指向新节点 l.next = newNode; } size++; } 指定位置添加分为两种情况，一个是在最后的节点新加一个。一种是在指定节点的前面插入新节点。
在后面添加前面尾巴添加已经说过，对于在指定节点的前面插入需要我们先找到指定位置节点，然后改变他们的 prev next 指向。
@Override public void add(int index, E element) { checkPositionIndex(index); if (index == size) { linkLast(element); } else { linkBefore(element, node(index)); } } /** * Links e as last element. */ void linkLast(E element) { addLast(element); } /** * Inserts element e before non-null Node succ. */ private void linkBefore(E element, Node<E> succ) { // assert succ != null final Node<E> prev = succ.prev; // 构造新节点 final Node<E> newNode = new Node<>(prev, element, succ); succ.prev = newNode; if (Objects.isNull(prev)) { first = newNode; } else { prev.next = newNode; } size++; } 节点查找为了优化，根据 index 查找的时候先判断 index 落在前半部分还是后半部分。前半部分通过 first 开始查找，否则通过 last 指针从后往前遍历。
@Override public E get(int index) { checkElementIndex(index); return node(index).item; } /** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // 优化查找，判断 index 在前半部分还是后半部分。 if (index < (this.size >> 2)) { // 前半部分，从头结点开始查找 Node<E> x = this.first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { // 后半部分，从尾节点开始查找 Node<E> x = this.last; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; } }