LinkedList源码分析

2020-06-04

本文基于java8的代码，是分析他的数据结构，插入，查询等功能。他既实现了List，也实现了Deque，所以它既可以当做动态数组，也可以像队列那样子去使用。

数据结构

他的成本变量有以下几个：

// 长度，也就是元素个数
transient int size = 0;
// 首节点
transient Node<E> first;
//末节点
transient Node<E> 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;
        }
    }

从数据结构上我们就可以看得出LinkedList他的数据结构是以链表的形式存在，有点是插入，删除效率高，确定是无法快速通过下标进行直接查询。

主要方法分析

List接口下的方法

主要的是link系列和unlink系列的方法

add方法

在add(E e)方法中，他是往链表末端插入一个元素，是直接调用linkLast(E e)去实现的，该方法的代码和解析如下

void linkLast(E var1) {
       //找到最后一个节点
       LinkedList.Node var2 = this.last;
       //生成目标节点
       LinkedList.Node var3 = new LinkedList.Node(var2, var1, (LinkedList.Node)null);
       //末端指针指向新节点
       this.last = var3;
       //假如之前为空，则把首节点也指向新节点，否则把之前的末节点的next指针指向新节点。
       if (var2 == null) {
           this.first = var3;
       } else {
           var2.next = var3;
       }
       //长度+1
       ++this.size;
       ++this.modCount;
   }

addFirst方法

他是往链接的头部插入一个元素，是通过调用linkFirst(E e)来实现的，下面是代码和分析

private void linkFirst(E var1) {
        //找到首节点
        LinkedList.Node var2 = this.first;
        //生成新节点
        LinkedList.Node var3 = new LinkedList.Node((LinkedList.Node)null, var1, var2);
        this.first = var3;
        //假如之前为空链表则末节点也指向新节点，否则是把之前首节点的prev指向新节点
        if (var2 == null) {
            this.last = var3;
        } else {
            var2.prev = var3;
        }
        //长度+1
        ++this.size;
        ++this.modCount;
    }

get/set方法

在获取元素或者是设置某个位置的值的时候，首先第一步是调用checkElementIndex(int index)来保证获取坐标/设置坐标是合法的(即index>=0 && index<size)，否则会报IndexOutOfBoundsException。然后通过Node<E> node(int index)获得这个index位置的节点值，该方法的代码和分析如下

Node<E> node(int index) {
    //假如index比当前的size的一般小，则从开头开始遍历到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;
    }
}

得到这个Node之后，就直接返回这个Node的item值或者是设置这个Node的item值。

remove方法

包括remove(Object o)和remove(int index)

remove(Object o)，他是首先通过遍历查询到这个o所在的Node节点，然后通过unlink(Node<E> x)方法进行移除。
remove(int index )，代码和分析如下，他首先是检测这个index是否合法，然后通过node(index)获取到这个元素，在之后是通过unlink(Node<E> x)方法进行移除元素。
unlink(Node<E> x)的代码和分析如下

E unlink(Node<E> x) {
    //获取需要移除的节点的值
    final E element = x.item;
    //获取他的前后节点
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    //假如prev节点为空，那么首节点就是next节点(不管是否为空)
    //否则把前节点的next值指向之前x的next节点，然后把x.prev置为空(不再指向前节点，释放内存)
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    //假如next节点为空，则末节点是prev，否则把next节点的prev指向之前x的prev
    //，然后把x.next置为空(不再指向后节点，释放内存)
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

indexOf和lastIndexOf

他们两个比较简单，一个是从开头去遍历查找，一个是从尾部往前去查找。contains(Object o)也是通过调用indexOf(Object o)来判断元素是否存在集合中的。

Deque和Queue接口下的特有方法

boolean offer(E e)，向末尾插入元素，通过调用add实现
E poll()，把首节点移除并返回回去，通过unlinkFirst方法实现
E element()，获取首节点，首节点为null则抛出异常
E peek()，获取firt这个node的值，为null则返回Null
void addFirst(E e) ，调用linkFirst(e)实现往头部插入元素
void addLast(E e)，调用linkLast(e)实现往尾部插入元素
boolean offerFirst(E e) 调用addFirst(e)实现往头部插入元素
boolean offerLast(E e)，调用addLast(e)实现往尾部插入元素
E peekFirst()，获取首节点的值，为null则返回null
E peekLast()，获取末节点的值，为null则返回null
E pollFirst()，获取首节点的值，假如不为null则同时把该节点从链表中移除
E pollLast()，获取末节点，假如不为null则同时把末节点从来链表中移除
void push(E e)，调用addFirst
E pop()，调用removeFirst()
E removeFirst()，假如首节点不存在会报错，否则移除首节点并返回
E removeLast()，假如末节点不存在会报错，否则移除末节点并返回
E getFirst()，假如首节点不存在会报错，否则返回首节点的值
E getLast()，假如末节点不存在会报错，否则返回末节点的值

迭代器

在LinkedList中，可以通过listIterator(int index)获取在他内部实现的ListIterator对象，这个内部类可以往前或往后进行遍历，也可以增加或者删除等

其他接口的实现

Cloneable 可调用clone方法
Serializable 可序列化