共计 2789 个字符,预计需要花费 7 分钟才能阅读完成。
前言
学习情况记录
- 时间:week 2
- SMART 子目标:Java 容器
记录在学习 Java 容器 知识点中,关于 List
的需要重点记录的知识点。
知识点概览:
- ArrayList 与 LinkedList 对比
- ArrayList 中的 RandomAccess 接口 是什么?
- LinkedList 中的 Deque 接口 是什么?
- 老调常谈 之 ArrayList 扩容机制
- ArrayList 与 Vector 对比
ArrayList 与 LinkedList 对比
底层数据结构:
- ArrayList 底层使用的 Object 数组,默认大小
10
。**
- LinkedList 底层使用的是双向链表数据结构(JDK1.6 之前为循环链表,JDK1.7 取消了循环。注意双向链表和双向循环链表的区别)。LinkedList 包含了 3 个重要的成员:
size
、first
、last
。size
是双向链表中节点的个数,first
和last
分别指向第一个和最后一个节点的引用。
- ArrayList 底层使用的 Object 数组,默认大小
插入和删除是否受元素位置的影响:
- 由于底层实现的影响,ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。比如:执行
add(E e)
方法的时候,ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element)
)时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位 / 向前移一位的操作。实际就是 近似 O(n)。 - 而 LinkedList 采用链表存储,所以插入,删除元素时间复杂度不受元素位置的影响,都是近似 O(1)
- 由于底层实现的影响,ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。比如:执行
- 是否支持快速随机访问 :这个也是由底层实现决定的,LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。 快速随机访问就是通过元素的序号快速获取元素对象 (对应于
get(int index)
方法)。 - 内存空间占用:ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放 prev 指针和 next 指针以及数据)。
ArrayList 中的 RandomAccess 接口 是什么?
前面的图中我们可以看到 ArrayList 继承了三个接口,后面两个都是比较熟悉的,分别是标识对象可复制和可序列化。
那么RandomAccess
接口代表什么呢?
前面的关于 ArrayList 与 LinkedList 的对比当中,有一点就是,
是否支持快速随机访问 :这个也是由底层实现决定的,LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。 快速随机访问就是通过元素的序号快速获取元素对象 (对应于
get(int index)
方法)。
而RandomAccess
接口 就是用来 标识该类支持快速随机访问。查看源码可以发现,这个接口内部没有任何的定义。仅仅是起标识作用。
比如在 Collections.binarySearch()
方法中,
实现了 RandomAccess 接口的 List 使用索引遍历,而未实现 RandomAccess 接口的 List 使用迭代器遍历。
总结一句话:实现 RandomAccess 接口的 List 可以通过 for 循环来遍历数据比使用 iterator 遍历数据更高效,未实现 RandomAccess 接口的 List 可以通过 iterator 遍历数据比使用 for 循环来遍历数据更高效。当然对于 ArrayList 来说,for 循环遍历和 Iterator 方式遍历差距不大,但是对于 LinkedList 这种没有实现的来说,两种遍历方式效率差距就有点大了。这主要是因为底层实现不同。
LinkedList 中的 Deque 接口是什么?
与 ArrayList 相对应的,LinkedList 中也有一个值得好好研究的接口,那就是Deque
接口。
Deque - double-ended queue
,中文名为双端队列。
我们都知道 Queue
是一个队列,遵循 FIFO 准则,我们也知道 Stack
是一个栈结构,遵循 FILO 准则。而 Deque
这个双端队列就厉害了, 它既可以实现栈的操作,也可以实现队列的操作,换句话说,实现了这个接口的类, 既可以作为栈使用也可以作为队列使用。
如何作为队列使用呢?Deque
实现了 Queue
,所以 Queue
所有的方法 Deque
都有,下面比较的是 Deque
区别 Queue
的方法:
Queue | Deque |
---|---|
add(e) | addLast() |
offer(e) | offerLast() |
remove() | removeFirst() |
poll() | pollFirst() |
element() | getFirst() |
peek() | peekFirst() |
如何作为栈使用呢?下面我们来看看下双端队列作为栈 Stack
使用的时候方法对应关系。
Stack | Deque |
---|---|
push(e) | addFist(e) |
pop() | removeFirst() |
peek() | peekFirst() |
因为篇幅有限,具体实现源码就不带大家去分析了。
引一篇好文:搞懂 Java LinkedList 源码
老调常谈 之 ArrayList 扩容机制
这是一个很频繁的面试点,故记录一下。
以下是源码部分。
- 从
add()
方法开始入手 ensureCapacityInternal(size + 1)
确认当前数组可否容纳size + 1
个元素,如果不够进行扩容grow(minCapacity)
这就是具体扩容的逻辑- 新容量的大小为
oldCapacity + (oldCapacity >> 1)
,也就是旧容量的1.5
倍 - 扩容操作 需要 调用
Arrays.copyOf()
这个方法,把原数组整个复制到新数组中,这个操作代价很高,所以 很多地方包括阿里开发手册上也会建议 在集合初始化的时候就指定好大概的容量大小,减少扩容的次数。
- 新容量的大小为
ArrayList 与 Vector 对比
ArrayList 与 Vector 的底层实现都是 Object 数组,所以两者使用和特性上非常类似。
不同的是,
- Vector 是线程安全的,内部使用了 synchronized 进行同步。这导致了 Vector 性能非常不好。相比较的话,推荐用 ArrayList,然后自己控制同步。
- Vector 每次扩容都是 2 倍大小,而不是 1.5
如果是想要达到线程安全的目的,Vector 有其他的替代方案:
- 使用
Collections.synchronizedList()
得到一个线程安全的 ArrayList(这类的 Collections.synchronized*() 就是一层 Wrapper,看源码就知道了) - 也可以使用 J.U.C 中的 CopyOnWriteArrayList 读写分离,后面的内容会有详细介绍
参考
- 搞懂 Java LinkedList 源码
- 《码出高效》
- 《疯狂 Java 讲义》
- github cs-note
- java guide