Java，数据结构与集合源码，关于List接口的实现类（ArrayList、Vector、LinkedList）的源码剖析

目录

ArrayList

ArrayList的特点：

ArrayList源码解析：

Vector

Vector的特点：

Vector源码解析：

LinkedList

LinkedList的特点：

LinkedList的源码剖析：

使用说明：

---

ArrayList

ArrayList的特点：

·实现类List接口，存储有序的、可以重复的数据。

·底层使用Object[ ]数组存储数据。

·线程不安全的。

ArrayList源码解析：

jdk7版本：

ArrayList<String> list = new ArrayList<>();//①

list.add("AA");//②

list .add( "BB" );//③

……

①处在new时，底层初始化了Object类型的数组elementData，初始化长度为10，即Object[ ] elementData = new Object[10];（类似于饿汉式）

②处相当于将elementData数组的元素下标为0的元素赋值为“AA”。即element[0] = "AA";

③处相当于将elementData数组的元素下标为1的元素赋值为“BB”。即element[1] = "BB";

当要添加第11个元素的时候，底层的element数组已满，则需要扩容。默认扩容为原来长度的1.5倍，并将原有数组中的元素复制到新的数组中。

jdk8版本：

ArrayList<String> list = new ArrayList<>();//①

list.add("AA");//②

list .add( "BB" );//③

……

①处在new时，底层初始化了Object类型的数组elementData，即Object[ ] elementData = new Object[ ]{};（类似于懒汉式）

②处首次添加元素时，会初始化数组elementData = new Object[10];   再将elementData数组的元素下标为0的元素赋值为“AA”。即element[0] = "AA";

③处相当于将elementData数组的元素下标为1的元素赋值为“BB”。即element[1] = "BB";

当要添加第11个元素的时候，底层的element数组已满，则需要扩容。默认扩容为原来长度的1.5倍，并将原有数组中的元素复制到新的数组中。

Vector

Vector的特点：

·实现类List接口，存储有序的、可以重复的数据。

·底层使用Object[ ]数组存储数据。

·线程安全的。

Vector源码解析：

（jdk8）

Vector v = new Vector();//①

v.add("AA");//②

v.add("BB");//③

①处在new时，底层初始化了Object类型的数组elementData，初始化长度为10，即Object[ ] elementData = new Object[10];（类似于饿汉式）

②处相当于将elementData数组的元素下标为0的元素赋值为“AA”。即element[0] = "AA";

③处相当于将elementData数组的元素下标为1的元素赋值为“BB”。即element[1] = "BB";

当要添加第11个元素的时候，底层的element数组已满，则需要扩容。默认扩容为原来长度的2倍，并将原有数组中的元素复制到新的数组中。

LinkedList

LinkedList的特点：

·实现类List接口，存储有序的、可以重复的数据。

·底层使用双向链表存储数据。

·线程不安全的。

LinkedList的源码剖析：

（jdk8）

LinkedList<String> list = new LinkedList<>();//①

list.add("AA");//②

list.add("BB");//③

①处并没有什么执行操作

②处将“AA”封装到一个Node对象1中，list对象的属性frist、last都指向此Node对象1。

③处将“BB”封装到一个Node对象2中，Node对象1和Node对象2构成双向链表，同时last指向Node对象2

因为LinkedList使用的是双向链表，不需要考虑扩容问题。

使用说明：

Vector基本不使用。

ArrayList底层使用数组结构，查找和添加操作效率高，时间复杂度为O(1)。删除和插入操作效率低，时间复杂度为O(n)。

LinkedList底层使用双向链表，查找和添加操作效率低，时间复杂度为O(n)。删除和插入操作效率高，时间复杂度为O(1)。

ArrayList除了有空参的构造器，默认底层长度为10之外，还可以传入int类型的值指定底层数组的长度。如果需要的底层数组长度大，又知道大概的数组长度需求，使用此指定底层数组长度的构造器可以避免频繁的新建的数组，让程序效率提高。