GuestArrayList.java

import java.util.Objects;

/**
 * 實作一：「懶惰」（lazy）的陣列版。
 *
 * add 不檢查重複，直接塞進陣列；重複要等到 remove 時才「一次把所有同名的都清成 null」。
 * 陣列滿了就「倍增」（array doubling）——這是攤銷 O(1) 插入的關鍵技巧。
 *
 * 資料不變量：
 *   0 <= used <= data.length
 *   data[used..] 全部是 null（尚未使用）
 * 注意：data[0..used-1] 可能含 null（被移除的洞）也可能含重複的名字。
 */
public class GuestArrayList implements GuestList {

    // package-private（沒有修飾子）：同一個套件裡的類別（例如子類別）可以直接存取
    String[] data = new String[2];
    int used = 0;                        // data[0..used-1] 是「用過」的格子

    @Override
    public void add(String name) {
        if (name == null) {                          // null 會跟「被移除的洞」混在一起，拒絕
            throw new IllegalArgumentException("賓客名字不可為 null");
        }
        if (this.used == this.data.length) {         // 滿了：換一個兩倍大的陣列
            String[] old = this.data;
            this.data = new String[this.used * 2];
            int i = 0;
            while (i < this.used) {
                this.data[i] = old[i];               // 把舊資料逐一複製過去：O(n)
                i = i + 1;
            }
        }
        this.data[this.used] = name;
        this.used = this.used + 1;
    }

    @Override
    public void remove(String name) {
        int i = 0;
        while (i < this.used) {                      // 懶惰法：必須掃完整個陣列，清掉所有同名
            if (this.data[i] != null && this.data[i].equals(name)) {
                this.data[i] = null;
            }
            i = i + 1;
        }
    }

    @Override
    public boolean isComing(String name) {
        int i = 0;
        while (i < this.used) {
            if (Objects.equals(this.data[i], name)) { // Objects.equals：兩邊都可能是 null 也安全
                return true;
            }
            i = i + 1;
        }
        return false;
    }

    @Override
    public int count() {
        int n = 0;
        int i = 0;
        while (i < this.used) {
            // 只在「第一次出現」時計數，這樣重複的名字不會被重複計算
            if (this.data[i] != null && indexOf(this.data[i]) == i) {
                n = n + 1;
            }
            i = i + 1;
        }
        return n;
    }

    /** @return name 第一次出現的索引；不存在則回傳 -1 */
    int indexOf(String name) {
        int i = 0;
        while (i < this.used) {
            if (this.data[i] != null && this.data[i].equals(name)) {
                return i;
            }
            i = i + 1;
        }
        return -1;
    }

    @Override
    public String[] coming() {
        String[] copy = new String[count()];        // 全新的陣列：防禦性複製
        int k = 0;
        int i = 0;
        while (i < this.used) {
            if (this.data[i] != null && indexOf(this.data[i]) == i) {
                copy[k] = this.data[i];
                k = k + 1;
            }
            i = i + 1;
        }
        return copy;
    }
}