AY 22-23 Final Exam - Question B1（Linked List 實作綜合題）

📝 情境說明

系統：IVE 停車場系統（IVECPS）。每一輛車是一個節點（ListNode），包含以下欄位：

type（String，例如 "private", "van"）
parkingSpaceNo（int，停車格編號）
plateNo（String，車牌號碼）
next（ListNode，指向下一節點）

本題將考驗如何實作串列的基礎操作：移除頭部節點、走訪搜尋，以及依照編號大小進行中間插入。

Part (a)：基礎操作實作

(i) removeFromHead() 的標準實作（5 分）

要求：移除並回傳排在第一位的節點（ListNode）。

public ListNode removeFromHead() throws EmptyListException {
    if (isEmpty())
        throw new EmptyListException();

    ListNode temp = head;          // 把目前的 head 暫存

    if (head == tail) {            // 特例：只有一個節點
        head = tail = null;        // 移除後清空頭尾指標
    } else {                       // 一般情況：至少有兩個節點
        head = head.next;          // head 指向下一個節點
    }

    return temp;                   // 回傳被移除的節點
}

⚠️ 教授重點：務必處理 head == tail 的特例情況，否則 tail 會殘留指向已被移除的節點。

(ii) isAvailable(int parkingSpaceNo) 的標準實作（6 分）

要求：檢查指定車位是否空著；若被佔用回傳 false，否則回傳 true。

public boolean isAvailable(int parkingSpaceNo) {
    ListNode current = head;               // 從頭開始巡邏

    while (current != null) {              // 只要還沒到串列尾就繼續
        if (current.parkingSpaceNo == parkingSpaceNo) {
            return false;                  // 找到代表被佔用
        }
        current = current.next;            // 繼續往下一個節點
    }

    return true;                           // 全部走訪完沒找到，代表空位
}

⚠️ 教授重點：不要在 LinkedList 類別內使用 this.parkingSpaceNo；必須派一個巡邏員（變數 current）逐一走訪每個節點進行檢查。

Part (b)：依序插入 (Insert in Order)

當新車進入時，系統要依 parkingSpaceNo 的大小把它插入單向鏈結串列，維持由小到大的排序。

(i) ParkingSpaceComparator 實作（3 分）

實作 Comparator 介面，完成 isLessThan 與 isGreaterThan。

public class ParkingSpaceComparator implements Comparator {

    public boolean isLessThan(int item1, int item2) {
        return item1 < item2;
    }

    public boolean isGreaterThan(int item1, int item2) {
        return item1 > item2;
    }
}

⚠️ 教授重點：實作介面時不要加 abstract 關鍵字，參數必須完整宣告型別 (int)，直接 return 運算結果最簡潔。

(ii) insertInOrder() 中間插入邏輯填空（6 分）

請完成在中間插入時的 5 個填空：

// ... 前面已經處理了空陣列、插在最前、插在最後的特例 ...
} else {  // insert in the middle
    ListNode current = head; // (1) locate to head node

    while ( current.next != null ) {  // (2) check boundary
        if ( comparator.isGreaterThan(current.next.parkingSpaceNo, parkingSpaceNo) ) {  // (3) check ordering
            ListNode newNode = new ListNode(type, parkingSpaceNo, plateNo);  // (4) create a new ListNode
            newNode.next = current.next;
            current.next = newNode;
            break; // inserted, exit loop
        }
        current = current.next; // (5) go to next node
    }
}

填空詳解：

(1) head：巡邏員從串列頭部開始走訪。
(2) current.next != null：因為要檢查下一個節點的值，必須確保它存在，避免 NullPointerException。
(3) comparator.isGreaterThan(...)：若「下一個節點的號碼」大於「新車號碼」，代表新車應插在目前節點與下個節點之間。
(4) ListNode newNode = ...：必須實例化新節點，並傳入對應的資料。
(5) current = current.next：巡邏員逐一往下一個節點移動。

💡 教授的綜合總結與考試速記：

刪除節點時，務必思考邊界情況（空串列、只有一個節點、在頭端刪除）。
走訪串列的標準起手式：ListNode current = head; 搭配迴圈，並在每次迴圈的最後做 current = current.next;，忘了這行會造成無限迴圈當機！
中間插入的靈魂：單向串列在中間插入時要「往前看一格（look ahead）」，也就是讓 current 停在要插入位置的「前一個」節點上。因此迴圈條件常用 current.next != null。
考試寫程式題時，建議在紙上畫出幾個方塊（節點）和箭頭（指標），視覺化模擬「指標切換」的過程，能大幅減少錯誤。