转载

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

前言

学习情况记录

  • 时间:week 2
  • SMART子目标 :Java 容器

记录在学习Java容器 知识点中,关于 List 的需要重点记录的知识点。

知识点概览:

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

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

ArrayList 与 LinkedList对比

  1. 底层数据结构:

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

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

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

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

  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 接口 是什么?

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

前面的图中我们可以看到ArrayList 继承了三个接口,后面两个都是比较熟悉的,分别是标识对象可复制和可序列化。

那么 RandomAccess 接口代表什么呢?

前面的关于ArrayList 与 LinkedList 的对比当中,有一点就是,

是否支持快速随机访问 :这个也是由底层实现决定的,LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。 快速随机访问就是通过元素的序号快速获取元素对象 (对应于 get(int index) 方法)。

RandomAccess 接口 就是用来 标识该类支持快速随机访问。 查看源码可以发现,这个接口内部没有任何的定义。仅仅是起标识作用。

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

比如在 Collections.binarySearch() 方法中,

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

实现了RandomAccess接口的List使用索引遍历,而未实现RandomAccess接口的List使用迭代器遍历。

总结一句话:实现RandomAccess接口的List可以通过for循环来遍历数据比使用iterator遍历数据更高效,未实现RandomAccess接口的List可以通过iterator遍历数据比使用for循环来遍历数据更高效。当然对于ArrayList来说,for循环遍历和Iterator方式遍历差距不大,但是对于LinkedList这种没有实现的来说,两种遍历方式效率差距就有点大了。这主要是因为底层实现不同。

LinkedList 中的 Deque 接口是什么?

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

与 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 扩容机制

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

以下是源码部分。

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

  1. add() 方法开始入手
  2. ensureCapacityInternal(size + 1) 确认当前数组可否容纳 size + 1 个元素,如果不够进行扩容
  3. grow(minCapacity) 这就是具体扩容的逻辑

    • 新容量的大小为 oldCapacity + (oldCapacity >> 1) ,也就是旧容量的 1.5
    • 扩容操作 需要 调用 Arrays.copyOf() 这个方法,把原数组整个复制到新数组中, 这个操作代价很高,所以 很多地方包括阿里开发手册上也会建议 在集合初始化的时候就指定好大概的容量大小,减少扩容的次数

ArrayList 与 Vector 对比

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

ArrayList 与 Vector 的底层实现都是 Object 数组,所以两者使用和特性上非常类似。

不同的是,

  • Vector 是线程安全的,内部使用了synchronized 进行同步。这导致了 Vector 性能非常不好。相比较的话,推荐用ArrayList,然后自己控制同步。
  • Vector 每次扩容都是2 倍大小,而不是1.5

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

如果是想要达到线程安全的目的,Vector 有其他的替代方案:

  • 使用 Collections.synchronizedList() 得到一个线程安全的ArrayList(这类的Collections.synchronized * () 就是一层Wrapper,看源码就知道了)
  • 也可以使用J.U.C中的 CopyOnWriteArrayList 读写分离,后面的内容会有详细介绍

参考

  1. 搞懂 Java LinkedList 源码
  2. 《码出高效》
  3. 《疯狂Java讲义》
  4. github cs-note
  5. java guide
原文  https://segmentfault.com/a/1190000019762419
正文到此结束
Loading...