3. List

数据结构在Java集合中的对应关系

线性表【数组】 -> ArrayList
线性表【链表】-> LinkedList
队列 -> Queue -> LinkedList，PriorityQueue, ArrayBlockingQueue … etc.
双端队列 -> Deque -> ArrayDeque
栈 -> LinkedList
哈希表 -> HashSet, HashTable, HashMap
跳表 -> ConcurrentSkipListMap
二叉树[red-black tree] -> treeMap, treeSet
哈希表 + 链表 -> LinkedHashMap, LinkedHashSet

List即数据结构中最基本的线性表，有数组和链表两种实现。 它的基本特征： 有序，可重复，除了第一个和最后一个元素，每个元素都只有一个前驱和一个后继。

Java 集合API中使用List接口来抽象化线性表，提供针对集合的CURD操作，相比Collection接口，List可以支持按索引位插入和查找，尤其当实现类是ArrayList时，可实现按下标的随机查找。

List接口方法

在Collection的基础上，新增如下方法：
1）E get(int index)
返回指定索引位上的值，如果底层是数组，可以随机访问，时间复杂度O(1)， 如果是链表，不支持随机访问，时间复杂度是O(n)。

2) E set(int index, E element)
相当于replace, 即更新指定索引位置上的元素

3) void add(int index, E element)
在指定索引位上插入元素，底层是数组时如果该索引位不是size()，则会涉及到移位，此时时间复杂度是O(n), 而底层是链表时，比较简单，时间复杂度时O(1)

4) E remove(int index)
移除指定索引位的值

5) indexOf(Object o)
从前往后查找指定元素的索引位，找不到时为-1， 使用equals判断元素是否相等

6) lastIndexOf(Object o)
从后往前查找指定元素的索引位，找不到时为-1

7) ListIterator listIterator()
返回增强的Iterator，它在基本的iterator基础上，新增了CUD功能，还能向前遍历。

8) List of(E e1, E e2 …)
比较实用的方法，能基于给定的元素生成unmodifiable list