ArrayList 中的遍歷刪除

在代碼編寫過程中經(jīng)常會遇到這樣的要求：遍歷一個線性表，要求只遍歷一遍（時間復雜度\(O(n)\)），刪除符合指定條件的元素，且要求空間復雜度 \(O(1)\)。

例如我們有下列數(shù)據(jù)，要求遍歷列表并刪除所有偶數(shù)。

List<Integer> myList = new ArrayList<>(Arrays.toList(new Integer[]{2, 3, 5, 8, 10, 9}));

代碼1：直接遍歷列表并刪除（錯誤）

初學者可能會直觀地認為，我直接一個for循環(huán)遍歷刪除不就好了嗎？但實際上這種做法是錯誤的。

static void remove1(List<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) % 2 == 0) {
            list.remove(i);
        }
    }
}

使用上面的測試數(shù)據(jù)，結(jié)果為：[3, 5, 7, 10, 9]，其中一個偶數(shù) 10 并沒有被刪除。

事實上，當刪除列表中元素時，列表的 size() 會改變！當?shù)谝粋€ 2 被刪除時，此時 list.size() 已經(jīng)從 6 變成了 5，而 i 只會一直向前跑，因此當 8 被刪除時，list.size() 為 4，此時 i 已經(jīng)變?yōu)?5，不再滿足 i < list.size() 的循環(huán)條件，就會退出循環(huán)，后面的元素也不會再被處理。

代碼2：控制循環(huán)變量的遍歷（低效）

第二種做法是，不采用 for 循環(huán)，而是采用 while 循環(huán) + 控制循環(huán)變量 i 的做法。

static void remove2(List<Integer> list) {
    int i = 0;
    int j;
    while (i < list.size()) {
        if (list.get(i) % 2 == 0) {
            j = i--;
            // 此處存在 i < 0 的可能，所以要及時恢復 i 的位置
            if (i < 0) {
                i = 0;
            }
            list.remove(j); // 注意此處刪除的是 j（也就是原來的 i）指向的元素
        } else {
            i++;
        }
    }
}

這里要對循環(huán)變量 i 進行控制，當刪除一個元素時，i 并不能向前進一個位置而應該向后回退一個位置，從這個回退的位置開始重新向前走，才不至于遺漏本應被遍歷到的元素。

代碼3：使用迭代器（推薦）

一種更好的寫法是使用迭代器，因為迭代器會自動判斷列表中的每一個元素是否被遍歷過。事實上，迭代器的實現(xiàn)和代碼 2 很接近，但是可讀性更好。

static void remove3(List<Integer> list) {
    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        Integer next = iterator.next();
        if (next % 2 == 0) {
            iterator.remove();
        }
    }
}

代碼4：使用 removeIf() 方法

Java 中對 ArrayList 類還支持一種 removeIf() 方法，參數(shù)傳入一個 Predicate 接口的實現(xiàn)對象或一個 lambda 表達式即可。

static void remove4(List<Integer> list) {
    list.removeIf(new Predicate<Integer>() {
        @Override
        public boolean test(Integer i) {
            return i % 2 == 0;
        }
    });
}

或者采用 lambda 表達式，更簡潔：

list.removeIf(i -> i % 2 == 0);

以上就是對列表遍歷刪除的方法總結(jié)。如果條件比較簡單，可以直接采用 removeIf() 方法，如果條件比較復雜，那么采用迭代器是一種比較好的方法。