1 LinkedList源码

LinkedList是基于链表结构的一种List，在分析LinkedList源码前有必要对链表结构进行说明。

1.1 链表的概念

链表是由一系列非连续的节点组成的存储结构，简单分下类的话，链表又分为单向链表和双向链表，而单向/双向链表又可以分为循环链表和非循环链表，下面简单就这四种链表进行图解说明

1.1.1 单向链表

单向链表就是通过每个结点的指针指向下一个结点从而链接起来的结构，最后一个节点的next指向null

[图片上传失败...(image-83de15-1636600770773)]

1.1.2 单向循环链表

单向循环链表和单向列表的不同是，最后一个节点的next不是指向null，而是指向head节点，形成一个“环”。
[图片上传失败...(image-cf103e-1636600770773)]

1.1.3 双向链表

从名字就可以看出，双向链表是包含两个指针的，pre指向前一个节点，next指向后一个节点，但是第一个节点head的pre指向null，最后一个节点的tail指向null

在这里插入图片描述

1.1.4 双向循环链表

双向循环链表和双向链表的不同在于，第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成一个环。而LinkedList就是基于双向循环链表设计的。

在这里插入图片描述

更形象的解释下就是：双向循环链表就像一群小孩手牵手围成一个圈，第一个小孩的右手拉着第二个小孩的左手，第二个小孩的左手拉着第一个小孩的右手。。。最后一个小孩的右手拉着第一个小孩的左手。

链表的概念介绍完了，下面进入写注释和源码分析部分，链表操作理解起来比数组困难了不少，所以务必要理解上面的图解，如果源码解析过程中遇到理解困难，请返回来照图理解。

1.2 定义

jdk 1.6 ，LinkedList 是双向循环链表，从jdk 1.7 后，LinkedList 是简单的双向链表。下面我们主要以jdk 1.8 的LinkedList说起
先来看看LinkedList的定义部分

1.2.1 类的属性

实际元素个数，首节点，尾节点

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

1.2.2 Node 的静态内部类

private static class Node<E>{
    E item;
    Node<E> prev;
    Node<E> next;
    Node(Node<E> prev, E element,Node<E> next){
        this.item=element;
        this.prev=prev;
        this.next=next;
    }
}

1.2.3 构造函数

 public LinkedList(){}
 public LinkedList(Collection<? extends E> c){
    this();//无参构造函数
    addAll();//添加集合中所有元素
}

1.2.4 查找 - get

先校验 index 的有效性
在查找时，先比较 index 与 (size >> 1)，即 index 与 size 中间值比较。
如果 index 较小，则从 first 开始往 last 方向遍历；
如果 index 较大，则从 last 开始往 first 方向遍历

public E get(int index){
    checkElementIndex(index);
    return node(index).item;
}
private void checkElementIndex(int index){
    if(!isElementIndex(index))
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(index) {
    return index>=0&&index<size;
}
Node<E> node(int 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;
        }
    }
}

1.2.5 添加add

注意：当从指定位置添加元素，其中可能会使用 node 方法，从查找中我们可以知道，查找当前 index 对应的 node 元素，需要遍历链表，如果增加的元素在中间，在大数据量下，花费时间可能比 ArrayList 要多

//添加元素
public boolean add(E e){
    linkLast(e);
    return true;
}
//在指定位置添加元素
public void add(int index,E element){
    checkPositionIndex(index);
    if(index==size)
        linkLast(element);
    else
        linkBefore(element,node(index));
}

① 插入到第一个元素中 - linkFirst
新添加的元素，前节点 pre 为 null，后节点 next 为原 first 节点。
新的 first 节点为当前添加的 new。
判断 first 是否为空，即添加的 new 是否是第一个元素，
如果为空，则 last 节点 为 当前节点 new；
如果不为空，last 节点不变，原 first 的前节点 pre 变更为 new，后节点 next 不变

在这里插入图片描述

private void linkFirst(E e){
    final Node<E> f = first;
    final Node<E> newNode=new Node<>(null,e,f);
    first = newNode;
    if(f==null)
        last=newNode;
    else
        f.prev=newNode;
    size++;
    modeCound++;
}

② 插入到最后一个元素中 - linkLast
新添加的元素后节点 next 为 null，前节点 pre 为原 last节点。
新的 last 节点为当前添加的 new。
判断 last 是否为空，即添加的 new 是否是第一个元素，
如果为空，则 first 节点为当前节点 new ；
如果不为空，则原 last 节点的后节点 next为当前节点 new

在这里插入图片描述

void linkLast(E e){
    final Node<E> I = last;
    final Node<E> newNode=new Node<>(I,e,null);
    last=newNode;
    if(I==null)
        first==newNode;
    else
        I.next=newNode;
    size++;
    modCount++;
}

③ 在非空节点前插入元素 - linkBefore
和 linkFirst 原理一样

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

1.2.6 修改

先校验 index 的有效性
然后node 方法返回当前 index 对应的 node 值
最后给原 node 值赋予新的 element

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

1.2.7 删除

我们可以看到 LinkedList 默认是从 first 节点开始删除数据的

public E remove(){
    return removeFirst();
}
public E removeFirst(){
    final Node<E> f =first;
    if(f==null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f){
    final E element = f.item;
    final Node<E> next = f.next;
    f.item=null;
    f.next=null;
    first=next;
    if(next==null)
        last=null;
    else
        next.prev=null;
    size--;
    modCount++;
    return element;
}