Java 容器 - 详细剖析 List 之 ArrayList, Vector, LinkedList

Richard_Yi 2019年07月15日 85次浏览

前言

知识点概览:

  • ArrayList 与 LinkedList对比
  • ArrayList 中的 RandomAccess 接口 是什么?
  • LinkedList 中的 Deque 接口 是什么?
  • 老调常谈 之 ArrayList 扩容机制
  • ArrayList 与 Vector 对比

ArrayList 与 LinkedList对比

  1. 底层数据结构:

    • ArrayList 底层使用的Object数组,默认大小 10

    • LinkedList 底层使用的是双向链表数据结构(JDK1.6之前为循环链表,JDK1.7取消了循环。注意双向链表和双向循环链表的区别)。LinkedList 包含了3个重要的成员:sizefirstlastsize是双向链表中节点的个数,firstlast分别指向第一个和最后一个节点的引用。

  2. 插入和删除是否受元素位置的影响:

    • 由于底层实现的影响,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)
  3. 是否支持快速随机访问:这个也是由底层实现决定的,LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

  4. 内存空间占用: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 的方法:

QueueDeque
add(e)addLast()
offer(e)offerLast()
remove()removeFirst()
poll()pollFirst()
element()getFirst()
peek()peekFirst()

如何作为栈使用呢? 下面我们来看看下双端队列作为栈 Stack使用的时候方法对应关系。

StackDeque
push(e)addFist(e)
pop()removeFirst()
peek()peekFirst()

因为篇幅有限,具体实现源码就不带大家去分析了。

引一篇好文:搞懂 Java LinkedList 源码

老调常谈 之 ArrayList 扩容机制

这是一个很频繁的面试点,故记录一下。

以下是源码部分。

  1. add()方法开始入手
  2. ensureCapacityInternal(size + 1) 确认当前数组可否容纳 size + 1 个元素,如果不够进行扩容
  3. 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 读写分离,后面的内容会有详细介绍

参考

  1. 搞懂 Java LinkedList 源码
  2. 《码出高效》
  3. 《疯狂Java讲义》
  4. github cs-note
  5. java guide