List接口简介

List接口常用的集合类有ArrayList（数组列表）、LinkedList（链表）、Vector（可变组数）和Stack（栈）。

List集合共有的操作分类

其实List集合说到底也不过是存放数据的容器，因此我们可以类比数据库，将对集合的操作方法分为增、删、改、查四大类。这些方法适用于List的任一个实现类（Stack通过继承Vector间接实现了List接口，但是它应该使用另一套方法，我们会在后文叙述）。

添加：

boolean add(E e) 添加元素成功返回True
void add(int index,E element)在指定位置添加元素（零起）
boolean addAll(Collection<? extends E> c)将自定集合的所有元素添加到此集合中。

ps：参数Collection<? extends E> c所有实现Collection的类。

查询：

E get(int index) 返回指定位置的元素
** int indexOf(Object o)** 找到第一次出现此元素的位置，不存在返回-1
boolean contains(Object o) 此集合包含此元素，则返回True。
boolean containsAll(Collection<?> c) 此集合包含指定集合的所有元素则返回True
boolean isEmpty() 此结合不包含元素（为空）则返回True
int size() 返回集合中的元素数
Object[] toArray() 返回包含所有元素的数组

删除：

void clean() 删除集合中的所有元素
boolean remove(Object o) 根据内容移除指定元素（第一次出现的）
E remove(int index)删除列表中指定位置的元素
boolean removeAll(Collection<?> c)移除指定集合中包含的所有元素
retainAll(Collection<?> c)与上面是正好相反的，保留指定集合中的所有元素（其他移除）

修改：

E set(int index, E element) 用指定元素替代该位置的元素

让我们来简单地实践一下：

import java.util.List;

public class ListTest {
    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        System.out.println("list1:"+list1);
        List<Integer> list2 = new LinkedList<>();
        list2.add(4);
        list2.add(5);
        list1.addAll(list2);
        System.out.println("List1+list2:"+list1);
        list1.add(3,66);
        System.out.println("Insert 66 to 3th:"+list1);
        System.out.println("Get 4th element from list1:"+list1.get(3));
        System.out.println("If list1 contains 77?"+list1.contains(77));
        System.out.println("If list1 contains list2?"+list1.containsAll(list2));
        System.out.println("If list1 is empty?"+list1.isEmpty());
        System.out.println("List1's size?"+list1.size());
        System.out.println("Get 5th element from list1:"+list1.toArray()[5]);
        list1.remove(2);
        System.out.println("Remove 3rd element:"+list1);
        list1.remove(new Integer(5));//[1]
        System.out.println("Remove element '5' from list1:"+list1);
        List<Integer> list3 = new Stack();
        list3.add(1);list3.add(2);
        list1.retainAll(list3);
        System.out.println("Retain list2's element in list1:"+list1);
        list1.set(1,77);
        System.out.println("Set 2nd element of value 77:"+list1);
        list1.clear();
        System.out.println("If list1 is empty?"+list1.isEmpty());
    }
}

输出结果：

list1:[1, 2, 3]
List1+list2:[1, 2, 3, 4, 5]
Insert 66 to 3th:[1, 2, 3, 66, 4, 5]
Get 4th element from list1:66
If list1 contains 77?false
If list1 contains list2?true
If list1 is empty?false
List1's size?6
Get 5th element from list1:5
Remove 3rd element:[1, 2, 66, 4, 5]
Remove element '5' from list1:[1, 2, 66, 4]
Retain list2's element in list1:[1, 2]
Set 2nd element of value 77:[1, 77]
If list1 is empty?true

上边的例子为了打字流畅，选择用了蹩脚的引文来做输出的注释，但是大家应该都看得懂把（→ →）

为了说明LinkedList、LinkList、Stack都实现了List接口，我例子用的list1、list2和list、分别使用了它们向上转型。

值得注意的是例子中标【1】的地方，这个地方使用了Integer类作为参数传入，以防止remove方法判断我传入的是用来表示位置的整型，而在前边的add方法中因为不会混淆，直接使用整型作为参数传入，它会被自动装箱为Integer类型。

使用的方法我们大致了解了，接下来我们看看它们的特性：

ArrayList

ArrayList是基于数组实现的
获取和修改元素get、set都是固定时间运行的，所以时间复杂度都为O(1)
添加和删除元素操作时间复杂度为O(n)，因为ArrayList插入的时候，在插入元素后边的所有元素都要向后移动，因此，插入的位置约靠后，需要的时间就越少，同理，删除
扩容机制：如果一开始不指定其实容量，先是10，而后每次扩充1.5倍
线程不安全，如果需要多个线程访问，可以在使用Collection.synchronizeList方法包装，如：

List list = Collection.synchronizeList(new ArrayList(...))

LinkedList

LinkedList是基于双链表实现的，共三个元素，前后分别为前后一个单位的引用，中间为本单位元素
获取元素较ArrayList慢，因为要沿着索引查找
添加和删除较ArrayList快，因为不涉及内容的移动，只需要沿着索引找到位置就可以快速添加和删除,且不存在容量问题，ArrayList容量满之后要移动整个数组到新的地址
线程不安全，可以和ArrayList使用同样的方法保证线程安全
除了实现List接口的方法之外，还有两个自己的添加元素方法void addFirst(E e)和void addLast(E e)分别为在头和尾添加元素
ps：其实看了源码就会发现，add(E e)的实现就是addLast(E e)的基础上加了 return true;）

Vector

可以看做是线程安全的ArrayList，为了线程安全，各项性能都比ArrayList稍差。

Stack

栈，相信大家很熟悉了，但是它居然也是List接口的实现类，不知道大家怎么想，反正我刚开始知道的时候就很惊讶（看源码才知道是因为它继承了Vector），但是栈不推荐使用List接口的方法（jdk文档里也没写，但是能用），而是有自己的方法对自身操作：

boolean empty()堆栈为空返回true
E peek()返回顶部对象
E pop()返回顶部对象并在栈中删除
E push(E item)将对象推到此堆栈顶部（返回的也是推进去的对象）
int search(Object o)返回对象

Java的List接口下ArrayList、LinkList、Vector和Stack的简要分析