LinkedList 源码解析

1、链表概念

• LinkedList 实现了List接口和Deque接口，所以它既可以看作一个列表(List)，又可以看作一个队列(Queue)，那也就可以作为栈(Stack)。
• LinkedList 可以作为列表、栈、队列、双向队列使用。可以说是很强大了。但如果栈或队列，首选还是ArrayDeque，因为它的性能会比LinkedList更好。
• LinkedList 底层是双向链表，所以它支持高效的插入和删除操作，但是不支持随机访问。

链表概念

链表是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。链表比数组占用更多的内存空间。

源码

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // ...
}

2、变量参数说明

LinkedList 的参数主要记录了链表的节点个数、第一个节点和最后一个节点。

源码

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;

• transient int size：表示LinkedList中元素的个数。被标记为transient的成员变量不会被序列化保存和恢复，这是因为LinkedList的大小可以通过遍历链表计算得到，所以不需要序列化保存和恢复该值。
• transient Node first：表示链表的第一个节点。被标记为transient的成员变量不会被序列化保存和恢复，因为根据链表结构，first指针可以重建。
• transient Node last：表示链表的最后一个节点。被标记为transient的成员变量不会被序列化保存和恢复，因为根据链表结构，last指针可以重建。

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

包含了数据、上一个节点和下一个节点。

3、构造函数

LinkedList 提供了两个构造函数，一个无参构造函数和一个包含集合的构造函数。用法和ArrayLi

源码

/**
 * Constructs an empty list.
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

4、getFirst()和getLast()

获取第一个节点和获取最后一个节点，这个就比较简单，因为LinkedList的内部结构就是由first和last两个指针来维护的。

源码

/**
 * Returns the first element in this list.
 *
 * @return the first element in this list
 * @throws NoSuchElementException if this list is empty
 */
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

/**
 * Returns the last element in this list.
 *
 * @return the last element in this list
 * @throws NoSuchElementException if this list is empty
 */
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

5、四个remove()方法

• removeFirst()：移除第一个节点
• removeLast()：移除最后一个节点
• remove(e)：移除指定元素节点
• remove(index)：移除指定下标节点

删除节点

• removeFirst()

将第一个节点置空，并将第二个节点赋值给第一个节点。原来的第一个节点内存就释放移除了。

源码

/**
 * 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()

直接将最后最后一个节点置空，并将LinkedList中记录的最后一个节点执行最后一个节点的上一个节点。

源码

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

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

• remove(e)

移除指定元素，判断的依据是equals方法， 如果equals，则直接unlink这个node；由于LinkedList可存放null元素，故也可以删除第一次出现null的元素。

源码

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If this list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns {@code true} if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return {@code true} if this list contained the specified element
 */
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;
}

/**
 * Unlinks non-null node x.
 */
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; // GC
    size--;
    modCount++;
    return element;
}

• remove(index)

使用的是下标计数， 只需要判断该index是否有元素即可，如果有则直接unlink这个node。

源码

/**
 * Removes the element at the specified position in this list.  Shifts any
 * subsequent elements to the left (subtracts one from their indices).
 * Returns the element that was removed from the list.
 *
 * @param index the index of the element to be removed
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

6、add()和addAll()

插入节点

• add() 插入节点，提供了两种方式，一种是直接插入，一种是插入到指定位置。

源码

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * Links e as last element.
 */
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++;
}

