java 有序列表_Java 中的 List —— 有序序列

List 在 java 中是个有序序列：

一、容量

ArrayList 中有一个容量概念，表示基础数组的大小(无参时默认为 10)。在需要的时候(比如 add操作)会自动增加其容量。LinkedList 没有这个概念。

TreeMap 也有容量，默认是 16.

二、改善的 search 方法

LinkedList 与 ArrayList 都很低效O(N)。比如 Collection 的 contain 和 remove 方法而言。他们均花费线性时间。下面对存、取、查找这三类情况进行比较：

访问数组中第 n 个数据的时间花费是 O(1) (类似地  HashMap 中通过 key 访问 value，但其存取都是 O(1) ，因为其索引是无序的，而数组是有序的索引)，但是要在数组中查找一个指定的数据则是 O(N) 。当向数组中插入或者删除数据的时候，最好的情况是在数组的末尾进行操作，时间复杂度是 O(1) ，但是最坏情况是插入或者删除第一个数据，时间复杂度是 O(N) 。 在数组的任意位置插入或者删除数据的时候，后面的数据全部需要移动，移动的数据还是和数据个数有关所以总体的时间复杂度仍然是 O(N) 。

在链表中查找第 n 个数据以及查找指定的数据的时间复杂度是 O(N) ，但是链表插入和删除数据的时间复杂度是 O(1) ，因为只需要调整指针就可以。

堆栈实现了一种后进先出的语义 (LIFO) ，可以使用数组或者是链表来实现它。队列实现了先入先出的语义 (FIFO) 。队列也可以使用数组和链表来实现

提高运行效率 O(logn)，可以使用 Collections.binarySearch(List list)，二分法进行查找，需要对原集合/数组进行排序(双枢纽快速排序