LinkedList

3.1.简介

LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列，它是基于双向链表实现的。

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

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

底层数据结构：

LinkedList底层使用的是双向链表结构

3.2.特性

• 通过链表实现
• 在频繁的插入删除数据时，使用linkedlist性能会更好

在LinkedList的源码注释中写道：

Doubly-linked list implementation of the `List` and `Deque` interfaces. Implements all optional list operations, and permits all elements (including `null`).

这告诉我们，linkedList是一个双向链表，并且实现了List和Deque接口中所有的列表操作，并且能存储任何元素，包括null

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

告诉我们，linkedList在执行任何操作的时候，都必须先遍历此列表来靠近通过index查找我们所需要的的值

也就是说，LinkedList是顺序存取的

• 顺序存取：每次操作必须先按开始到结束的顺序遍历 linkedList
• 随机存储：能够通过index。随便访问其中的任意位置的数据，这就是随机列表的意思。arrayList

然后剩余的注释主要是说明linkedList是非线程安全的（异步） ，例如在操作其Iterator时，如果改变列表结构（add\delete等）会发生fail-fast

特性总结：

1）异步，也就是非线程安全

2）双向链表。由于实现了list和Deque接口，能够当作队列来使用。

链表：查询效率不高，但是插入和删除这种操作性能好。

3）是顺序存取结构（注意和随机存取结构两个概念搞清楚）

3.3.继承结构

Object

|—AbstractCollection

     |--AbstractList

         |--AbstractSequentialList

                 |--LinkedList

LinkedList在最底层，说明他的功能最为强大，而且在ArrayList中他只有四层，这里多了一层AbstractSequentialList的抽象类，那么它是做什么的？

• 通过源码注解我们能发现：
  • 他能够减少像LinkedList这种实现顺序存取的类的工作，抽象出了一些这种类的共同的方法
  • 所以如果想实现顺序存取特性的类就去继承AbstractSequentialList抽象类，而如果想实现像ArrayList那样随机存取的类就实现AbstractList抽象类
  • 这样的分层更符合抽象的概念，越在高处的类，就越抽象，往在底层的类，就越有自己独特的个性

public abstract class AbstractSequentialList<E>
extends AbstractList<E>
//这里第一段就解释了这个类的作用，这个类为实现list接口提供了一些重要的方法，
//尽最大努力去减少实现这个“顺序存取”的特性的数据存储(例如链表)的什么鬼，对于
//随机存取数据(例如数组)的类应该优先使用AbstractList
//从上面就可以大概知道，AbstractSwquentialList这个类是为了减少LinkedList这种顺//序存取的类的代码复杂度而抽象的一个类，
This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a "sequential access" data store (such as a linked list). For random access data (such as an array), AbstractList should be used in preference to this class.

//这一段大概讲的就是这个AbstractSequentialList这个类和AbstractList这个类是完全//相反的。比如get、add这个方法的实现
This class is the opposite of the AbstractList class in the sense that it implements the "random access" methods (get(int index), set(int index, E element), add(int index, E element) and remove(int index)) on top of the list's list iterator, instead of the other way around.

//这里就是讲一些我们自己要继承该类，该做些什么事情，一些规范。
To implement a list the programmer needs only to extend this class and provide implementations for the listIterator and size methods. For an unmodifiable list, the programmer need only implement the list iterator's hasNext, next, hasPrevious, previous and index methods.

For a modifiable list the programmer should additionally implement the list iterator's set method. For a variable-size list the programmer should additionally implement the list iterator's remove and add methods.

The programmer should generally provide a void (no argument) and collection constructor, as per the recommendation in the Collection interface specification.

AbstractSequentialList

实现接口分析

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

• List接口： 列表， add、set等一些对列表进行操作的方法
• Deque接口： 有队列的各种特性
• Cloneable接口： 能够克隆，使用copy()方法
• Serializable接口：能够序列化

注意：和ArrayList不同，这里没有实现RandomAccess接口，所以不要使用for循环，而是使用iterator或foreach