/**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    checkPositionIndex(index);

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

• 尾部插入：直接将最后一个节点的下一个节点指向下一个节点即可。
• 指定位置插入：当index==size时，等同于add(E e); 如果不是，则分两步:
  1. 先根据index找到要插入的位置,即node(index)方法。
  2. 修改引用，完成插入操作。

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

• addAll()

addAll(index, c) 实现方式并不是直接调用add(index,e)来实现，主要是因为效率的问题，另一个是fail-fast中modCount只会增加1次。而是单独循环插入。

源码

/**
 * Appends all of the elements in the specified collection to the end of
 * this list, in the order that they are returned by the specified
 * collection's iterator.  The behavior of this operation is undefined if
 * the specified collection is modified while the operation is in
 * progress.  (Note that this will occur if the specified collection is
 * this list, and it's nonempty.)
 *
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

/**
 * Inserts all of the elements in the specified collection into this
 * list, starting at the specified position.  Shifts the element
 * currently at that position (if any) and any subsequent elements to
 * the right (increases their indices).  The new elements will appear
 * in the list in the order that they are returned by the
 * specified collection's iterator.
 *
 * @param index index at which to insert the first element
 *              from the specified collection
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
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;
}

7、set()和get()

set()是指定位置重新赋值，get()获取指定位置的值。

源码

/**
 * Replaces the element at the specified position in this list with the
 * specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

 /**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

8、clear()

清空不是直接将LinkedList设为null，而是要将每个节点内存释放。为了让GC更快可以回收放置的元素，需要将node之间的引用关系赋空。

源码

/**
 * Removes all of the elements from this list.
 * The list will be empty after this call returns.
 */
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++;
}

9、查找

LinkedList 底层是链表，查找起来就得通过循环去找。所以查找效率不如ArrayList。我们看两个查找方法，indexOf(Object o)和lastIndexOf(Object o)

• indexOf(Object o) 查找第一次出现的index, 如果找不到返回-1；

/**
 * Returns the index of the first occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the lowest index {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * @param o element to search for
 * @return the index of the first occurrence of the specified element in
 *         this list, or -1 if this list does not contain the element
 */
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;
}

• lastIndexOf(Object o) 查找最后一次出现的index, 如果找不到返回-1；

/**
 * Returns the index of the last occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the highest index {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * @param o element to search for
 * @return the index of the last occurrence of the specified element in
 *         this list, or -1 if this list does not contain the element
 */
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;
}

10、Queue常用方法概览

Queue（队列）是一种遵循先进先出（FIFO）原则的集合。

方法	说明
boolean add(E e)	将指定的元素插入此队列的尾部。如果队列已满，则抛出一个IllegalStateException异常。
boolean offer(E e)	将指定的元素插入此队列的尾部。如果队列已满，则返回false。
E remove()	移除并返回队列头部的元素。如果队列为空，则抛出一个NoSuchElementException异常。
E poll()	移除并返回队列头部的元素。如果队列为空，则返回null。
E element()	返回队列头部的元素。如果队列为空，则抛出一个NoSuchElementException异常。
E peek()	返回队列头部的元素。如果队列为空，则返回null。
boolean isEmpty()	如果队列为空，返回true；否则返回false。
int size()	返回队列中的元素个数。
void clear()	移除队列中的所有元素。

11、Deque常用方法概览

Deque（双端队列）是一种可以在两端（头和尾）进行操作的队列。Deque接口继承自Queue接口，因此拥有Queue的一些方法，同时还拥有一些新增的方法。

方法	说明
void addFirst(E e)	将元素添加到双端队列的头部。
void addLast(E e)	将元素添加到双端队列的尾部。
boolean offerFirst(E e)	将元素添加到双端队列的头部，并返回添加是否成功。
boolean offerLast(E e)	将元素添加到双端队列的尾部，并返回添加是否成功。
E removeFirst()	移除并返回双端队列的头部元素。如果队列为空，则抛出NoSuchElementException异常。
E removeLast()	移除并返回双端队列的尾部元素。如果队列为空，则抛出NoSuchElementException异常。
E pollFirst()	移除并返回双端队列的头部元素。如果队列为空，则返回null。
E pollLast()	移除并返回双端队列的尾部元素。如果队列为空，则返回null。
E getFirst()	返回双端队列的头部元素，但不移除元素。如果队列为空，则抛出NoSuchElementException异常。
E getLast()	返回双端队列的尾部元素，但不移除元素。如果队列为空，则抛出NoSuchElementException异常。
E peekFirst()	返回双端队列的头部元素，但不移除元素。如果队列为空，则返回null。
E peekLast()	返回双端队列的尾部元素，但不移除元素。如果队列为空，则返回null。
boolean removeFirstOccurrence(Object o)	移除双端队列中首次出现的指定元素。
boolean removeLastOccurrence(Object o)	移除双端队列中最后一次出现的指定元素。