LinkedList

      当比较LinkedList和ArrayList的区别时我们也许知道前者底层实现是链表，后者底层实现是数组，对于ArrayList在【此文】中详细介绍了，但是对于LinkedList的理解仅仅局限在链表而已，现在一起来看看它的底层实现吧！

类图

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

      我们发现LinkedList实现了Deque接口，它提供了对队列操作的相关方法。所以我们经常使用LinkedList去完成队列相关操作。

类前注释

      双向链表实现了List和Dqeue接口，它实现了所有的可选列表操作，它允许所有的元素类型，包括null。

      注意：LinkedList是非线程安全的。如果多个线程同时访问链接列表，并且至少有一个线程在结构上修改列表，则必须在外部进行同步。 （结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。）这通常通过在自然封装列表的对象上进行同步来实现。 如果没有这样的对象存在，列表应该使用Collections.synchronizedList方法“包装”。 这最好在创建时完成，以防止意外的不同步访问列表。

      LinkedList的iterator和listIterator方法返回的迭代器是fail-fast的:如果列表在迭代器创建之后的任何时间被结构化地修改，除了通过迭代器自己的remove或add方法之外，迭代器将会抛出ConcurrentModificationException。 因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来未确定的时间冒着任意的非确定性行为。

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

      看到next和prev就知道LinkedList不是单链表，是双向链表。

成员变量

transient int size = 0;    //记录LinkedList的大小
transient Node<E> first;   //表示LinkedList的头节点。
transient Node<E> last;    //表示LinkedList的尾节点。

构造方法

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

      LinkedList提供两个构造方法，其中需要注意的是第二个，它接受一个Collection来完成初始化。关键在于addAll方法。

public boolean addAll(Collection<? extends E> c) {
    //addAll方法可以在指定索引的节点后面插入Collection中的元素，初始化时size为0，即从头开始插入
    return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    //检查index是否合法，判断规则：index >= 0 && index <= size;
    //不合法抛出IndexOutOfBoundsException
    checkPositionIndex(index);

    //将Collection转为数组
    Object[] a = c.toArray();
    int numNew = a.length;
    //插入的集合为空，直接返回false
    if (numNew == 0)
        return false;
    
    //pred：index索引节点的前驱
    //succ：index索引表示的节点
    Node<E> pred, succ;
    if (index == size) {
        //在最末端插入节点
        succ = null;
        pred = last;
    } else {
        //添加位置在链表中
        //node()方法用于寻找index索引表示的节点
        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)
            //pred为null说明链表中无节点
            first = newNode;
        else
            pred.next = newNode;//设置前驱的后继
        //③、更新前驱
        pred = newNode;
    }

    //④、链接成完整链表
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    //更新链表的size
    size += numNew;
    modCount++;
    return true;
}

linkFirst

      私有方法，插入一个元素，并将它置为头节点。

private void linkFirst(E e) {
    //备份头节点
    final Node<E> f = first;
    //创建新节点
    final Node<E> newNode = new Node<>(null, e, f);
    //将新节点设置为头节点
    first = newNode;
    if (f == null)
        //f为空说明链表为空，插入的这个节点也是尾节点
        last = newNode;
    else
        //设置原来头节点的前驱为新节点
        f.prev = newNode;
    size++;
    modCount++;
}

linkLast

      插入一个元素，并将它置为尾节点。

void linkLast(E e) {
    //备份尾节点
    final Node<E> l = last;
    //创建新节点
    final Node<E> newNode = new Node<>(l, e, null);
    //将新节点设置为尾节点
    last = newNode;
    if (l == null)
        //f为空说明链表为空，插入的这个节点也是头节点
        first = newNode;
    else
        //设置原来尾节点的后继为新节点
        l.next = newNode;
    size++;
    modCount++;
}

getFirst

      重写来自Deque的方法，返回头节点，如果头节点为null抛出异常。

public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

getLast

      重写来自Deque的方法，返回尾节点，如果尾节点为null抛出异常。

public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

removeFirst

      重写来自Deque的方法，删除头节点并返回旧值，如果头节点为null抛出异常。

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // 断言 f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;//将数据域和后继设为null，GC帮助销毁
    f.next = null; // help GC
    //重新设置头节点
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

removeLast

      重写来自Deque的方法，删除尾节点并返回旧值，如果尾节点为null抛出异常。

remove

      删除等于指定元素的第一次出现的节点。删除成功返回true，失败返回false。

addFirst

      重写来自Deque的方法，从头部添加节点。借助linkFirst方法完成此方法。

addLast

      重写来自Deque的方法，从尾部添加节点。借助linkLast方法完成此方法。

add

      往链表中添加节点，从尾部插入。offer方法调用此方法实现尾插功能。

clear

      清空整个链表。其实就是遍历整个链表，将数据域，前驱，后继置为null。

public void clear() {
    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++;
}

get

      获取指定索引的元素值。

public E get(int index) {
    //判断索引的合法性
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    //如果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;
    }
}

set

      为指定索引的节点设置值，返回旧值。

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

indexOf

      返回此列表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1。

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

      与indexOf相似的还有lastIndexOf这一方法，它返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。

contains

      查找链表中是否有知道的元素值，返回对应的索引(第一次出现的位置)，使用indexOf实现此方法。

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

peek

      返回头节点的值，如果头节点为null则返回null。

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

      与之类似的方法还有element，但是不同的是如果链表为空则抛出NoSuchElementException。

peekLast

      返回尾节点的值，如果头节点为null则返回null。

poll

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

      出队操作，返回队首元素值。

push和pop

      push方法从头部插入元素，pop从头部删除元素。常使用这两个方法实现栈操作。

迭代器

      LinkedList为我们提供了两种迭代器，分别为ListIterator和DescendingIterator。使用ListIterator迭代器我们可以完成遍历，删除和修改节点的操作，同时这也是官方推荐我们遍历链表的方式，而不是使用fori遍历链表。使用ListIterator我们不仅可以正向遍历链表也可以反向遍历。
      descendingIterator方法来自Deque接口，使用DescendingIterator我们只能从后向前遍历，并且只提供删除操作，无法添加和修改节点。

clone

      同ArrayList一样，LinkedList的clone方法实现的是浅拷贝。

toArray

      此方法将链表中的值放在数组中，并将数组返回。

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

      使用此方法不能讲Object[]强转为其他类型，否则抛ClassCastException异常。如果我们需要实现将链表值放在指定类型数组中使用toArray(T[] a)方法。不过这里有个小坑哦！

public <T> T[] toArray(T[] a) {
    //如果你传入的数组a不够大会新建一个数组对象赋给a，
    //后序会将值赋值给新创建的数组对象，那么原来的那个数组将没有值，全为null
    //所以我们还是统一使用返回的数组就不会错了
    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;
}

版权属于：带翅膀的猫

本文链接：https://www.chengpengper.cn/archives/42/

转载时须注明出处及本声明