close

Mr.Muzi

一只很安静的monkey

Java Collection 07 - LinkedList

字数统计: 8.7k 阅读时长: 37 mins • 分类: 源码阅读 • 标签: JDK 1.7, Java集合

  关于 java.util.LinkedList<E> 的部分笔记，LinkedList是一个非线程安全的List集合实现类。因为其采用了双向链表作为底层存储数据结构而具有了可以以常量时间插入数据的性能，但是因为底层数据结构的限制导致其只能顺序访问元素。鉴于此，LinkedList适用于元素插入频繁，而元素遍历查找相对次要的场景中。本文演示代码段的执行环境基于JDK版本1.7。

概述

  LinkedList是一个以双向链表为基础的List集合，其综合了List集合和Deque队列的优势和特点实现了一个顺序访问的集合实现类。因为LinkedList的底层依赖了链表数据结构，所以在元素访问时都是按照链表的方式从首元素依次遍历直至到达目标元素。此外，鉴于其依赖的链表实现，所以在元素插入时可以达到常量时间的操作性能。

  需要注意的是，LinkedList是一个非线程安全的集合实现。如果需要在多线程环境中使用LinkedList完成需求，那么需要添加另外处理来保证多线程环境下的线程安全，一种可以实现要求的常用处理方式是使用Collections.synchronizedList(new LinkedList(…))来在LinkedList初始化时保证LinkedList的线程安全。示例如下：

1
List list = Collections.synchronizedList(new LinkedList(...));

  LinkedList返回的迭代器支持快速失败（fail-fast）检查。如果当前迭代器发现LinkedList集合最近一次做了不是由当前迭代器执行的结构化修改，那么就返回一个ConcurrentModificationException异常。

  LinkedList中通过两个Node节点：first和last来维护存储在LinkedList的元素内容。其中first节点指向集合中的第一个元素，last节点指向集合中的最后一个元素。在访问集合中元素时都是通过first或者last节点开始，逐个遍历直到到达目标位置。结构示例如图1所示：

图 - 1
 

  这里的first和last节点中也会存储元素。

 

继承关系

1
2
3
4
5
6
// LinkedList<E>
--java.lang.Object
  --java.util.AbstractCollection<E>
    --java.util.AbstractList<E>
      --java.util.AbstractSequentialList<E>
        --java.util.LinkedList<E>

 

实现接口

类名 实现接口
LinkedList<E> Iterable<E>, Collection<E>, List<E>, Queue<E>, Serializable, Cloneable

 

LinkedList

Constructor Summary

public LinkedList()

1
2
public LinkedList() {
}

  初始化一个LinkedList空集合实例。

public LinkedList(Collection<? extends E> c)

1
2
3
4
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

  根据集合c初始化一个LinkedList空集合实例，并将c中的内容复制到实例化后的集合实例中。初始化的实例集合中元素的位置和c一致。元素的加入通过addAll(Collection<? extends E> c)完成。

部分方法

private void linkFirst(E e)

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

  在链表首部加入元素e。LinkedList底层双向链表操作方法API之一。操作过程如图2所示：

图 - 2
 

  第2 ~ 3行代码根据元素e和当前LinkedList集合的首部元素创建一个Node节点，即alpha阶段。alpha的（1）过程表明在元素初始化过程中将新节点newNode的后继指向当前LinkedList集合的首部元素节点。第4行代码将当前LinkedList集合的首部元素节点指向新创建的newNode节点，使新的newNode节点成为新的首部元素。如果当前LinkedList集合是个空集合，则将last节点也指向到newNode，最终到达bravo_2阶段。此时整个集合中只包含一个元素，即newNode。如果当前LinkedList集合不为空，那么将被newNode之后的节点的前驱指向新创建的newNode节点，即bravo_1阶段的步骤（2）。

void linkLast(E e)

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++;
}

  在链表尾部加入元素e。LinkedList底层双向链表操作方法API之一。操作过程如图3所示：

图 - 3
 

  第2 ~ 3行代码根据元素e和当前LinkedList集合的尾部元素创建一个Node节点，即alpha阶段。alpha的（1）过程表明在元素初始化过程中将新节点newNode的前驱指向当前LinkedList集合的尾部元素节点。第4行代码将当前LinkedList集合的last节点指向新创建的newNode节点，使新的newNode节点成为新的尾部元素。如果当前LinkedList集合是个空集合，则将first节点也指向到newNode，最终到达bravo_2阶段。此时整个集合中只包含一个元素，即newNode。如果当前LinkedList集合不为空，那么将被newNode之前的节点的后继指向新创建的newNode节点，即bravo_1阶段的步骤（2）。

