List 相关常见知识

ArrayList 和 Array（数组）的区别？

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

• ArrayList 会根据实际存储的元素动态地扩容或缩容，而 Array 被创建之后就不能改变它的长度了。
• ArrayList 允许你使用泛型来确保类型安全，Array 则不可以。
• ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。Array 可以直接存储基本类型数据，也可以存储对象。
• ArrayList 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如 add ()、remove ()等。Array 只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。
• ArrayList 创建时不需要指定大小，而 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]

// 初始化一个 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 与 LinkedList 区别?

• ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
• ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是双向链表数据结构（JDK 1.6 之前为循环链表，JDK 1.7 取消了循环。注意双向链表和双向循环链表的区别）
• 插入和删除是否受元素位置的影响：
  • ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。
  • LinkedList 采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响 $O(1)$，如果是要在指定位置插入和删除元素 $O(n)$
• 是否支持快速随机访问：快速随机访问就是通过元素的序号快速获取元素对象 (对应于 get(int index) 方法)。
  • LinkedList 不支持高效的随机元素访问
  • ArrayList 支持（实现了 RandomAccess 接口） 。
• 内存空间占用：ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

一般不会使用 LinkedList ，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好。

RandomAccess 接口

public interface RandomAccess {
}

实际上 RandomAccess 接口中什么都没有定义。所以 RandomAccess 接口不过是一个标识罢了。 标识实现这个接口的类具有随机访问功能。

在 binarySearch() 方法中，它要判断传入的 list 是否 RandomAccess 的实例，如果是，调用 indexedBinarySearch()方法，如果不是，那么调用 iteratorBinarySearch()方法

双向链表与双向循环链表

ArrayList 插入和删除元素的时间复杂度？

非常好理解，复杂度和想象一样，和数组本质也一样。

插入：

• 头部插入：由于需要将所有元素都依次向后移动一个位置，因此时间复杂度是 O (n)。
• 尾部插入：当 ArrayList 的容量未达到极限时，往列表末尾插入元素的时间复杂度是 O (1)，因为它只需要在数组末尾添加一个元素即可；当容量已达到极限并且需要扩容时，则需要执行一次 O (n) 的操作将原数组复制到新的更大的数组中，然后再执行 O (1) 的操作添加元素。
• 指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素，因此时间复杂度为 O (n)。

删除：

• 头部删除：由于需要将所有元素依次向前移动一个位置，因此时间复杂度是 O (n)。
• 尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O (1)。
• 指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O (n)。

LinkedList 插入和删除元素的时间复杂度？

LinkList 为双向链表，值得注意。

• 头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O (1)。
• 尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O (1)。
• 指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，不过由于有头尾指针，可以从较近的指针出发，因此需要遍历平均 n/4 个元素，时间复杂度为 O (n)。

了解(看看就行，较为简单)：

ArrayList 和 Vector 的区别?（了解即可）

• ArrayList 是 List 的主要实现类，底层使用 Object[]存储，适用于频繁的查找工作，线程不安全。
• Vector 是 List 的古老实现类，底层使用 Object[] 存储，线程安全。

Vector 和 Stack 的区别?（了解即可）

• Vector 和 Stack 两者都是线程安全的，都是使用 synchronized 关键字进行同步处理。
• Stack 继承自 Vector，是一个后进先出的栈，而 Vector 是一个列表。

ArrayList 可以添加 null 值吗？

ArrayList 中可以存储任何类型的对象，包括 null 值。不过，不建议向 ArrayList 中添加 null 值， null 值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。