16.5 List接口

16.5.1 List接口的特点

实现List接口的集合类中的元素是有序的，且允许重复。
List集合中的元素都对应一个整数型的序号记载其在集合中的位置(每个元素都有索引)，可以根据序号存取集合中的元素。
List集合不仅支持Iterator还支持List集合专用迭代器ListIterator(双向迭代器)
List接口比Collection接口中新增的几个实用方法：
1. public E get(int index)；返回列表中的指定位置的的元素
2. public void add(int index, E element);　在列表的指定位置插入指定元素。将当前处于该位置的元素（如果有的话）和所有后续元素向右移动。
3. public E set(int index, E element) ;　用指定元素替换列表中指定位置的元素，并返回被替换的元素
4. public E remove(int index) 移除列表中指定位置的元素，并返回被移除的元素
5. public ListIterator listIterator() 返回此列表元素的列表迭代器(List专有)
注意：list集合中的元素的索引与数组中元素的索引一样，均是从0开始。

16.5.2 List接口的实现类

16.5.2.1 ArrayList 实现类，实现原理

ArrayList是使用数组结构实现的List集合

ArrayList<Student> list1 = new ArrayList<>();
ArrayList<Student> list2 = new ArrayList<>(8);//指定列表个数，内部数组默认初始化为10的长度，若大于10则会动态扩容（跟踪源码）

优点：

对于使用索引取出元素有较好的效率【随机读取效率非常高】
可以使用索引来快速定位对象

缺点：

删除和添加效率较低

16.5.2.2 LinkedList实现类，实现原理

LinkedList是List的实现类，他是一个基于链表实现的List类，对于顺序访问集合中的元素进行了优化。特别是插入，删除元素的速度特别快。LinkedList即实现了List接口，也实现了Deque接口。因此可以作为栈来使用。

Deque接口是Queue接口的子接口，它代表一个双端队列。因此可以从两端来操作队列的元素。

优点：

删除和添加效率较高

缺点：

随机读取效率较低

LinkedList新增了以下方法：

public void addFirst(E e);向集合头部添加数据
public void addLast(E e);向集合尾部添加数据
public E removeFirst();删除链表第一个数据，并返回被删除的数据
public E removeLast();删除链表的最后一个数据，并返回被删除的数据

对比ArrayList与LinkedList的效率：代码示例：

    public static void main(String[] args) {

        LinkedList<String> linkedList = new LinkedList<String>();
        ArrayList<String> arrayList = new ArrayList<String>();


        long l1 = System.currentTimeMillis();
        for (int i = 0; i < 99999; i++) {
            linkedList.add("张三" + i);
        }
        long l2 = System.currentTimeMillis();
        System.out.println("LinkedList 添加时间：" + (l2 - l1));


        l2 = System.currentTimeMillis();
        for (int i = 0; i < 99999; i++) {
            arrayList.add("张三" + i);
        }
        long l3 = System.currentTimeMillis();
        System.out.println("ArrayList 添加时间：" + (l3 - l2));

        l3 = System.currentTimeMillis();
        for (int i = 0; i < arrayList.size(); i++) {
            arrayList.get(i);
        }
        long l4 = System.currentTimeMillis();
        System.out.println("ArrayList 遍历时间：" + (l4 - l3));

        l4 = System.currentTimeMillis();
        for (int i = 0; i < linkedList.size(); i++) {
            linkedList.get(i);
        }
        long l5 = System.currentTimeMillis();
        System.out.println("linkedList 遍历时间：" + (l5 - l4));

        l5 = System.currentTimeMillis();
        while (linkedList.size() > 0) {
            linkedList.removeFirst();
        }
        long l6 = System.currentTimeMillis();
        System.out.println("linkedList 删除时间：" + (l6 - l5));


        l6 = System.currentTimeMillis();
        while (arrayList.size() > 0) {
            arrayList.remove(0);
        }
        long l7 = System.currentTimeMillis();
        System.out.println("arrayList 删除时间：" + (l7 - l6));

    }

效果：

16.5.1.3 Vector（了解）

在List 接口中还有一个子类：Vector。Vector类从整个 Java 的集合发展历史来看，Vector算是一个元老级的类，在 JDK1.0 的时候就已经存在此类。但是到了Java2(JDK1.2)之后重点强调了集合框架的概念，所以先后定义了很多的新接口(如：List 等)。但是考虑到一大部分的人已经习惯了使用 Vector类，因此设计者就让 Vector 类多实现了一个 List接口，这样才将其保留下来。但是因为其是 List 接口的子类，所以 Vector 类的使用与之前的并没有太大的区别。但是Vector内部有一些比较老的方法名比较长的方法。

Vector和ArrayList在使用上非常相似，都可用来表示一组数量可变的对象应用的集合，并且可以随机地访问其中的元素。

Vector的方法都是同步的(Synchronized),是线程安全的(thread-safe)，而ArrayList的方法不是，由于线程的同步必然要影响性能，因此，ArrayList的性能比Vector好。
当Vector或ArrayList中的元素超过它的初始大小时，Vector会将它的容量翻倍，而ArrayList只增加50%的大小，这样，ArrayList就有利于节约内存空间。

开发中使用到比较少！作为了解。

16.5.2.4 Stack（了解）

Stack类表示后进先出（LIFO）的对象堆栈。它通过五个操作对类Vector进行了扩展，允许将向量视为堆栈。

push 将数据对象压入栈顶
pop 取出堆栈顶部的值(会删除顶部的值)
peek 返回堆栈顶部的值
empty 测试堆栈是否为空
search 检测一个元素在堆栈中的位置

首次创建堆栈时，它不包含项。即：空栈！

开发中使用到相对较少！作为了解。

笔记：当一个列表类去实现了RandomAccess这个接口，做遍历的时候最好不要用foreach。

作业笔记：
     //比较中文的大小
     Collator c= Collator.getInstance();
     //如果result<0,则source < target.反之亦然。
     int result = c.compare(String source,String target);

四、List接口