void linkBefore(E e, Node<E> succ)

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

  在元素succ之前插入一个元素e。LinkedList底层双向链表操作方法API之一。操作过程如图4所示：

图 - 4
 

  在这个操作中，参数succ即为元素e的后继节点。第3 ~ 4行代码根据元素e和前驱节点succ创建一个Node节点，即alpha阶段。此时newNode的后继是succ，newNode的前驱为succ的前驱（有可能为null，若为null则表示succ为当前LinkedList集合的首部元素）。第5行代码将当前succ节点的前驱指向newNode节点，即bravo阶段的过程（1）。如果succ是当前LinkedList集合的第一个元素，那么完成newNode和succ的相互指定后newNode会成为LinkedList集合的首部元素（第6 ~ 7行代码的执行情况），反之，则将succ的前驱节点的后继更新为newNode节点，即bravo阶段的过程（2）。

private E unlinkFirst(Node<E> f)

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

  移除LinkedList集合中的首部元素f。LinkedList底层双向链表操作方法API之一。操作过程如图5所示：

图 - 5
 

  第3 ~ 4行代码获取首部元素的内容及其后继节点的相关信息。第6行代码将首部元素指向其后继的指针断开，即alpha阶段的步骤（1）。第7行代码则将first指向当前首部元素f的后继节点上，即bravo阶段。如果f节点的后继为空，且该方法删除是的首部节点，那么认为该节点会是当前LinkedList集合的唯一一个节点，所以last节点被置为null。反之，则将f的后继节点的前驱指针置为空，这样该后续节点将会成为真正的首部元素，即charlie阶段的过程（2）。最后，脱离LinkedList集合的首部元素element会被返回给方法调用方。

private E unlinkLast(Node<E> l)

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;
}

  移除LinkedList集合中的尾部元素l。LinkedList底层双向链表操作方法API之一。操作过程如图6所示：

图 - 6
 

  第3 ~ 4行代码获取尾部元素的内容及其前驱节点的相关信息。第6行代码将尾部元素指向其前驱的指针断开，即alpha阶段的步骤（1）。第7行代码则将last指向当前尾部元素l的前驱节点上，即bravo阶段。如果l节点的前驱为空，且该方法删除是的尾部节点，那么认为该节点会是当前LinkedList集合的唯一一个节点，所以first节点被置为null。反之，则将l的前驱节点的后继指针置为空，这样该前驱节点将会成为真正的尾部元素，即charlie阶段的过程（2）。最后，脱离LinkedList集合的尾部元素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
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;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

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

  移除LinkedList集合中的元素x。LinkedList底层双向链表操作方法API之一。操作过程如图7所示：

图 - 7
 

  第3 ~ 5行代码获取x元素的内容及其前驱、后继节点的相关信息。第7 ~ 8行代码中，如果x的前驱节点为null，那么x会是当前LinkedList集合的首部元素，那么就将first节点指向x的后继节点（PS：按照移除首部元素的方式处理）。否则，就将x的前驱节点的后继指针指向x的后继节点，即alpha阶段的步骤（1）。同时将x的前驱指针指向null以断开x和x的前驱节点的前驱关系，即alpha阶段的步骤（2）。如果x的后继节点为null，那么认为x元素为当前linkedList集合的尾部元素，那么就将last指向x的前驱节点（PS：按照移除尾部元素的方式处理）。否则，就将x的后继元素的前驱指针指向x的前驱节点，即alpha阶段的步骤（3）。同时将x的后继指针指向null以断开x和x的后继节点的后继关系，即alpha阶段的步骤（4）。最后，脱离LinkedList集合的尾部元素element会被返回给方法调用方，而linkedList集合的状态为bravo阶段所处的状态。

public E getFirst()

1
2
3
4
5
6
7
8
9
10
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

public E element() {
    return getFirst();
}

  得到当前LinkedList集合的首部元素。如果首部元素为null，那么抛出一个NoSuchElementException异常。public E element()方法完全调用getFirst()方法。

public E peek()

