【Java源码解读】LinkedList

源码来源：OpenJDK 10

 

简述

LinkedList实现了List和Deque（双端队列）接口，它是一个双向链表。

当需要访问特定索引处的元素时，会选取离目标位置更近的一端开始遍历（从头部或尾部开始）。

 

关于线程安全/同步

• 与ArrayList类似，LinkedList线程不安全。如果在多线程场景下使用，且至少有一个线程会改变list的结构，就要像对待ArrayList（TODO：hyper link）那样做好相关同步处理。
• 通过iterator方法和listIterator方法获得的迭代器都是fail-fast机制的。但该机制也是可用于辅助排障，而不能作为正常业务的依赖。这点也和ArrayList相同。

 

构造方法

LinkedList()

创建一个空的LinkedList

 

LinkedList(Collection<? extends E> c)

创建一个LinkedList，并将指定集合中的元素放入其中

该方法会通过addAll(Collection<? extends E> c)方法，将c中的元素放入list

 

其它方法

getFirst()

获取第一个元素。如果list为空，抛异常NoSuchElementException

 

getLast()

获取最后一个元素。如果list为空，抛异常NoSuchElementException

 

removeFirst()

移除第一个元素，并返回该元素

modCount加1，size减1。如果list为空，抛异常NoSuchElementException

可体会一下final局部变量的用法与引用置null方便GC的做法

/**
 * Removes and returns the first element from this list.
 *
 * @return the first element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/**
 * Unlinks non-null first node f.
 */
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;
}

 

removeLast()

 移除最后一个元素，并返回该元素

modCount加1，size减1。如果list为空，抛异常NoSuchElementException

 

addFirst(E e)

将指定元素添加到头部

modCount加1，size加1

 

addLast(E e)

将指定元素添加到末尾

modCount加1，size加1

该方法与add(E e)效果等价。但add会返回true，addLast返回类型是void

 

contains(Object o)

判断list中是否存在指定的元素

具体实现就是判断indexOf(Object o)的返回值是否大于等于0

 

size()

返回list中元素个数

 

add(E e)

将指定元素添加到末尾，并返回true

modCount加1，size加1

该方法与addLast(E e)效果等价。但add会返回true，addLast返回类型是void

 

remove(Object o)

移除list中第一个与指定对象o相等的元素，并返回true（成功移除）或false（未找到相等的元素）。

与ArrayList中的做法类似，如果o为null，则用‘==null’判断是否相等，否则用o.equals

如果成功移除，modCount加1，size减1

 

addAll(Collection<? extends E> c)

将指定集合中的元素放入list，并返回true（有新元素加入）或false（没有新元素加入）

该方法内部会调用addAll(int index, Collection<? extends E> c)，其中index的值是size（当前list中元素个数）

 

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

将指定集合中的元素放入list的指定索引处，并返回true（有新元素加入）或false（没有新元素加入）

如果有新元素加入，modCount加1，size增加值就是新元素个数

该方法会先检查index是否有效，即index>=0 && index<=size

与ArrayList类似，会先将c中元素（引用）复制一个新数组中，再将这些元素加入list。如果没有新元素，会直接返回false

在添加新元素前，需要先确定前一个节点和后继节点。如果index==size，前一个节点就是当前list的最后一个节点，后一个节点就是null；否则将调用方法node(int index)找到当前目标索引处的元素，从而确定新元素的目标连接点。node(int index)的做法就是上述提到的，目标索引离头部近就从头开始遍历，离尾部近就从尾部开始遍历

 

/**
 * Returns the (non-null) Node at the specified element index.
 */
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;
    }
}

 

 

clear()

移除list中所有元素

具体实现就是从头开始将每个节点的值、前引用和后节点引用（三个字段）都设置为null，最后将list的first和last字段置为null，size为0，modCount加1

 

get(int index)

获取指定索引处的元素

该方法会先检查index是否有效

具体实现就是调用方法node(int index)获取目标索引处的节点，再返回其中的元素

 

set(int index, E element)

将目标索引处的元素设置为指定的元素，并返回原来的元素

该方法会先检查index是否有效

具体做法就是调用方法node(int index)获取目标索引处的节点，再将其元素替换为新元素

 

add(int index, E element)

在指定索引处插入指定的元素

该方法会先检查index是否有效

如果index==size，则直接将新元素添加到list末尾

否则，先调用node(int index)找到目标索引处的节点，再将新元素添加到该节点前

modCount加1，size加1

 

remove(int index)

移除指定索引处的元素

该方法会先检查索引是否有效

具体实现是，先调用node(int index)找到目标节点，再将该节点移除，然后置空节点中元素的引用，最后size减1，modCount加1

 

indexOf(Object o)

返回指定元素在list中首次出现的索引。如果不存在目标元素，则返回-1

具体做法与ArrayList类似

 

lastIndexOf(Object o)

返回指定元素在list中最后一次出现的索引。如果不存在目标元素，则返回-1

具体实现与indexOf(Object o)类似。不同之处是遍历的方向相反

 

peek()

返回首个元素，但不删除该元素

如果list为空，则返回null

 

element()

返回首个元素，但不删除该元素

具体实现就是调用getFirst()方法。所以如果list为空，会抛异常NoSuchElementException

 

poll()

返回首个元素，并移除该元素

如果list为空，则返回null；否则元素被移除，modCount加1，size减1

 

remove()

返回首个元素，并移除该元素

具体实现就是调用removeFirst()方法。所以如果list为空，会抛异常NoSuchElementException

 

offer(E e)

将指定元素添加到list末尾，并返回true

具体实现就是调用add(E e)

 

offerFirst(E e)

将指定元素添加到list头部，并返回true

具体实现就是调用addFirst(E e)

 

offerLast(E e)

将指定元素添加到list末尾，并返回true

具体实现就是调用addLast(E e)

 

peekFirst()

返回首个元素，但不删除该元素。与peek()完全相同

 

peekLast()

返回首个元素，但不删除该元素

如果list为空，则返回null

 

pollFirst()

返回首个元素，并移除该元素。与poll()完全相同

 

pollLast()

返回最后一个元素，并移除该元素

如果list为空，则返回null

 

push(E e)

将指定元素添加到list头部

具体实现就是调用addFirst(E e)

 

pop()

获取首个元素，并将将其删除

具体实现就是调用removeFirst()。所以如果list为空，会抛异常NoSuchElementException

 

removeFirstOccurrence(Object o)

删除与指定对象相等的首个元素

具体实现就是调用remove(Object o)

 

removeLastOccurrence(Object o)

删除与指定对象相等的最后一个元素

具体实现与removeFirstOccurence(Object o)类似，只是遍历的方向相反

 

listIterator(int index)

获取一个从指定索引开始的ListIterator<E>

该方法会先检查索引是否有效

 

descendingIterator()

获取一个反向的Iterator<E>（LinkedList.DescendingIterator）

 

clone()

创建一个浅拷贝的副本

具体实现就是先创建一个空的LinkedList，再遍历list，将每个元素都通过新list的add(E e)添加到新list中，最后返回新list

 

toArray()

返回一个包含各元素的数组，且这些元素的顺序与list的相同

 

toArray(T[] a)

与toArray()类似，该方法时泛型形式

对入参a的处理策略与ArrayList.toArray(T[] a)相同。即，如果不足以放下所有元素，就创建一个新的数组存放，否则就直接放到a中；如果a的空间有剩余，会将末尾元素的后一格置为null

 

spliterator()

返回一个Spliterator<E>（可分割迭代器，延迟绑定、fail-fast，用于并行遍历）。与ArrayList.spliterator()类似