鏈表是常用的數(shù)據(jù)結(jié)構(gòu)，在Java中有很多基于鏈表的容器實現(xiàn)類，例如HashMap、LinkedList。但是這些鏈表有的是單向鏈表，有的是雙向鏈表，那么他倆有什么不同呢？(以下源碼均屬于jdk1.8.0_101)

單向鏈表只有后一節(jié)點指針，在節(jié)點刪除，移動的時候，需要暫存前一節(jié)點，刪除的時候?qū)⑶耙还?jié)點和后一節(jié)點連接，因為比雙向鏈表少維護(hù)一個前節(jié)點，只在刪除的時候暫存，所以比雙向鏈表節(jié)省資源，但是增加了操作的復(fù)雜性。
雙向鏈表有前后兩個節(jié)點指針，可以回溯指針，方便節(jié)點刪除，移動，在做刪除操作時只需要將索引節(jié)點前后兩個節(jié)點連接即可，但是相比單向鏈表會耗費(fèi)額外資源。

• 單向鏈表

  
  
  image.png

• 雙向鏈表

  
  
  image.png

源碼分析

1. HashMap - 單向鏈表

暫存前一節(jié)點，前后節(jié)點連接

• Node

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    ...
}

• removeNode

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e; // 暫存前一節(jié)點
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next; // 前一節(jié)點和后一節(jié)點連接
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

2. LinkedList - 雙向鏈表

直接連接前后節(jié)點

• Node

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

• unlink

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next; // 前節(jié)點連接后節(jié)點
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev; // 后節(jié)點連接前節(jié)點
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}