ArrayList和Araay数组区别

​

一、ArrayList和Array数组的区别?

ArrayList 内部基于动态数组实现，比 Array（静态数组） 使用起来更加灵活：

ArrayList会根据实际存储的元素动态地扩容或缩容，而 Array 被创建之后就不能改变它的长度了。

ArrayList 允许你使用泛型来确保类型安全，Array 则不可以。

ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。Array 可以直接存储基本类型数据，也可以存储对象。

ArrayList 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如 add()、remove()等。Array 只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。

ArrayList创建时不需要指定大小，而Array创建时必须指定大小。

下面是二者使用的简单对比：

Array：

 // 初始化一个 String 类型的数组

 String[] stringArr = new String[]{"hello", "world", "!"};

 // 修改数组元素的值

 stringArr[0] = "goodbye";

 System.out.println(Arrays.toString(stringArr));// [goodbye, world, !]

 // 删除数组中的元素，需要手动移动后面的元素

 for (int i = 0; i < stringArr.length - 1; i++) {

     stringArr[i] = stringArr[i + 1];

 }

 stringArr[stringArr.length - 1] = null;

 System.out.println(Arrays.toString(stringArr));// [world, !, null]

ArrayList ：

// 初始化一个 String 类型的 ArrayList

 ArrayList<String> stringList = new ArrayList<>(Arrays.asList("hello", "world", "!"));

// 添加元素到 ArrayList 中

 stringList.add("goodbye");

 System.out.println(stringList);// [hello, world, !, goodbye]

 // 修改 ArrayList 中的元素

 stringList.set(0, "hi");

 System.out.println(stringList);// [hi, world, !, goodbye]

 // 删除 ArrayList 中的元素

 stringList.remove(0);

 System.out.println(stringList); // [world, !, goodbye]

二、ArrayList 插入和删除元素的时间复杂度?

对于插入：

头部插入：由于需要将所有元素都依次向后移动一个位置，因此时间复杂度是 O(n)。

尾部插入：当 ArrayList 的容量未达到极限时，往列表末尾插入元素的时间复杂度是 O(1)，因为它只需要在数组末尾添加一个元素即可；当容量已达到极限并且需要扩容时，则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中，然后再执行 O(1) 的操作添加元素。

指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素，因此时间复杂度为 O(n)。

对于删除：

头部删除：由于需要将所有元素依次向前移动一个位置，因此时间复杂度是 O(n)。

尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O(1)。

指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

三、ArrayList 与 LinkedList 区别?

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

底层数据结构： ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）

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

ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)），时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。

LinkedList 采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、 removeLast()），时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o),remove(int index)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入和删除。

是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList（实现了 RandomAccess 接口） 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

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

我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）自己都说从来不会使用 LinkedList 。

​