Java容器篇小结之List自问自答

I. List篇

0. 什么是List

看到这个有点懵逼，一时还真不知道怎么解释，能让完全没有接触过的人都能听懂

列表，什么是列表呢？

好比你到了一个村里，看到每个房子上的门牌号，如这是张村1号，下一个是张村2号，接着是3号、4号...

现在你要去张村10号，那么得，顺着这个门牌一直往下走，就能找到了

这个村落里的门牌号的形式，就特别像JDK中的 LinkedList了，找张村10号的过程基本就是 LinkedList#indexOf()根据索引获取对应值的过程了

从这个case里面，小结一下List的特点

• 顺序性，有序（一个接一个，像冰糖葫芦似的串在一起）
• 唯一性（一个萝卜一个坑，不允许一个索引捞出多个内容出来）

这个顺序性好说，这个唯一性是我一家之言，多半描述得不太妥当，出发是为了与Map进行对比 ，下面重点说明一下

之前的博文Java Map常见问题汇总小结 把Map比作了词典，换在这里比作村牌号，可以这么玩，将户主名和门牌号一一对应，你报一个户主名，我就告诉你他家门牌号，然后就有这么个问题了

• 张三家的门牌是张村五号
• 后面张五家生了个小孩，也取名叫张三，然后张三自立门户了，门牌分的是张村105号

现在我问张三家门牌是多少？是五号呢还是105呢？这个就不唯一了

换成链表的方式，你报一个门牌号，要么这门牌号无效，要么就只有一家在哪儿等着你呢，这就是我所说的唯一性

（废话比较多，可惜没有稿费）

1. 常见的List有那些

JDK中实现了一些能够覆盖绝大部分场景的List容器，罗列一些常见的如下

• ArrayList
• LinkedList
• Vector
• CopyOnWriteArrayList

2. 根据不同的分类方式，对上面的List进行划分

根据是否线程安全分类

根据获取数据的时间复杂度

这个分类有点意思了，前面三个，给了索引，立马就把数据给你；这后面的一个，得遍历一把找到对应的位置再返回数据，详情建第四条

底层数据结构

扩容原理分类

3. ArrayList怎么用，如何实现的

基于数组的链表 ArrayList, 常用做有序数据存储的容器，一般使用的三把斧

// 1. 创建数组
List<String> list = new ArrayList<>();

// 2. 添加数据
list.add("word");
list.add(0, "hello");

// 3. 获取数组
list.get(0);

实现原理简要说明

• ArrayList底层数据结构为数组
• add(obj)会将数据直接扔进数组中，索引为当前列表的长度size，然后size+1
• 若数组已经满了，塞不下新的数据了，此时需要将数组扩容，优先扩容原来容量的1.5倍（若依旧不够，则扩容到恰好能容纳所有元素）
• add(index, obj)， 在索引处添加数据，会导致原数组中，索引之后的数据后移（即会出现数组拷贝）
• 删除末尾数据，直接将其置为null
• 删除数组内部的数据，会出现数组拷贝
• 删除元素，不会导致数组扩容（缩容）
• 查询索引位置内容，实际上是直接利用数组的获取方式

4. ArrayList, LinkedList区别与适用场景

两者的底层存储结构不同，直接导致最终的使用场景的区别，下面以列表方式给出对比

5. ArrayList是否线程安全，如何保证线程安全

ArrayList 非线程安全，即在遍历一个ArrayList对象时，若出现修改，则会抛一个并发修改异常，通常为了保障线程安全，请使用 CopyOnWriteArrayList代替，至于Vector，已经退出历史舞台了

Vector

线程安全的列表，其实现是在所有的方法上加了同步锁，确保同一时刻，只有一个线程在访问列表，是一种伪并发的使用方式

CopyOnWriteArrayList

写副本，替换原链表的方式实现线程安全，基本原理如下

• 读方法不加锁；修改方法加锁，一次只能一个写线程访问
• 修改时，会拷贝一份内容出来，对拷贝的结果进行操作，最后覆盖之前的内容
• 遍历和读取都是基于访问时刻列表中的数组进行的；在执行过程中，链表发生修改不会影响遍历和读取的结果（即此时访问的依然是原数组内容）

6. 几种遍历方式

把这个单独拎出来有点混字数的感觉（多谢也没有啥收益，纯属手欠...）

一般的遍历方式是采用foreach语法

List<String> strList = new ArrayList<>();
// ....
for(String str: strList) {
  System.out.println(str);
}

还有一种用得较少，一般是在要遍历的过程中，修改列表的值时使用

List<String> strList = new ArrayList<>();
Iterator<String> iterator = strList.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
    if(xxx) {
        iterator.remove();
    }
}

那么问题来了，在第一种方式中，若是修改了会怎么样

@Test
public void testRemove() {
    List<String> strList = new ArrayList<String>();
    strList.add("hello");
    strList.add("world");
    strList.add("test1");
    strList.add("test2");
    strList.remove(0);
    int i = 0;
    for(String str: strList) {
        System.out.println(str);
        if(++i == 1) {
            strList.remove(i);
        }
    }
}

抛了并发修改异常

7. 如何设计一个线程安全的ArrayList

完全照着CopyOnWriteArrayList抄的话就没意思了，然而让自己去想一个方案，可以怎么搞？实现省略，暂时没想法。。。