LinkedList源码分析

1 集合特性

对于集合框架我们的关注点一般在一下几点：

1. 集合底层实现的数据结构是什么 双向链表
2. 集合中元素是否允许为空 是
3. 是否允许重复的数据 是
4. 是否有序(这里的有序是指读取数据和存放数据的顺序是否一致) 是
5. 是否线程安全。 否

针对这些问题，我们先来分析集合框架LinkedList

2 LinkedList分析

依赖关系
LinkedList主要是继承自AbstractSequentialList抽象类并实现了List接口、实现了Cloneable和Serializable接口使得LinkedList具有克隆和序列化的功能、实现了Deque接口和Queue因此具有队列的性质（注意对比ArrayList没有随机访问哦）。

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

add方法分析，寻找最后节点，存在插在后面，不存在创建

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

get方法分析

    /**
     判断节点小于一般正序遍历，大于一般倒序遍历
     **/
    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;
        }
    }

ps：对比ArrayList有个细节要注意

ArrayList使用最普通的for循环遍历，LinkedList使用foreach循环比较快~

ArrayList 快在寻址，慢在扩容

LinkedList 慢在寻址，插入方便。