LinkedList

「这是我参与11月更文挑战的第4天，活动详情查看：2021最后一次更文挑战」

LinkedList简介
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口，能对它进行队列操作。 LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。 LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。 LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。 LinkedList 是非同步的。

数据结构

源码解析
方法字段
public class LinkedList

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

{

//元素个数
transient int size = 0;

/**
 * 指向第一个节点
 * 
 */
transient Node<E> first;

/**
 * 指向最后一个节点
 */
transient Node<E> last;
.
.
.
.
}

构造函数

/**
 * 空的构造函数
 */
public LinkedList() {
}

/**
 * 包含一个数组的构造函数，链表中的顺序按照集合中的元素顺序进行插入
 *
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);//这里调用了addAll(),就是插入所有元素
}

addAll(int index, Collection c)
插入给定集合的元素，从指定的index开始插入

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;//前驱为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//否则在index前面插入新节点
            pred.next = newNode;
        pred = newNode;//前驱为新节点
    }

    if (succ == null) {//后继为空
        last = pred;//在末尾插入
    } else {
        pred.next = succ;//否则链接最后的节点
        succ.prev = pred;
    }

    size += numNew;//节点个数增加
    modCount++;//结构性修改
    return true;
}

linkFirst(E e)
在头部插入一个新节点

private void linkFirst(E e) {
    final Node<E> f = first;//1、创建一个引用
    final Node<E> newNode = new Node<>(null, e, f);//2、创建新节点，它的下一个节点为当前的头结点
    first = newNode;//3、头引用指向新节点
    if (f == null)//如果没有头结点，只有尾结点
        last = newNode;//新节点为尾结点
    else
        f.prev = newNode;//4、否则之前的头结点的前引用指向新节点
    size++;
    modCount++;
}

linkLast(E e)
在尾部插入一个新节点，过程与在头部插入类似

void linkLast(E e) {

    final Node<E> l = last;//创建一个指向尾部的指针
    final Node<E> newNode = new Node<>(l, e, null);//创建新节点，新节点的前一个节点为当前的尾结点
    last = newNode;//last引用指向新节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;//当前尾结点的前引用指向新的尾结点
    size++;
    modCount++;
}

linkBefore(E e, Node succ)
在某个节点之前插入一个新节点

void linkBefore(E e, Node 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++;
}

indexOf(Object o)
从前向后查找，返回“值为对象(o)的节点对应的索引, 不存在就返回-1

public int indexOf(Object o) {
    int index = 0;
    if (o==null) {
        for (Entry e = header.next; e != header; e = e.next) {
            if (e.element==null)
                return index;
            index++;
        }
    } else {
        for (Entry e = header.next; e != header; e = e.next) {
            if (o.equals(e.element))
                return index;
            index++;
        }
    }
    return -1;
}

lastIndexOf(Object o)
从后向前查找，返回“值为对象(o)的节点对应的索引，不存在就返回-1*

public int lastIndexOf(Object o) {

    int index = size;
    if (o==null) {
        for (Entry e = header.previous; e != header; e = e.previous) {
            index--;
            if (e.element==null)
                return index;
        }
    } else {
        for (Entry e = header.previous; e != header; e = e.previous) {
            index--;
            if (o.equals(e.element))
                return index;
        }
    }
    return -1;
}

add(E e):队尾插入新节点，如果队列空间不足，抛出异常；LinkedList没有空间限制，所以可以无限添加。

offer(E e):队尾插入新节点，空间不足，返回false，在LinkedList中和add方法同样效果。

remove():移除队头节点，如果队列为空（没有节点，first为null），抛出异常。LinkedList中就是first节点（链表头）

poll()：同remove，不同点：队列为空，返回null

element()：查询队头节点(不移除)，如果队列为空，抛出异常。

peek()：同element，不同点：队列为空，返回null。

/**

 * 检索头结点元素
 */
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

/**
 * 与peek()作用一样
 */
public E element() {
    return getFirst();
}

/**
 * 删除并返回第一个节点
 */
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * 与poll()作用一样
 */
public E remove() {
    return removeFirst();
}

/**
 * 在尾部添加节点与add()一样
 */
public boolean offer(E e) {
    return add(e);
}

// Deque operations

/**

 * 调用add是在最后链接的
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

总结
LinkedList是基于双向链表实现的，不论是增删改查方法还是队列和栈的实现，都可通过操作结点实现 LinkedList无需提前指定容量，因为基于链表操作，集合的容量随着元素的加入自动增加 LinkedList删除元素后集合占用的内存自动缩小，无需像ArrayList一样调用trimToSize()方法 LinkedList的所有方法没有进行同步，因此它也不是线程安全的，应该避免在多线程环境下使用