LinkedList源码解析

底层数据结构

LinkedList底层通过双向链表实现，双向链表的每个节点用内部类Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素，当链表为空的时候first和last都指向null。

内部结构分析：

 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;
        }
    }

实现接口:

List接口和Deque接口

LinkedList底层的链表结构使它支持高效的插入和删除操作，另外它实现了Deque接口，使得LinkedList类也具有队列的特性; LinkedList是线程不安全的，如果想使LinkedList变成线程安全的，可以调用静态类Collections类中的synchronizedList方法：

List list=Collections.synchronizedList(new LinkedList(...));

Cloneable标记接口

Cloneable:是一个标记接口,按照约定，实现Cloneable的类应当重写Object.clone()方法,但是此接口不包含clone方法，在不实现Cloneable接口的对象上调用Object的clone方法会抛CloneNotSupportedException异常。

Serializable序列化接口

说明此类可以序列化，网络传输需要序列化，只要实现了Serilizable接口，这个对象就可以被序列化，java的这种序列化模式为开发者提供了很多便利，我们可以不必关系具体序列化的过程，这个类的所有属性和方法都会自动序列化

成员属性：

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

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

  
    //指向最后一个节点的指针
    transient Node<E> last;

    //序列化版本号
    private static final long serialVersionUID = 876323262645176354L;

构造函数：

 /**
     * 构造一个空列表。
     */
    //无参构造函数构造空链表
    public LinkedList() {
    }

    /**
     *传入一个集合构造一个包含指定集合元素的列表。 
     * @param c 其元素将被放入此列表的集合 
     * @throws NullPointerException 如果指定的集合为 null抛出空指针异常
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

方法函数：

getFirst()

返回此列表中的第一个元素

/**
    返回此列表中的第一个元素
     。 @return 此列表中的第一个元素
     @throws NoSuchElementException 如果此列表为空抛出空指针异常
     */
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

getLast

*返回此列表中的最后一个元素。

/**
    返回此列表中的最后一个元素。
     @return 此列表中的最后一个元素
     @throws NoSuchElementException 如果此列表为空
     */
    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

removeFirst()和unlinkFirst(Node f)

移除并返回此列表中的第一个元素

 /**
     * 移除并返回此列表中的第一个元素。
     * @return 此列表中的第一个元素
     * @throws NoSuchElementException 如果此列表为空
     */
    public E removeFirst() {
        //引用f指向first结点
        final Node<E> f = first;
        //如果f为空抛出异常
        if (f == null)
            throw new NoSuchElementException();
        //不为空调用unlinkFirst方法
        return unlinkFirst(f);
    }
/**
     *删除第一个节点 f。
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        //保存第一个结点值
        final E element = f.item;
        //创建指向时首节点的下一个结点的指针next
        final Node<E> next = f.next;
        //头结点初始化，值设为空，后继指针设为空
        f.item = null;
        f.next = null; // help GC
        //头指针后移
        first = next;
        //如果next指针为空，说明移除结点后 链表变为空链表
        if (next == null)
            //空链表  first last都为空
            last = null;
        else
            //不为空则将头结点的前驱结点设空
            next.prev = null;
        //元素个数-1
        size--;
        //改动次数+1
        modCount++;
        //返回删除结点值
        return element;
    }

removeLast()和unlinkLast(Node l)

返回此列表中的最后一个元素。

 /**
    从此列表中删除并返回最后一个元素。
     @return 此列表中的最后一个元素
     @throws NoSuchElementException 如果此列表为空
     */
    public E removeLast() {
        //引用l指向last结点
        final Node<E> l = last;
        //如果l为空抛出异常
        if (l == null)
            throw new NoSuchElementException();
        //不为空调用unlinkLast方法
        return unlinkLast(l);
    }
 /**
     * 删除的最后一个节点 l。
     */
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        //保存结点值
        final E element = l.item;
        //创建引用prev指向尾结点的前驱结点
        final Node<E> prev = l.prev;
        //初始化清空尾结点
        l.item = null;
        l.prev = null; // help GC
        //尾结点前移
        last = prev;
        // //如果prev指针为空，说明移除结点后 链表变为空链表
        if (prev == null)
            //空链表  first last都为空
            first = null;
        else
            //不为空则将prev的后继结点设空
            prev.next = null;
        //元素个数-1
        size--;
        //改动次数+1
        modCount++;
        //返回删除结点值
        return element;
    }

