集合-1 数组ArrayListLinkedList

一.数组

1.什么是数组？

数组是一种用连续的内存空间存储相同类型数据的线性数据结构。

2.为什么数组下标是从0开始？

（1）数组根据下标查找元素是基于寻址公式：元素地址=数组首地址+索引i*数组存储数据类型的大小

（2）如果下标从0开始，则寻址公式应改为：元素地址=数组首地址+(i-1)*数组存储数据类型的大小；对cpu而言多了一个(i-1)的操作，性能下降。

3.数组查找元素的时间复杂度

（1）已知下标：O(1)

（2）未知下标：O(n)

（3）未知下标但排序：根据二分法查找是O(logn)

（4）插入和删除时，为了保证在内存存储的连续性，需要数组元素，平均时间复杂度为O(n)

二.ArrayList

1.ArrayList的底层实现原理是什么？

（1）ArrayList底层是用动态的数组实现的。

（2）ArrayList创建时，若未指定容量，则初始化数组长度为0；第一次添加数据时才将数组长度扩容为10。

（3）后续的每次扩容，都将数组长度扩容为原来的1.5倍；每次扩容都需要将原数组元素拷贝到新数组。

（4）ArrayList在添加数据时：

        a.计算数组当前已存储容量size，若size+1>length，则调用grow()方法进行扩容(扩容为原来的1.5倍)。

        b.将新添加的数据存储到数组的size位置上，添加成功返回布尔值

2.ArrayList list = new ArrayList(10)；代码中list扩容了几次？

（1）ArrayList有三种构造方法：

        a.ArrayList(int initialCapacity)：带初始化容量的构造函数，将数组的容量初始化为initialCapacity；

        b.ArrayList()：无参构造函数，数组容量初始化为0，第一次添加元素时才扩容为10；

        c.ArrayList(Collection<?extends E> c)：将c转化为ArrayList
（2）代码中是使用了ArrayList的带初始化容量的构造函数，并未进行扩容。

3.如何实现数组和List之间的转换？

（1）数组转List：调用JDK中的工具类Arrays中的asList()方法。

（2）List转数组：调用List类中的toArray()方法。若toArray()方法不传参，则返回一个Object数组；若传入一个已经初始化长度的数组，则将List中的数据存到该数组并返回该数组。

4.通过Arrays.asList()将数组转List后，若修改数组内容，List会受影响吗？

（1）asList()的实现原理是通过Arrays类中的一个内部类ArrayList来将数组包装成一个ArrayList；

（2）asList()方法会将ArrayList中的数组指向传入的数组，再将ArrayList对象返回，以此来实现将数组转化成List。

（3）这个指向是一个引用传递，ArrayList的数组和传入的数组指向同一块地址，因此修改数组内容，List会受影响。

5.ArrayList 和 Arrays类的内部类Arrays.ArrayList的区别

（1）add方法

        a.ArrayList和Arrays.ArrayList都继承了抽象类AbstractList；

        b.AbstractList中的add()方法默认为若子类未重写该方法，则使用时会抛出UnsupportedOperationException异常

        c.ArrayList重写了add()方法，可以有添加元素操作

        d.Arrays.ArrayList未重写add()方法，无法添加元素

******e.由于Arrays.asList()返回的是Arrays.ArrayList对象，因此通过这种方式将数组转成的List是无法添加元素的。

（2）构造参数为数组或集合时

        a.ArrayList只能接收Collection

        b.Arrays.ArrayList能接收数组E[]

6.通过List类的toArray()将List转成数组后，若修改List内容，数组会受影响吗？

不会受影响，toArray()的实现原理是将List中的数组进行拷贝，并返回一个新数组对象。返回的数组与List中的数组不指向同一块地址，因此互不影响。

7.ArrayList和LinkedList的区别是什么？

1.底层数据结构

（1）ArrayList底层是用动态的数组实现的

（2）LinkedList底层是用双向链表实现的

2.操作数据的效率不同

（1）查

        a.已知索引的情况下，ArrayList根据寻址公式查找，效率是O(1)；LnkedList是遍历查找，效率是O(n)。

        b.未知索引的情况下，ArrayList和LinkedList都是遍历查找，效率都是O(n)。

（2）增删

        a.ArrayList进行尾部增删效率是O(1)，其他位置的增删都需要挪动数组，效率是O(n)。

        b.LinkedList进行头尾增删效率是O(1)，其他位置的增删都需要遍历链表，效率是O(n)。

3.内存空间占用

（1）ArrayList底层是数组，在内存中是连续存储的，节省内存空间。

（2）LinkedList底层是双向链表，在内存中是离散存储的，还需额外存储前后两个节点的地址，更占用内存空间

4.线程安全

ArrayList和LinkedList都是线程不安全的，若要保证线程安全，有两种方案：

（1）在方法内定义使用，对于局部变量是线程安全的。

（2）使用Collections.synchronizedList(new ArrayList<>())或Collections.synchronizedList(new LinkedList<>())构建线程安全的List，该方法就是创建加了synchronized锁的List，线程安全但操作性能下降。