1
2
3
4
5
6
7
8
9
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

  得到当前LinkedList集合的首部元素。如果首部元素为null，那么直接返回null（此时集合为空）。方法public E peekFirst()和peek()方法方法体完全相同，只是声明不同。

public E getLast()

1
2
3
4
5
6
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

  得到当前LinkedList集合的尾部元素。如果尾部元素为null，则抛出NoSuchElementException异常。

public E peekLast()

1
2
3
4
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

  返回当前LinkedList集合的尾部元素。如果尾部元素为null，那么直接返回null（此时集合为空）。

public E get(int index)

1
2
3
4
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

  返回当前LinkedList集合中index位置的元素。底层调用node(int index)完成操作。

private void checkElementIndex(int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size;
}

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

  index下标检查。如果index不符合要求，抛出IndexOutOfBoundsException异常。

private boolean isElementIndex(int index)

1
2
3
4
5
6
7
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

  index下标检查，避免发生越界溢出的情况。

Node<E> node(int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node<E> node(int index) {
    // assert isElementIndex(index);

    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;
    }
}

  采用顺序访问的方式从首/尾元素逐个访问直到到达index下标位置处，并返回index位置的元素。在访问过程中借鉴了二分查找的思想，通过比较index和$\frac{1}{2}$size 的大小关系决定是从首部进行遍历还是从尾部进行遍历（size为当前LinkedList集合中存储的元素数）来提高效率。

public E set(int index, E element)

1
2
3
4
5
6
7
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

  用element替换当前LinkedList集合中index位置处的内容。首先检查index的合法性，检查通过后通过node(int index)方法得到index位置的原有内容，同时用element替换原有内容。最后返回被替换的原有内容。

public E removeFirst()

1
2
3
4
5
6
7
8
9
10
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

public E remove() {
    return removeFirst();
}

  移除当前LinkedList集合的首部元素。实际调用unlinkFirst(Node<E> f)方法完成操作。如果首部元素为null，那么抛出NoSuchElementException异常。public E remove()方法通过 removeFirst()方法完成首部元素删除。

public E pop()

1
2
3
public E pop() {
    return removeFirst();
}

  完全调用removeFirst()方法移除首部元素，除此之外无任何处理。该方法在使用LinkedList作为栈存储的场景中使用。

public E poll()

1
2
3
4
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

  移除当前LinkedList集合的首部元素。实际调用unlinkFirst(Node<E> f)方法完成操作。如果首部元素为null，那么直接返回null（此时集合为空）。

public E pollFirst()

1
2
3
4
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

  移除当前LinkedList集合的首部元素。实际调用unlinkFirst(Node<E> f)方法完成操作。如果首部元素为null，那么直接返回null（此时集合为空）。

public E pollLast()

1
2
3
4
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

  移除当前LinkedList集合的尾部元素。实际调用unlinkLast(Node<E> l)方法完成操作。如果首部元素为null，那么直接返回null（此时集合为空）。

public E removeLast()

1
2
3
4
5
6
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

  移除当前LinkedList集合的尾部元素。实际调用unlinkLast(Node<E> f)方法完成操作。如果尾部元素为null，那么抛出NoSuchElementException异常。

public boolean remove(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}

  移除当前LinkedList集合中存储的第一个对象o。在执行过程中从首部元素开始遍历，如果在遍历过程中第一次遇到了对象o，那么就将其从集合中移除，并返回true。如果当前集合中未曾存储对象o，那么返回false表示当前集合未被修改。public boolean removeFirstOccurrence(Object o)方法直接调用remove(Object o)完成元素删除操作。

public E remove(int index)

1
2
3
4
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

  删除LinkedList集合中index位置处的元素。先通过node(int index)方法得到index位置处的元素，然后再通过E unlink(Node<E> x)删除元素。

