LinkedList源码分析

在我的印象里LinkedList的使用场景并没有ArrayList多，我一度认为ArrayList并没有LinkedList复杂，毕竟LinkedList是链表实现的。但是在我读完LinkedList的源码后发现，LinkedList的源码并没有ArrayList那么多的数组copy。只是单纯的链表操作。
首先看类定义

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

linkedList实现了AbstractSequentialList 这个类是一个抽象类，并且继承自AbstractList。我们知道ArrayList是直接继承自AbstractList的，这两者之间有何区别呢。
AbstractList实现随机访问数据存储集合的默认实现，例如数组 的实现ArrayList
AbstractSequentialList 实现顺序访问数据存储集合的默认实现 例如链表 的实现LinkedList
我们来对比一下两者的几个核心方法的实现
AbstractList

public boolean add(E e) { 
        add(size(), e);
        return true;
    }
abstract public E get(int index);
public E set(int index, E element) { 
        throw new UnsupportedOperationException();
    }

AbstractSequentialList

public void add(int index, E element) { 
        try { 
            listIterator(index).add(element);
        } catch (NoSuchElementException exc) { 
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }
public E get(int index) { 
        try { 
            return listIterator(index).next();
        } catch (NoSuchElementException exc) { 
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }
public E set(int index, E element) { 
        try { 
            ListIterator<E> e = listIterator(index);
            E oldVal = e.next();
            e.set(element);
            return oldVal;
        } catch (NoSuchElementException exc) { 
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

可以看到AbstractSequentialList 的实现使用的都是迭代器。迭代器只能顺序访问，这就很适合链表结构的数据结构。并且LinkedList还实现了Deque接口，Deque接口又实现了Queue接口，
Deque是一种双向队列的形式，支持在两端方向检索。
接下来开始正题:
要看LinkedList首先就要看他的数据结构 ，他核心的数据结构就是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;
        }
    }

从这个数据结构我们就能看到，他定义了自己前后的节点，这样他就实现了一种链表的结构简单举例1>2>3>4>5>null
但是光有Node是不够的 一个链表需要首尾 这时继续往下看，LinkedList的属性

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{ 
    // 定义list长度
    transient int size = 0;
    /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */
    // 首
    transient Node<E> first;
    /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */
    // 尾
    transient Node<E> last;

有了首尾，再加上 Node 的数据结构 一个链表就能够构建了。接下来我们看一下他的方法。为了方便理解，这里Node 可以理解为 一个指针
首先来看linkFirst方法

//赋值链表的第一个Node
private void linkFirst(E e) { 
        final Node<E> f = first; //得到当前的头指针
        final Node<E> newNode = new Node<>(null, e, f); //新的first 前没有node 后为原先的头指针
        first = newNode; // first变成新的头指针
        if (f == null) //如果 原来的first 是空 那么last就是这个链表里唯一的值，所以last也为他
            last = newNode; 
        else
            f.prev = newNode; // 将原来的的头指针的前引用 变成了 现在的头指针
        size++;                     
        modCount++;
    }

同样有linkFirst 就有 linkLast

void linkLast(E e) { 
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode; //将原来尾指针的后引用变成 新的尾指针
        size++;
        modCount++;
    }

之后我们来看一下 list中 最常用的方法

public boolean add(E e) { 
        linkLast(e); //这里调用了linkLast 向最后一位link一个值
        return true;
    }
//核心思路就是讲原来的last的next变成e 将e的prev变成原先的last
void linkLast(E e) { 
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

是不是很好理解呢， 就是在原本的last后面再跟一个 并把这个新的作为last就好了。
接着再来看remove方法 remove 方法有两个,先说第一个

//这里jdk做了 o==null的情况 如果==null 返回匹配到的第一个null值 ，否则去调用equals，这就是我们为何要去重写equals方法了。
public boolean remove(Object o) { 
        if (o == null) { 
            for (Node<E> x = first; x != null; x = x.next) { 
                if (x.item == null) { 
                    unlink(x);
                    return true;
                }
            }
        } else { 
            for (Node<E> x = first; x != null; x = x.next) { 
                if (o.equals(x.item)) { 
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
//这里涉及到一个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;
        //解绑 x的前后指针 
        //并且他们原先指向 x的指针 变成了新的位置
        if (prev == null) { 
            first = next;
        } else { 
            prev.next = next;
            x.prev = null;
        }
        if (next == null) { 
            last = prev;
        } else { 
            next.prev = prev;
            x.next = null;
        }
        //把x的值置为空
        x.item = null;
        size--;
        modCount++;
        return element;
    }

接下来我们看一下addAll这个方法

public boolean addAll(int index, Collection<? extends E> c) { 
        //校验index是否在范围内 这里的范围指的是 index不能小于0 且 index不能大于size(大于size 比如index = size +1 你size位置上的尾指针应该是谁的头指针呢？)
        checkPositionIndex(index);
        // 转成Obj数组
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
         //这里只需要 前一个节点 和当前节点就够了
        Node<E> pred, succ;
        if (index == size) { 
            //如果要往最后一个节点之后插入node 当前就是null 上一个节点就是原来的last
            succ = null;
            pred = last;
        } else { 
            // 否则获取当前index位置的节点
            succ = node(index);
            pred = succ.prev;
        }
        for (Object o : a) { 
            @SuppressWarnings("unchecked") E e = (E) o;
            //当前新node 的前指针指向 pred
            Node<E> newNode = new Node<>(pred, e, null);
            //如果pred为空那么first 就是新节点了，否则pred的next是当前节点
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;  //这里给挂了.next
             // 之后新节点就变成了pred
            pred = newNode;
        }
           // 插入完之后原先index位置上的节点为null 那么last就是最后插入的及诶单 ，否则 给循环添加完节点后的最后一个pred.next置为succ
        if (succ == null) { 
            last = pred;
        } else { 
            pred.next = succ;
            succ.prev = pred;
        }
        // 这样原先的链表就添加完了节点。
        size += numNew;
        modCount++;
        return true;
    }

之后我们来看一下get方法

public E get(int index) { 
        checkElementIndex(index);
        //调用了 node方法
        return node(index).item;
    }
//node方法 获取index位置上的节点
Node<E> node(int index) { 
        // assert isElementIndex(index);
        // 这里进行了一次2分 判断 index 在 size/2的左或者右 如果在左正向遍历，如果再右 反向遍历，提升效率.
        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;
        }
    }
//之前的remove方法 同样使用了 node方法
public E remove(int index) { 
        checkElementIndex(index);
        return unlink(node(index));
    }

之后是 contains 和 indexof

public boolean contains(Object o) { 
        return indexOf(o) != -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;
    }

之后是一些队列的方法 push pop peek等 很好理解 字面上就能看出来，我这里就不赘述了。
之后我来说一下迭代器 先来看我们最常用的

LinkedList linkedList = new LinkedList();
linkedList.iterator();

这里其实调的是AbstractSequentialList的iterator方法

public Iterator<E> iterator() { 
        return listIterator();
    }
public ListIterator<E> listIterator() { 
        return listIterator(0);
    }
public ListIterator<E> listIterator(final int index) { 
        rangeCheckForAdd(index);
        return new ListItr(index);
    }

这里其实AbstractSequentialList中是有ListItr这个类的但是 LinkedList自己又实现了一个内部类 起同样的名字，这里其实new ListItr其实new的是 LinkedList的ListItr，下面我们来看一下他的实现

private class ListItr implements ListIterator<E> { 
        // 上次返回的node
        private Node<E> lastReturned;
        //下一个node
        private Node<E> next;
        //下一个node 的索引值
        private int nextIndex;
        //操作次数
        private int expectedModCount = modCount;
        ListItr(int index) { 
            // assert isPositionIndex(index);
            //这里我们一般index = 0 所以next 是first
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }
        public boolean hasNext() { 
            return nextIndex < size;
        }
        public E next() { 
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();
            //这里先初始化上次返回的node 也就是这次查询的值
            lastReturned = next;
            //下一个节点
            next = next.next;
            //索引++
            nextIndex++;
            return lastReturned.item;
        }
        、、是否有上一个节点
        public boolean hasPrevious() { 
            return nextIndex > 0;
        }
        //这里能够向前 查询 
        public E previous() { 
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();
            //这里next 就等于上一个节点
            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }
        public int nextIndex() { 
            return nextIndex;
        }
        public int previousIndex() { 
            return nextIndex - 1;
        }
        public void remove() { 
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();
            //remove先记录下上次next返回结果的 下一个节点
            Node<E> lastNext = lastReturned.next;
            //然后将上次next 的指针去掉
            unlink(lastReturned);
           if (next==lastReturned)　　//这里表示删除的是调用previous()返回的元素。
　　        next =  lastNext;　//next被删除，所以next要后移，索引不变。
            else
                nextIndex--;   // 这里表示 调用next()返回的元素 被删了 ，所以要索引--
            lastReturned = null; //保证 不能连续删除 必须调用next 或者 previous
            expectedModCount++;
        }
        //后面这两个方法就很简单了
        public void set(E e) { 
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }
        public void add(E e) { 
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }
         //这里循环操作 action的操作
        public void forEachRemaining(Consumer<? super E> action) { 
            Objects.requireNonNull(action);
            while (modCount == expectedModCount && nextIndex < size) { 
                action.accept(next.item);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
            checkForComodification();
        }
        //如果有并发操作这个 对象 ，抛出异常
        final void checkForComodification() { 
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

jdk1.6后又提供了反向迭代器

/** * @since 1.6 */
    public Iterator<E> descendingIterator() { 
        return new DescendingIterator();
    }
    /** * 这里 next调previous 除了remove 都是反过来 */
    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();
        }
    }

接着我们看clone

@SuppressWarnings("unchecked")
    private LinkedList<E> superClone() { 
        try { 
            return (LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) { 
            throw new InternalError(e);
        }
    }
    /** * Returns a shallow copy of this {@code LinkedList}. (The elements * themselves are not cloned.) * * @return a shallow copy of this {@code LinkedList} instance */
    // 这里很简单，循环，add()
    public Object clone() { 
        LinkedList<E> clone = superClone();
        // Put clone into "virgin" state
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;
        // Initialize clone with our elements
        for (Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);
        return 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;
    }
public <T> T[] toArray(T[] a) { 
        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;
 /* * <p>如果列表适合指定的数组，并且有空余空间（即， *数组中包含的元素多于列表中的元素，即数组中的元素 *在列表结尾之后立即设置为{@code null}。 *（这对于确定列表的长度非常有用<i>仅</ i>如果 *调用者知道列表不包含任何null元素。） */
        if (a.length > size)
            a[size] = null;
        return a;
    }

这里我复制了这个方法的描述 ，但是我感觉这个东西并没什么卵用，因为你无法保证调用这 不含null元素，你只将size索引置为null 后面的还是不为null

@Test
    public void test1(){ 
        LinkedList linkedList = new LinkedList();
        linkedList.add("1");
        linkedList.add("2");
        linkedList.add("3");
        linkedList.add("4");
        System.out.println(linkedList);
        String[] strs = { null,null,null,null,"3223","1222","234455"};
        Object[] objects = linkedList.toArray(strs);
        for(Object o: objects){ 
            System.out.println(o);
        }
    }

打印结果

[1, 2, 3, 4]
1
2
3
4
null
1222
234455

我这里比较困惑，希望有大神给我解读一下。
LinkedList的源码解析就到这里 jdk1.8新增的并发迭代器Spliterator linkedlist也有实现，我没仔细研究 ，后续补上。