3.4.类的属性

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 实际元素个数
    transient int size = 0;
    // 头结点
    transient Node<E> first;
    // 尾结点
    transient Node<E> last;
}

LinkedList的属性非常简单，一个头结点、一个尾结点、一个表示链表中实际元素个数的变量。注意，头结点、尾结点都有transient关键字修饰，这也意味着在序列化时该域是不会序列化的。

3.5.构造方法

• 空参构造

/**
 * 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
*/
//将集合c中的各个元素构建成LinkedList链表。
public LinkedList(Collection<? extends E> c) {
    // 调用无参构造函数
    this();
    // 添加集合中所有的元素
    addAll(c);
}

说明：会调用无参构造函数，并且会把集合中所有的元素添加到LinkedList中。

3.6.内部类（Node）

//根据前面介绍双向链表就知道这个代表什么了，linkedList的奥秘就在这里。
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;
    }
}

说明：内部类Node就是实际的节点，用于存放实际元素的地方

3.7.核心方法

3.7.1. add()

LinkedList包含多种add方法

• boolean add(E)
• void add(int, E)
• boolean addAll(int, Collection<? extends E>)
• boolean addAll(Collection<? Extends E>)
• void addFirst(E)
• void addLast(E)

add(E)

public boolean add(E e) {
    // 添加到末尾
    linkLast(e);
    return true;
}

add(E e)方法用于向LinkedList中添加一个元素，并且添加到链表尾部。具体添加到尾部的逻辑是由linkLast函数完成的。

LinkLast(xxx)

/**
  * Links e as last element.
*/
void linkLast(E e) {
    final Node<E> l = last; //记录添加前链表尾部节点
    final Node<E> newNode = new Node<>(l, e, null); //新建一个节点（pre，value，next） 值为传入的参数e，接上尾部节点
    last = newNode; //更新链表中的尾部节点为当前新建节点
    if (l == null) //表示链表为空
        first = newNode; //那么链表只有一个当前节点，同时也作为头节点
    else
        l.next = newNode; //不为空的情况就将上一个尾节点的next连向当前节点
    size++; //记录长度++
    modCount++;
}

Tips：所以add方法默认将元素添加到链表尾部

3.7.2.addAll()

addAll有两个重载函数addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型, 前者会转换为后者

• addAll(c)

public boolean addAll(Collection<? extends E> c) {
    //继续往下看
    return addAll(size, c);
}

• addAll(size,c)

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index); //检查index是否合理

    Object[] a = c.toArray(); //将集合c转为数组
    int numNew = a.length; //计算长度
    if (numNew == 0)
        return false; //长度为0-->失败

    Node<E> pred, succ;  //新建两个节点用于记录
    if (index == size) { //情况1: 需要存放的位置就是链表的长度-->存入末尾
        succ = null;
        pred = last; //记录上一个节点就是尾节点
    } else { //情况2: 需要插入链表中间某个位置
        succ = node(index); //记录当前位置的节点-->  前-(插入的位置)-当前位置节点
        pred = succ.prev; //记录当前位置的上一个节点
    }

    for (Object o : a) { //遍历数组将对象插入链表
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null); //新建节点，存入数据e
        if (pred == null) //表示插入的位置在头节点，没有上一个节点了
            first = newNode; //那么当前节点就变成新的头节点
        else
            pred.next = newNode; //将新的节点连接到pre节点的next上
        pred = newNode; //更新pred节点内容
    }

    if (succ == null) { //根据succ来判断是插入尾部还是插入中间
        last = pred; //插入尾部的话，last就变成了最后一个插入的节点
    } else {
        pred.next = succ; //将最后一个插入的节点的next连接到刚刚记录的当前位置节点上
        succ.prev = pred; //将当前位置节点pre连上最后插入的节点
    }

    size += numNew; //记录长度
    modCount++;
    return true;
}

说明：参数index表示插入的位置，会在下标为index节点的前面进行插入

我们注意到在方法中有这么一条succ = node(index);调用了node()方法，get()方法也会调用该方法

