美思 [Java] 程式設計教學:使用 LinkedList 物件

Java陣列
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

前言

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

LinkedListArrayList 在 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 的範圍為 0LinkedList 的寬度 (不包含)。超過這個範圍的話,會拋出 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 迴圈,使用顯式迭代器反而程式碼更長,故此範例程式僅供參考。

關於作者

身為資訊領域碩士,美思認為開發應用程式的目的是為社會帶來價值。如果在這個過程中該軟體能成為永續經營的項目,那就是開發者和使用者雙贏的局面。

美思喜歡用開源技術來解決各式各樣的問題,但必要時對專有技術也不排斥。閒暇之餘,美思將所學寫成文章,放在這個網站上和大家分享。