public boolean removeLastOccurrence(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean removeLastOccurrence(Object o) {
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

  移除当前LinkedList集合中存储的最后一个对象o。在执行过程中从尾部元素开始遍历，如果在遍历过程中第一次遇到了对象o，那么就将其从集合中移除，并返回true。如果当前集合中未曾存储对象o，那么返回false表示当前集合未被修改。

public void addFirst(E e)

1
2
3
public void addFirst(E e) {
    linkFirst(e);
}

  将元素e加入到当前LinkedList集合首部位置。实际调用linkFirst(E e)方法完成操作。

public boolean offerFirst(E e)

1
2
3
4
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

  将元素e加入到当前LinkedList集合中的首部位置。底层直接调用addFirst(E e)方法完成操作。该方法适用于利用LinkedList作为双端队列（Deque operations）的场景中，通过该方法向队列首部输入元素。

public boolean offer(E e)

1
2
3
public boolean offer(E e) {
    return add(e);
}

  将元素e加入到当前LinkedList集合中的尾部位置。底层直接调用add(E e)方法完成操作。该方法适用于利用LinkedList作为双端队列（Deque operations）的场景中，通过该方法向队列尾部输入元素。

public boolean offerLast(E e)

1
2
3
4
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

  将元素e加入到当前LinkedList集合的尾部位置上。底层直接调用addLast(E e)方法完成操作。该方法适用于利用LinkedList作为双端队列（Deque operations）的场景中，通过该方法向队列尾部输入元素。

public void push(E e)

1
2
3
public void push(E e) {
    addFirst(e);
}

  将元素e加入到当前LinkedList集合中的首部位置。底层直接调用addFirst(E e)方法完成操作。该方法适用于利用LinkedList作为栈存储的场景中，通过该方法想栈顶部输入元素。

public void addLast(E e)

public void addLast(E e) {
    linkLast(e);
}

  将元素e加入到当前LinkedList集合的尾部位置上。实际调用linkLast(E e)方法完成操作。

public boolean add(E e)

1
2
3
4
public boolean add(E e) {
    linkLast(e);
    return true;
}

  将元素e加入到当前LinkedList集合的尾部位置上。实际调用linkLast(E e)方法完成操作。

public boolean addAll(Collection<? extends E> c)

1
2
3
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

  将集合c中的元素全部加入到当前LinkedList集合的尾部位置上。实际调用addAll(int index, Collection<? extends E> c)方法完成操作。

public boolean addAll(int index, Collection<? extends E> c)

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
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

  将集合c中的元素加入到LinkedList集合中自index指定的位置起。如果c集合中没有存储任何元素，那么不做处理直接返回false。第9 ~ 16行代码计算index位置处的节点及其前驱节点，如果index指向了集合尾部（index = size），那么操作会在集合尾部执行，这种情况下只会确定前驱节点而认为后继节点为null，否则将前驱节点和后继节点都计算确认完成。

  在通过计算得到index位置处的前驱节点和后继节点信息后，以计算好的前驱节点为基础，依次将c集合中的元素加入当前LinkedList集合中（第18 ~ 26行代码的操作过程）。在c中所有元素全部加入到当前LinkedList集合后，建立与前面计算得到的后继节点的指向关系 — c集合中最后一个元素的后继节点是根据index计算得到的后继节点，同时计算得到的后继节点的前驱节点是c集合中的最后一个元素。最后更新当前LinkedList集合中存储的元素总数并返回true表示确实执行过元素添加操作。

public void add(int index, E element)

1
2
3
4
5
6
7
8
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

  将元素element加入到当前LinkedList集合中index指定的位置上。先对index做边界检查，检查通过的话根据index指定的位置决定采用linkLast(E e)或者linkBefore(E e, Node<E> succ)方法完成元素插入。

public boolean contains(Object o)

1
2
3
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

  判断当前LinkedList集合中是否存储了元素o。如果未存储元素o，则返回false，否则返回true。

public int indexOf(Object o)

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;
}

  返回元素o在当前LinkedList集合中第一次被存储的位置。从集合首部元素开始遍历，如果元素o为null，那么返回null在集合中第一次被存储的位置下标，反之则返回非null元素o在集合中第一次被存储的位置。如果集合中不存在元素o，那么返回-1。

public int lastIndexOf(Object o)

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;
}

  返回元素o在当前LinkedList集合中最后一次被存储的位置。从集合尾部元素开始遍历，如果元素o为null，那么返回null在集合中最后一次被存储的位置下标，反之则返回非null元素o在集合中最后一次被存储的位置。如果集合中不存在元素o，那么返回-1。

public int size()

1
2
3
public int size() {
    return size;
}

  返回当前LinkedList集合中存储的元素数。

public void clear()

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++;
}

  清空当前LinkedList集合中的所有元素。

public ListIterator<E> listIterator(int index)

1
2
3
4
public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

  返回一个基于当前LinkedList集合从index位置开始遍历元素的迭代器。

public Object clone()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public Object clone() {
    LinkedList<E> clone = superClone();

    // Put clone into "virgin" state
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;

    // Initialize clone with our elements
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);

    return clone;
}