add(E e)和linkLast(E e)

将指定的元素附加到此列表的末尾。 这个方法相当于 addLast()

/**
    将指定的元素附加到此列表的末尾。 这个方法相当于 addLast()
     @param e 要附加到此列表的元素
     @return {@code true} （由 {@link Collectionadd} 指定）
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
 /**
     * 链接 e 作为最后一个元素。
     */
    void linkLast(E e) {
        //创建引用常量l指向尾结点
        final Node<E> l = last;
        //用有参构造创建新节点，前驱指针指向尾结点，结点值由e赋值
        final Node<E> newNode = new Node<>(l, e, null);
        //尾指针指向新结点
        last = newNode;
        //如果链表为空
        if (l == null)
            //头指针指向新结点
            first = newNode;
        else
            //不为空则将原来的尾结点指向新节点
            l.next = newNode;
        //元素个数+1
        size++;
        //改动次数+1
        modCount++;
    }

addAll(Collection<? extends E> c)

将指定集合中的所有元素追加到此列表的末尾

 /**
    将指定集合中的所有元素追加到此列表的末尾。
     @param c 包含要添加到这个列表的元素的集合 
      @throws 如果指定的集合为 null，则为 NullPointerException
     * 
     */
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

addAll(int index, Collection<? extends E> c)

将指定集合中的所有元素插入到指定下标

 /**
   从指定位置开始，将指定集合中的所有元素插入此列表。将当前在该位置的元素（如果有）和任何后续元素向右移动（增加它们的索引）。
     @param 索引索引，在该索引处插入指定集合中的第一个元素
     @param c 包含要添加到此列表的元素的集合如果指定的集合为 null，
     则 @throws NullPointerException
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        //检查下标是否越界
        checkPositionIndex(index);

        //将集合转化为Object[]数组
        Object[] a = c.toArray();

        //记录a的长度
        int numNew = a.length;
        //如果参数a数组长度为0 返回false
        if (numNew == 0)
            return false;

        //创建结点指针pred指向要插入位置的前一个结点, succ表示要插入位置的那个结点
        Node<E> pred, succ;

        //如果要插入的位置为最后一个
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            //不为最后一个先找到对应index的结点赋值给succ
            succ = node(index);
            //要传入位置的前一个结点地址赋给pred
            pred = succ.prev;
        }

        //遍历a数组
        for (Object o : a) {
            //强转类型
            @SuppressWarnings("unchecked") E e = (E) o;
            //创建新结点前驱指针指向pred，结点值赋值
            Node<E> newNode = new Node<>(pred, e, null);
            //如果pred等于空相当于链表为空，头指针指向新结点
            if (pred == null)
                first = newNode;
            else
                //否则pred的next指向新结点
                pred.next = newNode;
            //pred指针后移
            pred = newNode;
        }

        //在末尾插入时，succ为空，为空则尾指针指向pred
        if (succ == null) {
            last = pred;
        } else {
            //否则将插入的新链表的尾部双向连接被插入的位置的结点
            pred.next = succ;
            succ.prev = pred;
        }
        //元素个数=原个数+传入集合的长度
        size += numNew;
        //改动次数+1
        modCount++;

        //返回true
        return true;
    }

addLast()

将指定的元素附加到此列表的末尾

/**
    将指定的元素附加到此列表的末尾。 <p>这个方法相当于{@link add}。
     @param e 要添加的元素
     */
    public void addLast(E e) {
        linkLast(e);
    }
 /**
     * 链接 e 作为最后一个元素。
     */
    void linkLast(E e) {
        //创建引用常量l指向尾结点
        final Node<E> l = last;
        //用有参构造创建新节点，前驱指针指向尾结点，结点值由e赋值
        final Node<E> newNode = new Node<>(l, e, null);
        //尾指针指向新结点
        last = newNode;
        //如果链表为空
        if (l == null)
            //头指针指向新结点
            first = newNode;
        else
            //不为空则将原来的尾结点指向新节点
            l.next = newNode;
        //元素个数+1
        size++;
        //改动次数+1
        modCount++;
    }