具体代码如下：

/**
  * Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
    // assert isElementIndex(index);
    //主要操作就是判断index在链表的前半段还是后判断然后去遍历查找
    if (index < (size >> 1)) { //index<(size/2) --> 前1/2
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next; //遍历查找
        return x;
    } else { //后1/2
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) //从尾开始往前找
            x = x.prev; 
        return x;
    }
}

根据索引查找节点，有一个小优化，先判断是前半部分还是后半部分，然后再去遍历，能提高效率

addAll()中的一个问题：

为什么要先将传入的集合转为数组，再遍历数组添加元素，而不是直接遍历呢？

1. 如果直接遍历集合的话，那么在遍历过程中需要插入元素，在堆上分配内存空间，修改指针域，这个过程中就会一直占用着这个集合，考虑正确同步的话，其他线程只能一直等待。
2. 如果转化为数组，只需要遍历集合，而遍历集合过程中不需要额外的操作，所以占用的时间相对是较短的，这样就利于其他线程尽快的使用这个集合

所以就是有利于提高多线程访问集合的效率

3.7.3.remove(Object o)

/**
     * 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
*/
//注释中提到，如果要移除一个值那么会移除index最小的那个，也就是第一次遍历到的那个
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x); //调用unlink
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x); //调用unlink
                return true;
            }
        }
    }
    return false;
}

主要就是判断o是否为null，然后遍历寻找与o相等的第一个元素，然后调用unlink移除他

unlink()

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; //去除当前节点的prev指针
    }

    if (next == null) { //如果要移除的节点是尾节点
        last = prev; //将当前节点的上一个节点变成尾节点
    } else {
        next.prev = prev; //将下一个节点的prev链到上一个节点（跳过当前节点）
        x.next = null; //去除当前节点的next指针
    }

    x.item = null; //设置为null，让gc回收他 （此时prev，item，next都为null）
    size--; //记录节点减少
    modCount++;
    return element; //将开头记录的值返回
}

移除一个节点并返回他的值

3.7.4.get(index)

/**
     * 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}
     */
//这里没有什么，重点还是在node(index)中
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

调用node(index)

/**
     * Returns the (non-null) Node at the specified element index.
     */
//这里查询使用的是先从中间分一半查找
Node<E> node(int index) {
    // assert isElementIndex(index);
    //"<<":*2的几次方 “>>”:/2的几次方，例如：size<<1：size*2的1次方，
    //这个if中就是查询前半部分
    if (index < (size >> 1)) {//index<size/2
        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;
    }
}

3.7.5.indexOf(Object o)

//这个很简单，就是通过实体元素来查找到该元素在链表中的位置。跟remove中的代码类似，只是返回类型不一样。
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;
}

3.8.迭代器

LinkedList中除了有一个Node的内部类外，还有其他两个内部类：Listltr和DescendingIterator

3.8.1.Listltr内部类

private class ListItr implements ListIterator<E> {
    ..
}

我们发现他只实现了ListIterator接口

ListIterator的结构:

我们发现ListIterator中不但有向后迭代的方法还有向前迭代的方法，所以这个内部类就是让linkedList不光能像后迭代，也能向前迭代。

查看Listltr的方法：发现在迭代的过程中，还能移除、修改、添加值的操作。

3.8.2.DescendingIterator内部类

/**
     * Adapter to provide descending iterators via ListItr.previous
     */
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();
    }
}

主要还是调用ListItr的方法，封装了一下其中的几个方法，能用正常的逻辑去向前迭代

总结

1）linkedList本质上是一个双向链表，通过一个Node内部类实现的这种链表结构。
2）能存储null值
3）跟arrayList相比较，就真正的知道了，LinkedList在删除和增加等操作上性能好，而ArrayList在查询的性能上好
4）从源码中看，它不存在容量不足的情况
5）linkedList不光能够向前迭代，还能像后迭代，并且在迭代的过程中，可以修改值、添加值、还能移除值。
6）linkedList不光能当链表，还能当队列使用，这个就是因为实现了Deque接口