具有索引的 List

List是一種Collection，作用是收集物件，並以索引方式保留收集的物件順序，其實作類別之一是java.util.ArrayList，其實作原理大致如 定義與使用泛型 的ArrayList範例。例如可用java.util.ArrayList改寫 java.lang.Object 的Guest類別，而作用相同：

package cc.openhome;

import java.util.*;
import static java.lang.System.out;

public class Guest {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        collectNameTo(names);
        out.println("訪客名單：");
        printUpperCase(names);
    }

    static void collectNameTo(List<String> names) {
        Scanner scanner = new Scanner(System.in);
        String name;
        while(true) {
            out.print("訪客名稱：");
            name = scanner.nextLine();
            if(name.equals("quit")) {
                break;
            }
            names.add(name);
        }
    }

    static void printUpperCase(List<String> names) {
        for(int i = 0; i < names.size(); i++) {
            String name = names.get(i);
            out.println(name.toUpperCase());
        }        
    }
}

你可以查看API文件，可發現List介面定義了add()、remove()、set()等許多依索引操作的方法。java.util.LinkedList也實作了List介面，你可以將上面的範例中ArrayList換為LinkedList，而結果不變，那麼什麼時候該用ArrayList？何時該用LinkedList呢？

ArrayList特性

正如 定義與使用泛型 中自行開發的ArrayList，java.util.ArrayList實作時，內部就是使用陣列來保存收集之物件，也因此考慮是否使用ArrayList，就等於考慮是否要使用到陣列的特性。

陣列在記憶體中會是連續的線性空間，根據索引隨機存取時速度快，如果操作上有這類需求時，像是排序，就可使用ArrayList，可得到較好的速度表現。

陣列在記憶體中會是連續的線性空間，如果需要調整索引順序時，會有較差的表現。例如若在已收集100物件的ArrayList中，使用可指定索引的add()方法，將物件新增到索引0位置，那麼原先索引0的物件必須調整至索引1、索引1的物件必須調整至索引2、索引2的物件必須調整至索引3...依此類推，使用ArrayList作這類的操作並不經濟。

陣列的長度固定也是要考量的問題，在ArrayList內部陣列長度不夠時，會建立新陣列，並將舊陣列的參考指定給新陣列，這也是必需耗費時間與記憶體的操作，為此，ArrayList有個可指定容量（Capacity）的建構式，如果大致知道將收集的物件範圍，事先建立足夠長度的內部陣列，可以節省以上所描述之成本。

LinkedList特性

LinkedList在實作List介面時，採用了鏈結（Link）結構，若你不是很瞭解何謂鏈結，可參考底下的SimpleLinkedList範例：

package cc.openhome;

public class SimpleLinkedList<E> {
    private class Node {
        Node(E elem) {
            this.elem = elem;
        }
        E elem;
        Node next;
    }
    
    private Node first;

    public void add(E elem) {
        Node node = new Node(elem);        
        if(first == null) {
            first = node;
        }
        else {
            append(node);
        }
    }

    private void append(Node node) {
        Node last = first;
        while(last.next != null) {
            last = last.next;
        }
        last.next = node;
    }
    
    public int size() {
        int count = 0;
        Node last = first;
        while(last != null) {
            last = last.next;
            count++;
        }
        return count;
    }
    
    public E get(int index) {
        checkSize(index);
        return findElemOf(index);        
    }

    private void checkSize(int index) throws IndexOutOfBoundsException {
        int size = size();
        if(index >= size) {
            throw new IndexOutOfBoundsException(
                    String.format("Index: %d, Size: %d", index, size));
        }
    }

    private E findElemOf(int index) {
        int count = 0;
        Node last = first;
        while(count < index) {
            last = last.next;
            count++;
        }
        return last.elem;
    }
}

在SimpleLinkedList內部使用Node封裝新增的物件，每次add()新增物件之後，將會形成以下的鏈狀結構：