@SuppressWarnings("unchecked")
private LinkedList<E> superClone() {
    try {
        return (LinkedList<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError();
    }
}

  返回一个LinkedList集合的浅度复制对象。该方法只复制LinkedList对象自身，对于其内部存储的元素内容并不会参与复制过程，所以通过复制操作得到的副本集合中存储的元素内容是通过遍历添加得到的（第10 ~ 11行代码的操作过程）。

public Iterator<E> descendingIterator()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public Iterator<E> descendingIterator() {
    return new DescendingIterator();
}

private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

  返回一个基于整个LinkedList集合的逆序迭代器。该迭代器的执行方向是单向的，执行顺序是从尾部向首部进行遍历。该实现类实现了Iterator<E>接口的三个方法，而实际调用的是ListItr实现类的获取前驱元素的方法来完成逆向集合遍历。

public Object[] toArray()

1
2
3
4
5
6
7
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

  将当前LinkedList集合中存储的所有元素存入一个Object[] 数组中并返回。

public <T> T[] toArray(T[] a)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        a = (T[])java.lang.reflect.Array.newInstance(
        a.getClass().getComponentType(), size);
    int i = 0;
    Object[] result = a;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;

    if (a.length > size)
        a[size] = null;

    return a;
}

  将当前LinkedList集合中存储的所有元素存储到数组a中并返回a。如果数组的长度不足以容纳集合中的所有元素，那么会以a的类型重新分配一个数组空间来容纳集合中所有元素。之后将集合中的所有元素按照从首部到尾部的顺序依次存储到数组中。在执行完存储操作后数组中仍有空余空间，那么就将数组中存储元素的下一个空间位置置为null，这么做有利于快速地知道集合中存储的元素个数（在集合中没有存储null元素的情况下）。

private void writeObject(java.io.ObjectOutputStream s)

1
2
3
4
5
6
7
8
9
10
11
12
private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();

    // Write out size
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

  LinkedList集合的自定义序列化方法。在实际序列化操作过程中会调用LinkedList自己的序列化方法来完成序列化操作。

private void readObject(java.io.ObjectInputStream s)

1
2
3
4
5
6
7
8
9
10
11
12
13
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();

    // Read in size
    int size = s.readInt();

    // Read in all elements in the proper order.
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}

  LinkedList集合的自定义反序列化方法。在反序列化过程中会按照LinkedList自己的反序列化过程来完成反序列化操作。

 

Node<E>

  在LinkedList中，底层元素存储结构是一个Node节点，每个节点有一个前驱节点指向当前节点的前一个节点，有一个后继节点指向当前节点的下一个节点。除此之外，还有一个字段来维护当前节点存储的内容。具体内容代码如下：

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;
    }
}

 

