List 接口

一个List是一个有序Collection。
除了继承自Collection的操作外，List接口还包括一下操作：

• 按位存取——基于元素的数字位置，such as get, set, add, addAll, and remove.

• 查询——搜索指定对象在List中的数值位置index，Search methods include indexOf and lastIndexOf.

• 迭代——利用List的有序特性扩展了Iterator 的含义，The listIterator methods provide this behavior.

• Range-view——sublist 方法值操作任意范围的List。

java平台提供了两种比较通用的List：

• ArrayList通常性能更好。
• LinkedList在特定场景性能更好。

Collection 操作

List继承所有The Collection Interface的操作。

• remove移除第一个指定元素。
• add ，addAll添加元素到最后。

list1.addAll(list2);

List<Type> list3 = new ArrayList<Type>(list1); // ArrayList的标准转换函数
list3.addAll(list2);

聚合操作

List<String> list = people.stream()
.map(Person::getName)
.collect(Collectors.toList());

想Set一样，有equals and hashCode进行逻辑比较，不论实现方式。

按位存取 and 查询

基本按位存取操作，包括get, set, add and remove. set and remove 分别返回修改之前和移除的值。
addAll 按位插入所有元素。

对调算法

public static <E> void swap(List<E> a, int i, int j) {
    E tmp = a.get(i);
    a.set(i, a.get(j));
    a.set(j, tmp);
}

基于对调算法的洗牌算法

import java.util.*;
public static void shuffle(List<?> list, Random rnd) {
    for (int i = list.size(); i > 1; i--)
        swap(list, i - 1, rnd.nextInt(i));
}



public class Shuffle {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        for (String a : args)
            list.add(a);
        Collections.shuffle(list, new Random());
        System.out.println(list);
    }
}
Collections.shuffle(list); // 

ArrayList 的静态方法asList可以将一个Array视为List，但是返回的List并没有add和remove方法，Array是长度不可变的，并不是通常意义上的List实现。
洗牌Array

import java.util.*;

public class Shuffle {
    public static void main(String[] args) {
        List<String> list = Arrays.asList(args);
        Collections.shuffle(list);
        System.out.println(list);
    }
}

迭代器

iterator 方法返回Iterator对象，Iterator对象返回以恰当顺序的元素
ListIterator 继承自 Iterator (hasNext, next, and remove) ， hasPrevious 和 previous 类似于 hasNext 和 next
hasPrevious 是向后移动指针，hasNext是向前指针。
listIterator()没有参数时，以起始位置开始，有int参数时，以指定位置开始。
范围始终是[0，n)的区间。

for (ListIterator<Type> it = list.listIterator(list.size()); it.hasPrevious(); ) {
    Type t = it.previous();
    ...
}

调用 next 和 previous，相当于往前移动后往后移，会形成死循环。

边界情况，previousIndex 会返回-1于初始值之前，nextIndex会返回list.size()于最后一个元素之后。

如下是一种可能的List.indexOf实现：

public int indexOf(E e) {
    for (ListIterator<E> it = listIterator(); it.hasNext(); )
        if (e == null ? it.next() == null : e.equals(it.next()))
            return it.previousIndex();
    // Element not found
    return -1;
}

Iterator 接口的remove方法移除 Collection的next方法返回的元素。
ListIterator接口则是next or previous返回的元素。
ListIterator接口额外提供了set和add方法，set方法会覆盖next or previous返回的元素，add方法会在当前光标前插入元素。

public static <E> void replace(List<E> list, E val, E newVal) {
    for (ListIterator<E> it = list.listIterator(); it.hasNext(); )
       // trick 处理当为null时的NullPointerException
        if (val == null ? it.next() == null : val.equals(it.next())) 
            it.set(newVal);
}
public static <E> 
    void replace(List<E> list, E val, List<? extends E> newVals) {
    for (ListIterator<E> it = list.listIterator(); it.hasNext(); ){
       // trick 处理当为null时的NullPointerException
        if (val == null ? it.next() == null : val.equals(it.next())) {
            it.remove();
            for (E e : newVals)
                it.add(e);
        }
    }
}

Range-View 操作

subList(int fromIndex, int toIndex)返回list的[formIndex, toIndex)部分的list。半开半闭范围类似于for循环。
如view这个术语所示，List调用sublist返回的list由List备份，因此对list的修改会同步到List中。
任何需要List的操作都可以通过subList而不是整个List来作为范围操作，比如删除List的一部分：

list.subList(fromIndex, toIndex).clear();

比如，发牌：

public static <E> List<E> dealHand(List<E> deck, int n) {
    int deckSize = deck.size();
    List<E> handView = deck.subList(deckSize - n, deckSize);
    List<E> hand = new ArrayList<E>(handView);
    handView.clear();
    return hand;
}

对于大部分List的实现，比如ArrayList，从最后删除元素的性能大体上优于从最前删除。
对原List的增删操作，会导致sublist的list变成undefined，因此推荐将sublist产生的list仅作为过渡对象。

Collections 的大多数算法都适用于List。

sort — sorts a List using a merge sort algorithm, which provides a fast, stable sort. (A stable sort is one that does not reorder equal elements.)
shuffle — randomly permutes the elements in a List.
reverse — reverses the order of the elements in a List.
rotate — rotates all the elements in a List by a specified distance.
swap — swaps the elements at specified positions in a List.
replaceAll — replaces all occurrences of one specified value with another.
fill — overwrites every element in a List with the specified value.
copy — copies the source List into the destination List(source List's length < destination List's length).
binarySearch — searches for an element in an ordered List using the binary search algorithm.
indexOfSubList — returns the index of the first sublist of one List that is equal to another.
lastIndexOfSubList — returns the index of the last sublist of one List that is equal to another.