Java核心技术面试精讲 - 对比Vector、ArrayList、LinkedList有何区别？ - 《☕ Java》

典型回答
考点分析
知识扩展

典型回答

这三者都是实现集合框架中的List，也就是所谓的有序集合，因此功能相似，定位，添加，删除，遍历等。但因为具体的设计区别，在行为，性能，线程安全等方面，表现又有很大不同。

Vector 是 Java 早期提供的线程安全的动态数组

ArrayList 是应用更加广泛的动态数组实现，它本身不是线程安全的

LinkedList 是双向链表，不需要调整容量，非线程安全

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

考点分析

Vector 和 ArrayList 作为动态数组，内部元素以数组形式顺序存储，非常适合随机访问，除了尾部插入和删除元素，其它操作性能会相对较差。
而LinkedList进行节点插入、删除却高效的多，但是随机访问性能则要比动态数组慢
数据结构与算法，性能与并发
掌握典型排序算法，内部排序，归并，交换，选择，插入等；外部排序，掌握利用内存和外部存储处理超大数据集

知识扩展

对比Vector、ArrayList、LinkedList有何区别？ - 图1

List，有序集合，提供了方便的访问、插入、删除等操作
Set，Set不允许元素重复，不存在两个对象equals返回true，保证唯一性
Queue/Deque，则是Java提供的标准队列结构的实现

TreeSet默认利用TreeMap实现，HashSet其实也是以HashMap为基础实现的，Map的马甲

TreeSet 支持自然顺序访问，但是添加、删除、包含等操作相对低效（log(n)）
HashSet 利用哈希算法，理想情况下，如果哈希散列正常，可以提供常数时间的添加、删除、包含等操作，但是它不保证有序
LinkedHashSet，内部构建了一个记录插入顺序的双向链表，因此提供了按照插入顺序遍历的能力，与此同时，也保证了常数时间的添加，删除，包含等操作，这些操作性能略低于HashSet，因为需要维护链表的开销
在遍历元素时，HashSet性能受自身容量影响，所以初始化时，除非有必要，否则不要将其背后的HashMap容量设置过大。而对于LinkedHashSet，由于其内部链表提供的方便，遍历性能只和元素多少有关系。

:::warning Q: 如何进行容器的性能测试呢？ :::

这些集合类都不是线程安全的，但是可以通过 Collections 工具类的 synchronized 实现线程安全：

List list = Collections.synchronizedList(new ArrayList());

扩展学习 Collections 集合工具类提供的静态方法
ArrayList 源码实现

Java 提供的默认排序算法：

对于原始数据类型，目前使用的是所谓双轴快速排序（Dual-Pivot QuickSort），是一种改进的快速排序算法
对于对象数据类型，目前是则是使用TimSort，思想上也是一种归并和二分插入排序结合的优化排序算法

Java 8 改进：
支持Lambda和Stream，函数式代码；
Java 8 在语言层面的新特性，允许接口实现默认方法；

Java 9 改进：
Java标准类库提供了一系列的静态工厂方法，比如，List.of() Set.of()，代码简洁，同时是不可变的。

List<String> simpleList = List.of("Hello","world");