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
采用链表存储,所以在头尾插入或者删除元素不受元素位置的影响,如果是要在指定位置插入和删除元素
- 是否支持快速随机访问:快速随机访问就是通过元素的序号快速获取元素对象 (对应于
get(int index)
方法)。LinkedList
不支持高效的随机元素访问ArrayList
支持(实现了RandomAccess
接口) 。
- 内存空间占用:
ArrayList
的空间浪费主要体现在在list
列表的结尾会预留一定的容量空间,而LinkedList
的空间花费则体现在它的每一个元素都需要消耗比ArrayList
更多的空间(因为要存放直接后继和直接前驱以及数据)。
一般不会使用
LinkedList
,需要用到LinkedList
的场景几乎都可以使用ArrayList
来代替,并且,性能通常会更好。
RandomAccess 接口
Q: LinkedList
为什么不能实现 RandomAccess
接口?
A: RandomAccess
是一个标记接口,用来表明实现该接口的类支持随机访问(即可以通过索引快速访问元素)。由于 LinkedList
底层数据结构是链表,内存地址不连续,只能通过指针来定位,不支持随机快速访问,所以不能实现 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
是一个列表。
随着 Java 并发编程的发展,Vector
和 Stack
已经被淘汰,推荐使用并发集合类(例如 ConcurrentHashMap
、CopyOnWriteArrayList
等)或者手动实现线程安全的方法来提供安全的多线程操作支持。
ArrayList 可以添加 null 值吗?
ArrayList 中可以存储任何类型的对象,包括 null 值。不过,不建议向 ArrayList 中添加 null 值, null 值无意义,会让代码难以维护比如忘记做判空处理就会导致空指针异常。