Java后端高频面试问题：ArrayList相关

1.ArrayList和LinkedList的区别？

1.底层数据结构：

Arraylist 底层使⽤的是 Object 数组； LinkedList 底层使⽤的是双向链表数据结构。

（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别。）

2.插入和删除是否受元素位置的影响：

① ArrayList 采⽤数组存储，所以插⼊和删除元素的时间复杂度受元素位置的影响。当在尾部添加时，时间复杂度为O(1)，当在指定位置插入和删除元素，时间复杂度为O(n)，因为插入元素位置之后的元素都要向后移1位，删除元素位置之后的元素都要向前移1位。

②LinkedList采用链表存储，所以在对于 add(E e) ⽅法的插⼊，删除元素时间复杂度不受元素位置的影响，近似 O（1），如果是要在指定位置 i 插⼊和删除元素的话（ (add(int index, E element) ） 时间复杂度近似为 o(n)) 因为需要先移动到指定位置再插⼊。

3.是否支持快速随机访问：LinkedList 不⽀持⾼效的随机元素访问，⽽ArrayList⽀持。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) ⽅法)。

4.内存空间占用：ArrayList的空间浪费主要体现在在list列表的结尾会预留⼀定的容量空间，⽽LinkedList的空间花费则体现在它的每⼀个元素都需要消耗⽐ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

2.ArrayList和LinkedList线程不安全该怎么解决？

线程安全解决方法：

方法1：Collections.synchronizedList(new LinkedList<String>)

SynchronizedList是Collections的内部类，Collections提供了synchronizedList方法，可以将一个

线程不安全的List包装成线程安全的List，即SynchronizedList。它比Vector有更好的扩展性和兼

容性，但是它所有的方法都带有同步锁，也不是性能最优的List。

方法2：将ArrayList和LinkedList换成线程安全的集合

如CopyOnWriteArrayList、ConcurrentLinkedQueue等

CopyOnWriteArrayList是Java 1.5在java.util.concurrent包下增加的类，它采用复制底层数组的方

式来实现写操作。当线程对此类集合执行读取操作时，线程将会直接读取集合本身，无须加锁与阻

塞。当线程对此类集合执行写入操作时，集合会在底层复制一份新的数组，接下来对新的数组执行

写入操作。由于对集合的写入操作都是对数组的副本执行操作，因此它是线程安全的。在所有线程

安全的List中，它是性能最优的方案

谈谈CopyOnWriteArrayList的原理

CopyOnWriteArrayList是Java并发包里提供的并发类，简单来说它就是一个线程安全且读操作无锁的ArrayList。正如其名字一样，在写操作时会复制一份新的List，在新的List上完成写操作，然后再将原引用指向新的List。这样就保证了写操作的线程安全。CopyOnWriteArrayList允许线程并发访问读操作，这个时候是没有加锁限制的，性能较高。而写操作的时候，则首先将容器复制一份，然后在新的副本上执行写操作，这个时候写操作是上锁的。结束之后再将原容器的引用指向新容器。注意，在上锁执行写操作的过程中，如果有需要读操作，会作用在原容器上。因此上锁的写操作不会影响到并发访问的读操作。

优点：读操作性能很高，因为无需任何同步措施，比较适用于读多写少的并发场景。在遍历传统的List时，若中途有别的线程对其进行修改，则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其"读写分离"的思想，遍历和修改操作分别作用在不同的List容器，所 以在使用迭代器进行遍历时候，也就不会抛出ConcurrentModificationException异常了。

缺点：一是内存占用问题，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC。二是无法保证实时性，Vector对于读写操作均加锁同步，可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。

方法3：使用Vector

Vector内部方法主要使用synchronized关键字

3.ArrayList的扩容机制

1.ArrayList以无参构造方法创建ArrayList时，初始化赋值的是一个空数组，当真正对数组进行添加元素操作时，才真正分配容量。

当向ArrayList中添加第一个元素时，数组容量默认扩容为10。

2.当需要扩容时，ArrayList每次扩容都以原来容量的1.5倍进行扩容

3.然后再判断新容量是否大于最小需要容量，如果还是小于最小需要容量，那就把最小需要容量当作数组的新容量

4.如果新的容量已经大于最大容量MAX_ARRAY_SIZE（MAX_ARRAY_SIZE，MAX_ARRAY_SIZE为Integer.MAX_VALUE-8，-8是为了避免oom）,

则会调用hugeCapacity(）方法，返回Integer的最大值。

5.再通过Arrays.copyOf()方法将原数组中的内容放到扩容后的新数组里面。

4.ArrayList遍历删除会出的问题？

ArrayList删除一个元素自然没有问题，删除多个元素时，前面删除了后面的元素向前移动，下标发生了改变。（正序删除）

ArrayList<String> list = new ArrayList<>();
//init测试数据
for (int i = 1; i <= 5; i++) {
    list.add(String.valueOf(i));
}
//foreach遍历删除
for (String str : list) {
    if ("1".equals(str)) {
        list.remove(str);
    }
}
//抛出异常
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
    at java.util.ArrayList$Itr.next(Unknown Source)
    at test.Test.main(Test.java:54)

解决办法：

①Iterator迭代器：

public static void main(String[] args){
    List<String> list = new ArrayList<String>();

    list.add("111");
    list.add("222");
    list.add("222");
    list.add("333");
    list.add("444");
    list.add("333");

    Iterator iterator = list.iterator();
    while (iterator.hasNext()){
        if (iterator.next().equals("222")){
            iterator.remove();
        }
    }
    System.out.println(Arrays.toString(list.toArray()));
}

②for倒序遍历删除：

public static void main(String[] args){
    List<String> list = new ArrayList<String>();

    list.add("111");
    list.add("222");
    list.add("222");
    list.add("333");
    list.add("444");
    list.add("333");
    //for循环反向循环删除
    for (int i = list.size() - 1;i >= 0;i--){
        if (list.get(i).equals("222")){
            list.remove(i);
        }
    }
    System.out.println(Arrays.toString(list.toArray()));
}