LinkedList实现分析（一）——LinkedList初探与对象创建

LinkedList是Java对数据结构中链表的一种实现。
与ArrayList相比：（1）它不支持随机读取数据，或者说在根据索引值去获取元素时，需要对List进行遍历，当然了jdk对遍历元素做了优化，这点我们后面对讲到。（2）往LinkedList中增加元素，不需要对原始list进行扩容，这样可以避免在对list进行扩容的时候内存溢出。这个是什么意思？由于ArrayList是基于数组实现的，而在java中，数组的容量是不可变的，因此当ArrayList在某个状态的时候，它存储数据的数组已经饱和，如果此时再往ArrayList中增加一个元素，ArrayList会对底层数组进行扩容：创建一个包含更大数据量的数组，把老数组的数据复制到新数组，扩容的基本要求是把数据容量扩大到当前数组的1.5倍（可以参考我的另外一篇文章ArrayList实现分析（二）——常用操作），如果此时内存不足以容纳1.5倍的数据，那么就会出现内存溢出。而且当数据量很大的时候，每次老数组复制数据到新数组的时候，会消耗不少时间。个人在这里推荐：如果业务中不涉及到大量的随机读取元素的操作，尽量使用LinkedList。

下面开始介绍一下LinkedList内部提供的几个重要属性：

//当前list的大小
transient int size = 0;
//list中第一个元素
transient Node<E> first;
//list中最后一个元素
transient Node<E> last;
//该属性定义在LinkedList父类AbstractList中，表示当前list修改次数
//只要是对list进行过增删改操作，modCount都会增加
protected transient int modCount = 0;

还有一个非常重要的内部静态类Node,该类是时间存储list数据元素的类，每当有新元素添加到LinkedList中的时候，会创建一个Node对象，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;
        }
    }

Node只提供一个构造方法，创建一个Node节点，需要提供三个参数: 插入的时候的上一个节点的指针，插入的元素，插入元素的后一个元素的指针，通常是在LinkedList的尾追加新元素，因此创建Node的时候，next通常赋值为null，表示插入的元素是放在整个LinkedList的尾部。
介绍完基本的属性，下面看一下LinkedList提供了两种构造方法：

//创建一个空的list
public LinkedList() {
}
//使用Collection对象创建list
public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
}

由上面的源码可知，通过传入一个Collection对象构造LinkedList时，它实际是通过调用addAll方法把Collection对象添加到一个空的LinkedList中。addAll方法后面具体再详细介绍。下一篇文章，我们开始介绍LinkedList常用方法的实现。

最后编辑于：2019.08.22 18:30:26