private class ListItr implements ListIterator<E>

  LinkedList集合自定义的迭代器实现类，相关实现代码如下：

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
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned = null;
    private Node<E> next;
    private int nextIndex;
    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();

        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(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        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++;
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

  ListItr的构造函数会传入一个index参数。根据index会找到该index位置处的元素节点，该元素节点是迭代器遍历的起点。同时初始化nextIndex的值，该字段标记了迭代执行到了什么位置。

  根据nextIndex和size的大小关系来判断当前迭代是否已经到了集合尾部位置。根据nextIndex和0的大小关系判断当前迭代是否已经到了集合首部位置。

  如果想遍历得到当前节点的下一个节点，可以调用方法next()。当前next指针指示的即是需要返回的节点，取得当前next指针指向的内容，同时将next指针指向next的后继节点来完成next向后遍历一个节点的操作。最后更新nextIndex的值并返回取得的元素内容。

  如果想得到当前节点的前驱节点，可以调用方法previous()。在完成快速失败和边界检查以后获取到当前next节点的前驱节点。如果当前next节点为null，那么说明当前next的前驱节点是集合的last节点，所以直接返回last节点上的内容。

  如果想在某次调用next()或者previous()方法之后删除某个节点，可以调用remove()方法。在删除之前得到当前节点的后继节点，之后从当前LinkedList集合中删除当前节点。如果迭代器执行的previous()方法遍历，那么将当前被移除节点的后继节点的前驱指针指向当前next节点。如图8所示：

图 - 8
 

  alpha阶段是迭代器初始化完成后的状态，此时只有next指针和nextIndex下标指示器。bravo阶段是迭代器完成了一次previous()方法操作之后的结果。此时lastReturn和next指向了同一个元素，nextIndex指示的下标就是next元素的下标位置。执行remove()操作时，删除lastReturn节点的元素，同时将next指针指向lastReturn元素的后继节点。即charlie阶段。此时next节点指示的元素的下标位置等同于被删除节点的下标位置，而next和nextIndex指向的会是同一个元素节点。

  反之，迭代器执行的是next()方法遍历，则将nextIndex的值减一，表示迭代位置由于元素移除而向前偏移了一个位置。如图9所示：

图 - 9
 

  alpha阶段是迭代器初始化完成后的状态，此时只有next指针和nextIndex下标指示器。bravo阶段是迭代器完成了一次next()方法操作之后的结果。此时lastReturn和next指向了不同元素，nextIndex指示的下标就是next元素的下标位置。执行remove()操作时，删除lastReturn节点的元素，同时将nextIndex的值减1。即charlie阶段。此时next节点指示的元素未发生变化，只是该节点元素的逻辑位置下标前移了一位，为了保证next和nextIndex指示的是同一个元素，所以需要对nextIndex做减一操作。

  相关移除操作完成后，最后将lastReturned置为null，保证不会连续执行remove操作，并更新expectedModCount。

  如果想在某次调用next()或者previous()方法之后更新某个节点的内容，可以调用set(E e)方法。该方法直接将当前节点的值进行替换。

  如果想在某次调用next()或者previous()方法之后加入一个元素e，可以调用add(E e)方法。如果当前next已经到达了集合尾部位置，那么就按照将元素加入集合尾部的思路进行处理，否则按照将元素加入到next元素之前的思路进行处理。最后最后更新nextIndex和expectedModCount的值。

 

涉及基础知识点

  1. 为什么说fail-fast无法得到保证

      “快速失败”也就是fail-fast，它是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，就有可能会产生fail-fast机制。如果两个及以上线程对同一个集合的元素做了结构化修改，就有可能触发快速失败校验并抛出ConcurrentModificationException异常。在多/单线程环境里，Iterator是工作在一个独立的线程中，并且拥有一个 mutex 锁。Iterator被创建之后会建立一个指向原来对象的单链索引表，当原来的对象经历过结构化修改时，这个索引表的内容不会同步改变，所以当索引指针往后移动的时候就找不到要迭代的对象，所以会马上抛出ConcurrentModificationException 异常。

      如果在单线程环境下，集合在被遍历的过程中没有通过迭代器提供的API对集合做结构化修改，那么就会抛出ConcurrentModificationException 异常。如果是在多线程环境下，当一个线程在遍历这个集合的同时，另一个线程修改了这个集合的结构。这种情况下也会抛出ConcurrentModificationException 异常。

      但是该异常不是任何情况下都会触发的。因为modCount在多线程环境中由于没有synchronized或者volatile修饰，所以可能会存在多线程下某个线程作出的结构化修改导致另外一个线程无法及时得到更新后的modCount内容，从而导致不会检测到并抛出ConcurrentModificationException 异常。

      如果需要解决该问题，那么可以考虑使用java.util.concurrent.CopyOnWriteArrayList<E>，这个实现是ArrayList的一个线程安全版本。CopyOnWriteArrayList是一个实现了List接口，底层依赖数组作为存储结构的线程安全实现，其从数据结构、定义等方面都和ArrayList完全一致，其中所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现。但是CopyOnWriteArrayList也有缺陷，那就是由于每次修改容器都会复制底层数组，需要很大的开销，特别是容器规模很大的时候。所以，只有当迭代操作远远多于修改操作的时候，才使用这个容器。

 

参考文献

  1. 楚云之南. 解析Java的迭代器中的fast-fail错误检测机制 [E]
  2. h2pl. Java集合详解3：Iterator，fail-fast机制与比较器 [E]
  3. Hollis. Java中的fail-fast机制 [E]
  4. chenssy. Java提高篇（三四）——-fail-fast机制 [E]
  5. 清浅池塘. LinkedList初探 [E]

 
 
 
 

------------- End of this article, thanks! -------------
 


  版权声明：本文由N.C.Lee创作和发表，采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可，转载请注明作者及出处。
  本文作者为 N.C.Lee
  本文标题为 Java Collection 07 - LinkedList
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-LinkedList.html