List与Set数据结构区别及LinkedList与ArrayList选择指南

在接口里都定义好了，子类不要也得要。

当然子类也会做一些自己的实现，这样就有了不同的数据结构。

那我们一个个来看。

List

List 最大的特点就是：有序，可重复。

看官网说的：

一个有序的集合（也被称作一个序列）。

列表通常允许有重复的元素，而集合则不是这样。

这一下说出了 Set 的特点，它与 List 完全相反。Set 是无序的，并且不重复。

List 的实现方式包含 LinkedList 和 ArrayList 这两种。在面试时，最为常被问到的问题就是这两个数据结构该如何进行选择。

对于这类选择问题：

一是考虑数据结构是否能完成需要的功能；

如果都能完成，二是考虑哪种更高效。

（万事都是如此啊。

具体来看这两个 classes 的 API 以及它们的时间复杂度分别是怎样的：

功能方法ArrayListLinkedList

增

add(E e)

O(1)

O(1)

增

add(int index, E e)

O(n)

O(n)

删

remove(int index)

O(n)

O(n)

删

remove(E e)

O(n)

O(n)

改

set(int index, E e)

O(1)

O(n)

查

get(int index)

O(1)

O(n)

稍微解释几个：

add(E e) 是在尾巴上加元素。ArrayList 可能会出现扩容的情况。但均摊复杂度（amortized time complexity）仍是 O(1) 的。

add(int index, E e)用于在特定位置添加元素。对于 LinkedList 而言，它需要先找到该位置，然后才能添加元素。单纯的“加”这个动作的时间复杂度是 O(1)，然而要找到这个位置的时间复杂度却是 O(n)。（对于此观点，有的人认为是 O(1)，在与面试官交流时需解释清楚，请勿抬杠。）

remove(int index)的作用是移除这个索引位置上的元素，所以

如果 remove 见到的第一个元素是 E e，那么就执行 remove(E e)操作。

那造成时间复杂度的区别的原因是什么呢？

答：

这个特点使得在数组中能够凭借下标以 O(1) 的时间获取到任何位置的数。然而，链表却无法做到这一点，它只能从开头开始逐个进行遍历。

在“改查”这两个功能方面，由于数组具备随机访问的特性，因此 ArrayList 的效率较高。

那「增删」呢？

如果不考虑找到这个元素的时间，

数组由于物理上具有连续性，在进行增删元素操作时，若在尾部进行则较为方便，但若在其他位置进行，就会致使后续元素都需要移动，因此其效率较低；而链表能够便捷地断开与下一个元素的连接，既可直接插入新元素，也可移除旧元素。

但是实际上你得考虑找到元素所花费的时间。并且如果是在尾部进行操作，当数据量较大时，ArrayList 的速度会更快。

所以说：

改查选择 ArrayList；

增删在尾部的选择 ArrayList；

在其他情况下，若时间复杂度相同，就推荐选择 ArrayList。因为它的 overhead 更小，也就是说它在内存使用方面更有效率。

Vector

那我们来聊一下 Vector，它是 List 的最后一个知识点。这就像是一个年龄暴露帖，用过 Vector 的人都是大佬。

Vector 如同 ArrayList 一样，是从 java.util.AbstractList 继承而来的，并且其底层是通过数组来实现的。

但是现在已不再使用了，原因是……它增添了过多的 synchronized 。

任何好处都伴有代价。线程安全会导致效率降低，在某些系统中很容易成为瓶颈。因此，如今大家不再在数据结构层面添加 synchronized，而是将这个任务转交给我们程序员。

面试常问的问题是：Vector 和 ArrayList 有哪些区别？仅仅回答出这一点还不够全面。

来看 stack overflow 上的高票回答：

一是刚才已经说过的线程安全问题；

二是扩容时扩多少的区别。

这个得看看源码：

这是 ArrayList 的扩容实现。这个算术右移操作是将这个数的二进制进行往右移动一位的操作，并且在最左边补上符号位。然而，由于容量不存在负数，所以实际上是补 0 。

右移一位会产生除以 2 的效果，而定义的新容量是原容量的 1.5 倍。

再来看 Vector 的：

通常我们不定义 capacityIncrement ，所以在默认情况下它是扩容两倍。

答出来这两点，就肯定没问题了。

Queue & Deque

Queue 是一种线性数据结构，它的特点是一端进入，另一端出去；Deque 则是两端都可以进行进出操作。

Queue

Java 中的这个 Queue 接口存在一些特点。一般来讲，队列的语义通常是先进先出（FIFO）的。

这里有个例外，即 PriorityQueue ，它也被称作 heap 。它不会按照进入的时间顺序输出，而是依据规定的优先级输出。并且它的操作不是 O(1) 的，其时间复杂度的计算较为复杂，我们之后会单独开一篇来讲解。

