二、List

相关信息

Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。是list，set等的父接口。

相关信息

Collections 是一个包装类。 它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于Java的Collection框架。

1.ArrayList

对于ArrayList，它的特点是内部采用动态数组实现，这决定了以下几点。

• 可以随机访问，按照索引位置进行访问效率很高，用算法描述中的术语，效率是O(1)，简单说就是可以一步到位。
• 除非数组已排序，否则按照内容查找元素效率比较低，具体是O(N), N为数组内容长度，也就是说，性能与数组长度成正比。
• 添加元素的效率还可以，重新分配和复制数组的开销被平摊了，具体来说，添加N个元素的效率为O(N)。
• 插入和删除元素的效率比较低，因为需要移动元素，具体为O(N)。

2.LinkedList

用法上，LinkedList是一个List，但也实现了Deque接口，可以作为队列、栈和双端队列使用。实现原理上，LinkedList内部是一个双向链表，并维护了长度、头节点和尾节点，这决定了它有如下特点。

• 按需分配空间，不需要预先分配很多空间。
• 不可以随机访问，按照索引位置访问效率比较低，必须从头或尾顺着链接找，效率为O(N/2)。
• 不管列表是否已排序，只要是按照内容查找元素，效率都比较低，必须逐个比较，效率为O(N)。
• 在两端添加、删除元素的效率很高，为O(1)。
• 在中间插入、删除元素，要先定位，效率比较低，为O(N)，但修改本身的效率很高，效率为O(1)。

理解了LinkedList和ArrayList的特点，就能比较容易地进行选择了：

如果列表长度未知，添加、删除操作比较多，尤其经常从两端进行操作，而按照索引位置访问相对比较少，则LinkedList是比较理想的选择。

3.ArrayDeque

ArrayDeque实现了双端队列，内部使用循环数组实现，这决定了它有如下特点。

• 在两端添加、删除元素的效率很高，动态扩展需要的内存分配以及数组复制开销可以被平摊，具体来说，添加N个元素的效率为O(N)。
• 根据元素内容查找和删除的效率比较低，为O(N)。
• 与ArrayList和LinkedList不同，没有索引位置的概念，不能根据索引位置进行操作。

ArrayDeque和LinkedList都实现了Deque接口，应该用哪一个呢？（详见：https://www.youngxy.top/page/Java-SE/七、数据结构.html#java官方推荐的实现方式-deque）

如果只需要Deque接口，从两端进行操作，一般而言，ArrayDeque效率更高一些，应该被优先使用；如果同时需要根据索引位置进行操作，或者经常需要在中间进行插入和删除，则应该选LinkedList。

4.PriorityQueue

PriorityQueue实现了队列接口Queue，但按优先级出队，内部是用堆实现的，有如下特点：

• 实现了优先级队列，最先出队的总是优先级最高的，即排序中的第一个。
• 优先级可以有相同的，内部元素不是完全有序的，如果遍历输出，除了第一个，其他没有特定顺序。
• 查看头部元素的效率很高，为O(1)，入队、出队效率比较高，为O(log2(N))，构建堆heapify的效率为O(N)。
• 根据值查找和删除元素的效率比较低，为O(N)。