addFirst()和linkFirst(E e)

将指定的元素附加到此列表的开头

 /**
     * 在此列表的开头插入指定的元素。
     *
     * @param e the element to add
     */
    public void addFirst(E e) {
        linkFirst(e);
    }

   /**
     * 链接 e 作为第一个元素。
     */
    private void linkFirst(E e) {
        //创建常量f指向头指针
        final Node<E> f = first;
        //创建新结点，e赋值给结点值，next指针指向头指针
        final Node<E> newNode = new Node<>(null, e, f);
        //头指针指向新结点
        first = newNode;
        //如果链表为空，则f为空
        if (f == null)
            //尾结点盒指向新结点
            last = newNode;
        else
            //f(相当于原来的头结点)的前驱指针指向新结点
            f.prev = newNode;
        //元素个数+1
        size++;
        //改动次数+1
        modCount++;
    }

contains(Object o)和indexOf(Object o)

查找列表中是否包含元素o，如果此列表包含指定的元素返回true

 /**
    如果此列表包含指定的元素，则返回 {@code true}。
     @param o 要测试此列表中是否存在的元素
     @return {@code true} 如果此列表包含指定的元素
     */
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }
 /**
   返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1。
    @param o 要搜索的元素
     @return 此列表中第一次出现指定元素的索引，如果此列表不包含该元素，则为 -1
     */
    public int indexOf(Object o) {
        int index = 0;
        //如果o等于空遍历链表
        if (o == null) {
            //创建引用x指向头结点,循环条件为x不为空，每一次循环后x后移
            for (Node<E> x = first; x != null; x = x.next) {
                //如果结点值为空返回下标
                if (x.item == null)
                    return index;
                //下标++
                index++;
            }
        } else {
            //创建引用x指向头结点,循环条件为x不为空，每一次循环后x后移
            for (Node<E> x = first; x != null; x = x.next) {
                //如果结点与o相等，返回下标
                if (o.equals(x.item))
                    return index;
                //下标++
                index++;
            }
        }
        //没找到返回-1
        return -1;
    }

get(int index)

返回此列表中指定位置的元素。

/**
    返回此列表中指定位置的元素。
     @param index 要返回的元素索引
     @return 此列表中指定位置的元素
     @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
      //检查下标是否越界
        checkElementIndex(index);
        //返回对应位置的结点值
        return node(index).item;
    }


 Node<E> node(int index) {
        // assert isElementIndex(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;
        }
    }

set(int index, E element)

*返回此列表中的最后一个元素。

/**
    用指定的元素替换此列表中指定位置的元素。
     @param index 要替换的元素的索引
     @param element 要存储在指定位置的元素
     @return 之前在指定位置的元素
     @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        //检查下标是否越界
        checkElementIndex(index);
        //找到对应下标的结点赋值给x
        Node<E> x = node(index);
        //保存原结点的值
        E oldVal = x.item;
        //新值替换旧值
        x.item = element;
        //返回旧值
        return oldVal;
    }
 Node<E> node(int index) {
        // assert isElementIndex(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. LinkedList

• LinkedList底层的链表结构使它支持高效的插入和删除操作，
• 实现了Deque接口（双端队列），使得LinkedList类也具有队列的特性
• 线程不安全，性能高
• 可作为队列，栈使用

2. 与 ArrayList 的比较

ArrayList 基于动态数组实现。ArrayList 和 LinkedList 的区别可以归结为数组和链表的区别：

• 数组支持随机访问，但插入删除的代价很高，需要移动大量元素；
• 链表不支持随机访问，但插入删除只需要改变指针。