概览

同 ArrayList 一样,LinkedList 也是对 List 接口的一种具体实现。不同的是,ArrayList 是基于数组来实现的,而 LinkedList 是基于双向链表实现的。LinkedList 类的声明如下:

1
2
3
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 继承自 AbstractSequentialList,实现了 List 接口,同时还实现了 Deque 接口。AbstractSequentialList 是 AbstractList 的子类,为基于顺序访问的链表提供了一些基本的实现。LinkedList 实现了 Deque 接口,Deque 接口是一种双端队列,可以作为 FIFO 队列和 LIFO 队列(栈)来使用。LinkedList 支持所有元素,包括 null。

下面基于JDK 8 中的代码对LinkedList的实现加以分析。

底层结构

LinkedList 基于双向链表进行实现,并使用两个引用 first 和 last 分别指向双向链表的头尾元素。同 ArrayList 一样,使用 modCount 来记录结构化修改的次数,并依此实现 fail-fast 机制。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    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 和 next 指向该节点的前驱和后继结点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    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;
        }
    }

双向链表操作

LinkedList 提供的所有操作都是在双向链表的基础上完成的。Dqeue 接口的一些实现就是在 双向链表的两端进行操作,也是基于对头和尾部元素的操作。总的来说,双向链表的操作并不复杂,下面简单地进行解析,大部分操作都是对以下几种操作的封装。

向头部添加元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    //将一个元素加入双向链表的头部
    private void linkFirst(E e) {
        final Node<E> f = first;
        //新节点的前驱节点为null,后继节点为原来的头节点
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null) //原来的头节点为空
            //新加入的节点是第一个也是最后一个
            last = newNode;
        else
            //修改原来头节点的前驱指向
            f.prev = newNode;
        //调整链表大小
        size++;
        //修改计数器
        modCount++;
    }

向尾部添加元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

从中间插入元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    //在一个非空节点前插入元素
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev; //获取前驱
        //注意新建节点的前驱与后继
        final Node<E> newNode = new Node<>(pred, e, succ);
        //调整相关节点的前驱与后继关系
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        //修改大小
        size++;
        modCount++;
    }

移除头部节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    //将头节点从链表移除
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        //引用修改为null,方便GC
        f.item = null;
        f.next = null; // help GC
        //调整头节点
        first = next;
        if (next == null) //移除后链表为空
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

移除尾部节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

移除任意一个非空节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
    //移除一个非空节点
    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; //后继

        //注意对前驱为null的处理
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        //注意对后继为null的处理
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

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

清空链表

主要是为了方便垃圾回收器进行垃圾回收。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }

根据索引获取元素

因为是双向链表,可向前遍历,也可向后遍历。查找时双向进行,靠近头节点则从前向后查找;靠近尾部,则从后向前查找。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    //根据索引获取元素
    Node<E> node(int index) {
        // assert isElementIndex(index);
        //双向查找,根据index和size判断
        //前半段,从头节点向后查找
        //后半段,从尾节点向前查找
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

反查一个元素的索引

第一次出现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

最后一次出现,从后向前查找:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

迭代器

通过 next 的指向依次进行遍历。还提供了反向的迭代(从尾部到头部),通过 prev 的指向依次遍历。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        //创建迭代器时的modCount,检测并发修改,fail-fast
        private int expectedModCount = modCount;

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        public E previous() {
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();

            //如果next == null, 前一个为尾节点
            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }

        public int nextIndex() {
            return nextIndex;
        }

        public int previousIndex() {
            return nextIndex - 1;
        }

        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node<E> lastNext = lastReturned.next;
            //调用unlink方法移除元素
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            //修改modCount
            expectedModCount++;
        }

        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (modCount == expectedModCount && nextIndex < size) {
                action.accept(next.item);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
            checkForComodification();
        }
        //检查并发修改,fail-fast
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

小结

LinkedList 是 List 接口基于双向链表的一种实现,同时还实现了 Deque 接口,可以作为 FIFO 和 LIFO 队列使用。双向链表的实现使得插入和删除操作的代价降低,可以在常数时间内完成;然而查找操作需要遍历列表,尽管双向列表使得可以从两端进行查找,但在长度较长时仍然需要较长的时间。

在大多数情况下会选择使用 ArrayList,尽管插入和删除代价相较于 LinkedList 更高,但随机访问的特性使得在查找方面 ArrayList 比 LinkedList 具有更多的优势。关于 ArrayList 和 LinkedList 的使用选择上可以参考 StackOverflow 上的这个问答