[Java] 程式設計教學：使用 LinkedList 物件

前言

LinkedList 是 Java 串列 (List) 的另一個實作，其內部為鍵結串列 (linked list)。

LinkedList 和 ArrayList 在 API 有許多重疊之處，但兩者實作相異。主要的選擇考量是演算法上的效率。

建立 LinkedList 物件

在預設情形下，Java 不會自動引入 LinkedList。要使用該容器的話，請引入以下物件：

import java.util.LinkedList;
import java.util.List;

一般情形下，List 的公開方法就夠了。故使用以下敘述來建立 LinkedList 物件：

List<Integer> lst = new LinkedList<Integer>();

若需要 LinkedList 特有的公開方法，則改用以下敘述來建立 LinkedList 物件：

LinkedList<Integer> lst = new LinkedList<Integer>();

由於 Java 泛型不支援基礎型態，以下敘述是錯的：

/* WRONG CODE. */
List<int> lst = new LinkedList<int>();

存取 LinkedList 物件的元素

由於 Java 不支援運算子重載 (operator overloading)，LinkedList 無法用 [...] 存取元素。替代的方式是使用 get() 函式取得元素、使用 add(E) 函式新增元素。參考以下範例程式：

import java.util.LinkedList;
import java.util.List;

public class MainProgram
{
    public static void main (String[] args)
    {
        /* Create a LinkedList object. */
        List<Integer> lst = new LinkedList<Integer>();

        /* Some integer data. */
        int data[] = {1, 2, 3, 4, 5};

        for (int n : data) {
            /* Append an element to
                the rear of the list. */
            lst.add(n);
        }

        /* Retrieve an element from the list. */
        assertCond(5 == lst.get(4));
    }

    /* Home-made assert. */
    public static void assertCond (boolean cond)
    {
        if (!cond)
            throw new IllegalArgumentException("Wrong condition");
    }
}

若要在特定位置新增元素，則改用 add(i, E) 函式。參考以下程式碼片段：

for (int i = 0; i < data.length; ++i) {
    /* Add an element to a specific location
        of the list. */
    lst.add(i, data[i]);
}

注意此處的 i 的範圍為 0 到 LinkedList 的寬度 (不包含)。超過這個範圍的話，會拋出 IndexOutOfBoundsException 例外。

由於 set() 函式不會新增元素，故以下程式碼片段是錯的：

for (int i = 0; i < data.length; ++i) {
    /* WRONG CODE. */
    lst.set(i, data[i]);
}

檢查特定元素是否存在

使用 contains() 函式檢查特定元素是否存在。參考以下範例程式：

import java.util.LinkedList;
import java.util.List;

public class MainProgram
{
    public static void main (String[] args)
    {
        List<Integer> lst = new LinkedList<Integer>();

        int data[] = {1, 2, 3, 4, 5};

        for (int n : data)
            lst.add(n);

        /* Check whether an element exists. */
        assertCond(lst.contains(5));
    }

    /* Home-made assert. */
    public static void assertCond (boolean cond)
    {
        if (!cond)
            throw new IllegalArgumentException("Wrong condition");
    }
}

走訪 LinkedList

使用計數器 (Counter)

雖然 LinkedList 是串列而非陣列，Java 刻意提供相同的 API，所以仍然可以使用計數器走訪容器：

for (int i = 0; i < lst.size(); ++i)
    System.out.println(lst.get(i));

但從資料結構的觀點來看，這樣的程式碼效率不佳，故應儘量避免使用。

使用隱性迭代器 (Implicit Iterator)

由於 LinkedList 內含迭代器，故可用 for 迴圈走訪：

for (int n : lst)
    System.out.println(n);

使用顯性迭代器 (Explicit Iterator)

既然 LinkedList 有迭代器，也可以用顯式迭代器來走訪。參考以下範例程式：

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class MainProgram
{
    public static void main (String[] args)
    {
        List<Integer> lst = new LinkedList<Integer>();

        int data[] = {1, 2, 3, 4, 5};

        for (int n : data)
            lst.add(n);

        Iterator<Integer> it = lst.iterator();
        while (it.hasNext()) {
            int n = it.next();
            System.out.println(n);
        }
    }
}

比起使用 for 迴圈，使用顯式迭代器反而程式碼更長，故此範例程式僅供參考。