Queue 的方法在官网[1]中已总结完毕。它包含两组 API，其基本功能相同，然而：

功能抛异常返回值

增

add(e)

offer(e)

删

remove()

poll()

瞧

element()

peek()

为什么会抛异常呢？

那 add(e) 怎么会抛异常呢？

有些队列会有容量的限制，像 BlockingQueue 就是这样。如果已经达到了它的最大容量，并且不会进行扩容，那么就会抛出异常。然而，如果使用 offer(e) 方法，就会返回 false 。

那怎么选择呢？：

Deque

Deque 两端都可进出，所以有针对 First 端的操作以及针对 Last 端的操作，每端都有两组操作，一组会抛出异常，一组会返回特殊值。

功能抛异常返回值

增

addFirst(e)/ addLast(e)

offerFirst(e)/ offerLast(e)

删

removeFirst()/ removeLast()

pollFirst()/ pollLast()

瞧

getFirst()/ getLast()

peekFirst()/ peekLast()

使用时同理，要用就用同一组。

Queue 的这些 API 是 O(1) 的时间复杂度，确切地说是均摊时间复杂度。Deque 的这些 API 也是 O(1) 的时间复杂度，同样是均摊时间复杂度。

实现类

它们的实现类有这三个：

所以说，

我们一个个来看。

实现普通队列时，要考虑如何选择用 LinkedList 还是 ArrayDeque 呢？

来看一下 StackOverflow[2] 上的高票回答：

总结而言，推荐使用 ArrayDeque，因其效率较高。而 LinkedList 会存在其他额外的开销，比如 overhead 等情况。

LinkedList 的内存占用会随着元素的增加而动态增长。

还是在刚才的同一个问题下，这是我认为总结的最好的：

ArrayDeque 是一种能够进行扩容操作的数组。LinkedList 则是采用链表结构的。

ArrayDeque 不能存储 null 值，然而 LinkedList 能够存储 null 值。

ArrayDeque 在头尾端进行增删操作时效率较高。而 LinkedList 只有在要移除中间某个元素且已找到该元素后进行移除时，才是 O(1) 的操作。

ArrayDeque 在内存使用方面更高效。

所以，若不是必须要存 null 值，那就选择 ArrayDeque 吧！

如果是一位很有经验的面试官问你，在什么情况下你会选择使用 LinkedList 呢？

为了版本兼容的问题，实际工作中我们不得不做一些妥协。。

那最后一个问题，就是关于 Stack 了。

Stack

Stack 在语义方面是一种线性数据结构，其特点是后进先出（LIFO）。

很多高频面试题需要用到栈。例如接水问题，其最优解是用双指针，但用栈是最直观的解法，这是需要了解的。之后若有机会，会专门进行撰写。

那在 Java 中是怎么实现栈的呢？

Java 中有 Stack 这个类。然而，官方文档表明不建议使用它。

原因很简单。Vector 已经被弃用了。Stack 继承了 Vector 。

如果想要实现 Stack 的语义，那就可以使用 ArrayDeque 。

Deque stack = new ArrayDeque<>();

Set

刚才已经讲过，最后一个 Set 具有特定，其特定为无序且不重复。

就和数学里学的「集合」的概念一致。

Set 的常用实现类有三个：

HashSet 利用 Hashmap 的 key 来存储元素。它的主要特点是无序的。其基本操作的时间复杂度都是 O(1)，速度很快。

LinkedHashSet 是一个由 HashSet 和 LinkedList 组成的结构，它的特点在于既具备 O(1)的时间复杂度，又能够保持插入的顺序。

TreeSet 采用红黑树结构。它的特点是能够有序。可以通过自然排序或者自定义比较器来进行排序。其缺点是查询速度不如 HashSet 快。

那每个 Set 的底层实现其实就是对应的 Map：

数值被放置在 map 的 key 上，在 value 上放置了 PRESENT，它是一个静态的 Object，就如同一个占位符，每个 key 都指向这个 object。

具体的实现原理是在 HashMap 那篇文章里讲过的。增删改查这四种操作也是在 HashMap 那篇文章里讲过的。哈希冲突以及 hashCode()/equals()等问题同样是在 HashMap 那篇文章里讲过的。这里就不再详细说明了。

总结

再回到开篇的这张图，有没有清楚了一些呢？

每个数据结构之下都包含着诸多内容。例如，对于 PriorityQueue ，本文并未详细阐述，原因在于一旦提及它，又得花费半天时间。

参考资料

[1]

Queue:

[2]

ArrayDeque vs LinkedList:

- END -

点击卡片进入小程序，签到赢礼品