集合 · 单选题 · 第 11 题
Java 后端开发面试 · 第 11 题
关于 ArrayList 和 LinkedList,下列说法正确的是?
- AArrayList 随机访问是 O(1);LinkedList 按下标访问要遍历,是 O(n)
- BLinkedList 按下标访问也是 O(1),而且比 ArrayList 的随机访问还要更快
- CArrayList 在头部插入元素是 O(1),不需要移动其他元素
- DLinkedList 是线程安全的,ArrayList 在多线程下才需要加锁
答案
A A. ArrayList 随机访问是 O(1);LinkedList 按下标访问要遍历,是 O(n)
解析
ArrayList 底层是数组,随机访问直接算偏移;头部插入要整体后移元素,是 O(n)。LinkedList 是双向链表,按下标访问要从较近的一端遍历。两者都不是线程安全的。实际使用中,ArrayList 因为内存连续、缓存友好,多数场景性能更好。