8.5.4 各种线性表的性能分析

发表于 2019-07-08 更新于 2020-03-07 分类于 1 疯狂Java讲义 (第4版) ，第8章 Java集合， 8.5 Queue集合 Waline：本文字数： 841 阅读时长 ≈ 1 分钟

线性表

Java提供的List就是一个线性表接口,而ArrayList、 LinkedList又是线性表的两种典型实现:基于数组的线性表和基于链表的线性表。

Queue代表了队列。

Deque代表了双端队列(既可作为队列使用,也可作为栈使用),接下来对各种实现类的性能进行分析。

初学者可以无须理会ArrayList和LinkedList之间的性能差异,只需要知道LinkedList集合不仅提供了List的功能,还提供了双端队列* 、*栈的功能**就行。但对于一个成熟的Java程序员,在一些性能非常敏感的地方,可能需要慎重选择哪个List实现。

一般来说,由于数组以一块连续内存区来保存所有的数组元素,所以数组在随机访问时性能最好,所有的内部以数组作为底层实现的集合在随机访问时性能都比较好;

内部以链表作为底层实现的集合在执行插入、删除操作时有较好的性能。

但总体来说, ArrayList的性能比LinkedList的性能要好,因此大部分时候都应该考虑使用ArrayList.

对于ArrayList、 Vector集合,应该使用随机访问方法(也就是get())来遍历集合元素,这样性能更好;

对于LinkedList集合,则应该采用迭代器(Iterator)来遍历集合元素.

如果需要经常执行插入、删除操作来改变包含大量数据的List集合的大小,可考虑使用LinkedList集合。
使用ArrayList、 Vector集合可能需要经常重新分配内部数组的大小,效果可能较差。

如果有多个线程需要同时访问List集合中的元素,开发者可考虑使用Collections将集合包装成线程安全的集合。