27.3 Java集合学习之List（基本概念，API，存储原理）

1. List接口

在学习List接口之前我们还是得复习下这张图

从图中我们知道了，List接口继承了Collection接口。
也就是说List接口是在Collection接口的基础上衍生出来的具体的链表数据结构的接口，在Java集合中，链表数据结构类都必须要实现List接口。
通过查看List接口的定义并和Collection接口进行比较，可以找到，专属于List接口的方法有：

//指定开始位置将另一个集合的元素插入进List中
boolean addAll(int index, Collection<? extends E> c);

//将List中的元素通过传入的Operator进行替换处理
default void replaceAll(UnaryOperator<E> operator) {
    Objects.requireNonNull(operator);
    final ListIterator<E> li = this.listIterator();
    while (li.hasNext()) {
        li.set(operator.apply(li.next()));
    }
}

//将List中的元素通过传入的Comparator进行排序处理
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

//根据索引位置得到指定位置的元素
E get(int index);

//重置指定索引位置的元素
E set(int index, E element);

//向指定位置插入新的元素
void add(int index, E element);

//删除指定位置的元素
E remove(int index);

//得到第一个和对象o相等的对象的位置
int indexOf(Object o);

//得到最后一个和对象o相等的对象的位置
int lastIndexOf(Object o);

// 获得链表迭代器
ListIterator<E> listIterator();

//获得指定起始位置的链表迭代器
ListIterator<E> listIterator(int index);

//获得指定位置范围的链表
List<E> subList(int fromIndex, int toIndex);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

2. List的具体实现

在具体的查看源码前，我们可以根据上面的图片先猜出那些具体的集合是通过实现List接口来定义的：
ArrayList, LinkedList 这是两个比较明显的实现了。

2.1 ArrayList

简单概况一下ArrayList的实现就是：
ArrayList是基于动态数组实现的一个链表数据结构实现的一个线程不安全的类。
它的使用特性是插入，删除慢。修改快，查询快，且支持随机查询（根据get(int index)能以常数时间获取元素）。

2.1.1 存储原理

• 开辟存储存储空间：
  如果使用的是默认无参构造方法，size1.5<=size+1，则为elementData开辟10个对象空间。
  如果使用的是指定数量的构造方法，size1.5<=size+1，则为elementData开辟size+1个对象空间。
• 扩容机制：
  每次添加前会对size+1进行检查
  如果在原数组的基础上增加了一半后大于size+1且小于MAX_ARRAY_SIZE,则将数组扩容至150%大小。

具体的实现可以查阅Jdk源码来进行学习。

2.1.2 性能测试实例

//完整代码地址在文章最后
public static void main(String[] args) {
    List<Integer> list = addTest(100000);
    System.out.println("修改耗时："+updateTest(list)+"ms");
    System.out.println("查询耗时： "+queryTest(list)+"ms");
    System.out.println("插入耗时： "+insertTest(list)+"ms");
    System.out.println("删除耗时： "+deleteTest(list)+"ms");
}
1
2
3
4
5
6
7
8

上面的测试结果实事求是的验证了ArrayList的 插入，删除慢。

2.2 LinkedList

简单概述一下LinkedList的实现就是：LinkedList是基于双向链表实现的一个链表数据结构实现的一个线程不安全的类。

2.2.1 存储原理

LinkedList 采用链表存储，如果是在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e) addLast(E e)、removeFirst()、 removeLast()），时间复杂度为 O(1)，效率非常好。
如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入。但是不需要进行原有数据的整体移动处理。

需要注意的是： LinkedList不支持高效随机元素访问，ArrayList支持。 LinkedList则无需担心扩容问题，它的存储原理是需要的时候进行开辟空间，然后通过引用链接到一起，所以LinkedList的存储位置是碎片化，不连续的。

具体的实现请查阅源码。

2.2.2 性能测试实例

//代码地址在文章最后
public static void main(String[] args) {
    List<Integer> list = addTest(100000);
    System.out.println("修改耗时："+updateTest(list)+"ms");
    System.out.println("查询耗时： "+queryTest(list)+"ms");
    System.out.println("插入耗时： "+insertTest(list)+"ms");
    System.out.println("删除耗时： "+deleteTest(list)+"ms");
}
1
2
3
4
5
6
7
8

可以看到，相比而言，其总体性能和ArrayList相比差距还是较大的。

2.3 Vector

其实除了ArrayList, LinkedList两种有名的实现之外，JDK最开始提供的List的实现版本是Vector但是它的性能和功能都逐渐被淘汰了。

2.3.1 存储原理

Vector底层用的是数组实现。 它的关键操作方法都是同步的，这使得线程安全，但是性能不好。

• 开辟内存空间
  默认开辟10个内存空间
• 扩容机制
  既然是使用数组实现，那么它也一定会有相应的扩容机制，每次添加前会对elementCount+1进行检查，
  如果它大于了数组长度，则进行扩容，采用的基本逻辑是如果指定了扩容大小capIncre，则扩为 oldCap+capIncre,否则进行两倍扩容。扩完后如果还是小于elementCount+1,则newCap = elementCount+1
  还进行了一些极限纠正。

具体的实现请查阅源码。

2.3.2 性能测试实例

//完整代码地址见下方链接
public static void main(String[] args) {
    List<Integer> list = addTest(100000);
    System.out.println("修改耗时："+updateTest(list)+"ms");
    System.out.println("查询耗时： "+queryTest(list)+"ms");
    System.out.println("插入耗时： "+insertTest(list)+"ms");
    System.out.println("删除耗时： "+deleteTest(list)+"ms");
}
1
2
3
4
5
6
7
8

可以看到在这个测试实例下，Vector的性能和ArrayList相差不大。
但是，在多线程的情况下它的性能下降的还是很厉害的。

完整代码地址：
https://gitee.com/yan-jiadou/study/tree/master/Java%E5%9F%BA%E7%A1%80%E5%AD%A6%E4%B9%A0/src/main/java/Progress/exa27_3

LinkedList部分参考了文章： https://javaguide.cn/java/collection/java-collection-questions-01.html#collection-%E5%AD%90%E6%8E%A5%E5%8F%A3%E4%B9%8B-list