认识Java Collections (四)

List Interface
除了从Collections继承的标准方法外，List处于以下目的定义了自己的方法：
位置访问  通过元素所在位置访问元素
搜索      搜索List中的特定元素 并返回位置
迭代      提供更加丰富的迭代器
Range-view(范围视图)  对给定List实施范围操作。

List的接口定义如下：

public interface List<E> extends Collection<E> {
    // Positional access
    E get(int index);
    E set(int index, E element);    //optional
    boolean add(E element);         //optional
    void add(int index, E element); //optional
    E remove(int index);            //optional
    boolean addAll(int index,
        Collection<? extends E> c); //optional

    // Search
    int indexOf(Object o);
    int lastIndexOf(Object o);

    // Iteration
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);

    // Range-view
    List<E> subList(int from, int to);
}

 
Java 平台包括两种通用的List实现, ArrayList 和 LinkedList。一般来说 ArrayList性能更好些，但在某些特殊情景下，LinkedList也有优势。

2. Collection Operations
与Collection的集合操作行为一致，不再过多描述。

3.位置访问和搜索操作
以下是交换给定List两个元素的算法：

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);
}

这个算法是多态的，因为它可以交换任意给定类型的List的两个元素。下面是使用以上算法的另一个算法：

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

上面这个算法已被包括在Java平台Collection的实现中，这个算法很巧妙：它从头开始遍历List，并且重复的为每一个元素寻找一个新位置进行替换，最终进行list.size()-1次替换。并且，这会保证List元素的每一个全排列都有等概率出现的可能。
下面这个程序将把它参数列表中的元素随机打印出来：

import java.util.*;

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);
    }
}

实际上，这个程序可以更短更快，这要依赖于Array类的静态工厂方法 asList()，这个方法调用会返回一个List，而这个List并不是一般的List实现，因为它没有实现add和remove方法：因为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);
    }
}

4.Iterator 迭代器
List提供了功能更丰富的迭代器，ListIterator，它允许我们在遍历List时可以通过任意次序(正序、倒序)对List进行操作。接口的声明如下：

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove(); //optional
    void set(E e); //optional
    void add(E e); //optional
}

hasPrevious 等方法，实际上是利用List的index访问特性仿照hasNext的一种实现。下面是一个倒序遍历List的实现：

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

注意ListIterator方法的参数，不带参数的方法调用与ListIterator（0）是一样的。ListIterator方法从给定的索引位置给出Iterator对象。给定的索引位置，即是第一次调用next方法时返回的元素的位置。直观的说，迭代器开始的位置位于两个元素之间，如下图的黄箭头所示：

所以，参数的合法取值范围是0-n，共计n+1个可取值。

对于next和previous的调用是可以混合使用的。当然，你要非常的小心。在进行以此next调用后再次执行previous操作，将返回同一个元素，反之亦然。稍有不慎，极可能出现一个死循环，下面就是这样的一个例子。

ArrayList<Integer> a = new ArrayList<Integer>();
a.add(1);
a.add(2);
a.add(3);
ListIterator<Integer> it = a.listIterator(2);
for(;it.hasPrevious();){
	System.out.println(it.previous());
	System.out.println(it.next());
}

这段代码将会一直输出2 。这是由于next方法已经内在的将访问指针进行了改变，即已经指向了下一个即将访问的位置。而previous又将指针指向了刚刚访问过的位置。

5. Range-View 操作
subList(fromIndex,toIndex)将返回一个子List，从List中进行截取。应当注意，返回的List其实是原List的一个浅拷贝，就是说，对原List的更改将直接反映到新List上，反之亦然。
下面的代码将移除List中某个范围区间内的所有元素

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

注意下面的代码，返回的index值是位于subList中的位置：

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

下面的这段代码将模仿人们玩扑克时，手中抓到的牌，并将被拿走的牌从整套牌中删除：

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;
}

下面就是扑克游戏发牌的模拟程序，该程序需要2个参数。1.玩家数 2.每位玩家可得到的牌数

import java.util.*;

class Deal {
    public static void main(String[] args) {
        int numHands = Integer.parseInt(args[0]);
        int cardsPerHand = Integer.parseInt(args[1]);

        // Make a normal 52-card deck.
        String[] suit = new String[]
            {"spades", "hearts", "diamonds", "clubs"};
        String[] rank = new String[]
            {"ace","2","3","4","5","6","7","8",
             "9","10","jack","queen","king"};
        List<String> deck = new ArrayList<String>();
        for (int i = 0; i < suit.length; i++)
            for (int j = 0; j < rank.length; j++)
                deck.add(rank[j] + " of " + suit[i]);

        Collections.shuffle(deck);

        for (int i=0; i < numHands; i++)
            System.out.println(dealHand(deck, cardsPerHand));
    }
}

运行结果如下：
java Deal 4 5

[8 of hearts, jack of spades, 3 of spades, 4 of spades,
    king of diamonds]
[4 of diamonds, ace of clubs, 6 of clubs, jack of hearts,
    queen of hearts]
[7 of spades, 5 of spades, 2 of diamonds, queen of diamonds,
    9 of clubs]
[8 of spades, 6 of diamonds, ace of spades, 3 of hearts,
    ace of hearts]

(to be continued....)