List: ArrayList và LinkedList

Tình huống mở đầu

Giờ cao điểm sáng thứ Hai, màn hình bếp của quán Cà Phê Gió đang có 6 đơn chờ pha: Latte, hai đơn đã bị khách huỷ, Mocha, Tea và một Latte nữa. Bạn viết một vòng for để xoá các đơn huỷ khỏi danh sách. Mong đợi: còn đúng 4 đơn. Thực tế màn hình hiện 5 đơn, và một đơn đã huỷ vẫn nằm đó chờ barista pha nhầm.

Không có dòng chữ đỏ nào hiện ra, code cũng không có dòng nào trông sai. Vậy máy đã làm điều gì mà bạn không nhìn thấy? Hãy giữ câu hỏi này trong đầu, cuối bài bạn sẽ tự tay sửa nó.

Ôn nhanh bài trước: trong họ Collection, interface nào là danh sách có thứ tự và cho phép phần tử trùng nhau: List, Set hay Map?

Đáp án: List. Set không cho phép trùng, còn Map lưu cặp khoá và giá trị nên đứng ngoài họ Collection.

Mục tiêu bài học

Sau bài này, bạn có thể:

• Viết được code thêm, chèn, đọc, sửa và xoá phần tử của ArrayList cho màn hình bếp.
• Mô tả được điều gì xảy ra với các ghế phía sau khi chèn hoặc xoá một phần tử ở giữa ArrayList.
• Chọn được ArrayList hay LinkedList cho một việc cụ thể và nêu được lý do.
• Sửa được vòng lặp xoá phần tử bị bỏ sót hoặc ném ConcurrentModificationException.

Bài này đo được bằng năm câu trong phần Tự kiểm tra, mỗi câu ghi rõ nó kiểm tra mục tiêu nào.

Hãy xem video dưới đây để có cái nhìn đầu tiên, sau đó mình đi chậm hơn từng bước ở các phần sau.

Bức tranh lớn (Big Picture)

Trước khi đi vào chi tiết, hãy xem bài này nằm ở đâu trong thư viện.

Cách đọc hình: đi từ trên xuống. Iterable là nền của mọi thứ dùng được với for-each, Collection thêm các thao tác chung như add và size, rồi Collection chia thành List, Set, Queue. Map đứng riêng bên phải vì nó lưu cặp khoá và giá trị. Ô màu lục (List) là hợp đồng mà bài này dùng, hai ô màu vàng (ArrayList, LinkedList) là hai cách làm đúng hợp đồng đó. Mỗi ô đều có nhãn chữ, màu chỉ giúp bạn tìm nhanh.

List chỉ nói rằng "tôi là danh sách có thứ tự, mỗi phần tử có một chỉ số". Nó không nói dữ liệu nằm ở đâu trong bộ nhớ. ArrayList trả lời bằng một dãy ô liền nhau, còn LinkedList trả lời bằng một chuỗi nút. Cùng hợp đồng, nhưng cách làm khác nhau kéo theo tốc độ khác nhau, và đó là chủ đề của bài.

Xuyên suốt bài, mình dùng một hình ảnh: ArrayList là một dãy ghế đánh số trong rạp chiếu phim, ghế đầu tiên là ghế 0. Dự án xuyên suốt là màn hình bếp của quán Cà Phê Gió: mỗi đơn là tên một đồ uống đứng trên một ghế. Có chỗ hình ảnh này không còn đúng, và mình sẽ chỉ rõ chỗ đó khi tới.

Khái niệm cốt lõi

Bài này có bốn khái niệm. Mỗi khái niệm đi kèm một hình.

Khái niệm 1: List, chỉ số và ArrayList

List là danh sách có thứ tự: mỗi phần tử đứng ở một vị trí cố định, và cho phép hai phần tử giống nhau. Chỉ số (index) là số thứ tự của vị trí đó, bắt đầu từ 0. Trong rạp chiếu phim, đó là số ghế.

ArrayList là cách làm List bằng một mảng bên trong. Mảng gồm các ô liền nhau, nên biết số ghế là nhảy thẳng tới ghế đó. Kích thước (size) là số ghế đang có người ngồi, không phải số ghế của cả rạp.

Cách đọc hình: bốn ô nằm ngang là bốn ghế, từ ghế 0 đến ghế 3. Ghế 0 đến 2 có người (Latte, Mocha, Tea), ghế 3 là chỗ trống dự phòng. Mũi tên "jumps straight to" cho thấy get(2) không đi qua ghế 0 và 1 mà tới thẳng ghế 2.

Ba thao tác bạn sẽ dùng nhiều nhất: add(x) xếp người mới vào cuối dãy, get(i) đọc người ở ghế i, size() đếm số người. Ghế phải có thật: gọi get(3) khi chỉ có ba người là lỗi.

Khái niệm 2: chèn hoặc xoá ở giữa thì các ghế sau dồn ô

Dồn ô (shift) là việc các phần tử phía sau dịch chuyển một ghế để nhường chỗ hoặc lấp chỗ trống. add(i, x) chèn x vào ghế i, còn remove(i) lấy người ở ghế i ra và trả người đó về.

Cách đọc hình: hàng trên là danh sách trước khi chèn: Latte, Mocha, Tea ở ghế 0, 1, 2. Hàng dưới là sau add(1, "Espresso"). Latte không di chuyển, Espresso ngồi vào ghế 1, còn Mocha và Tea mỗi người dịch sang phải một ghế. Hai mũi tên có nhãn "moves right" chỉ rõ ai dịch chuyển.

Đây là khái niệm quan trọng nhất của bài, vì mọi hành vi lạ về sau đều đến từ đây. Chèn hoặc xoá ở ghế càng gần đầu thì càng nhiều người phải dịch chuyển. Thêm vào cuối thì không ai phải dịch chuyển.

Chỗ hình ảnh không còn đúng: ở rạp thật, khách đã ngồi sẽ không phải đứng lên khi có người mới tới. Trong ArrayList, họ phải dịch ghế, và máy thực sự làm việc đó cho mỗi người, nên việc chèn đầu danh sách dài tốn thời gian.

Concept Check 1. Danh sách đang là [Latte, Mocha, Tea]. Bạn chạy orders.add(1, "Espresso"). Hãy chọn đáp án đúng trước khi đọc tiếp.

• A. Ba phần tử, Mocha mất vì Espresso ghi đè lên ghế 1.
• B. Bốn phần tử, Mocha vẫn ở ghế 1 và Espresso chen vào ghế cuối cùng.
• C. Bốn phần tử, Mocha ở ghế 2 vì Mocha và Tea cùng dồn sang phải.
• D. Lệnh báo lỗi vì ghế 1 đã có người nên không chèn được.

Đáp án: C. A nhầm add(i, x) với set(i, x): set mới ghi đè, còn add chèn thêm và giữ mọi phần tử. B sai vì danh sách luôn giữ thứ tự bạn yêu cầu, Espresso phải ngồi đúng ghế 1. D sai vì chèn vào ghế đang có người là việc bình thường, chỉ cần dồn ô. Chỉ có chỉ số ngoài khoảng từ 0 đến size() mới là lỗi.

Khái niệm 3: LinkedList, chuỗi nút thay cho dãy ghế

LinkedList là cách làm List bằng một chuỗi nút (node). Mỗi nút giữ một phần tử và biết nút kế tiếp. Không có mảng nào cả, nên không có ghế để nhảy tới.

Cách đọc hình: ba nút Latte, Mocha, Tea nối với nhau bằng mũi tên "next". Nút màu lục ở bên trái là Espresso mới tạo bởi addFirst, chỉ cần nối nó tới nút Latte. Hộp trắng bên phải là get(2): nó không có đường tắt, phải đi qua nút 0 và nút 1 rồi mới tới nút 2.

Vì vậy hai cách làm đổi chỗ sở trường cho nhau. ArrayList đọc theo chỉ số rất nhanh nhưng chèn ở đầu phải dồn ô. LinkedList chèn ở đầu chỉ đổi một liên kết nhưng đọc theo chỉ số phải đi bộ qua các nút. Ở rạp chiếu phim, hình ảnh dãy ghế không mô tả được LinkedList: hãy nghĩ nó là một hàng người đứng nắm tay nhau, người nào chỉ biết người đứng ngay sau mình.

Khái niệm 4: xoá phần tử khi đang duyệt

Duyệt là đi qua từng phần tử của danh sách. Khi bạn xoá phần tử trong lúc duyệt, các ghế phía sau dồn ô, nên vòng lặp có thể bỏ sót phần tử hoặc báo lỗi. Iterator là "con trỏ duyệt" mà vòng for-each dùng ngầm bên dưới. ConcurrentModificationException là lỗi mà iterator ném ra khi nó phát hiện danh sách bị sửa cấu trúc không qua chính nó.

Cách đọc hình: hàng trên màu xám là hai cách sai: xoá trong for-each ném ConcurrentModificationException, vòng lặp theo chỉ số tăng dần bỏ sót phần tử. Hàng dưới màu vàng là bốn cách đúng: Iterator.remove(), removeIf, vòng lặp đi ngược, và duyệt một bản sao. Bài này chỉ dùng removeIf làm cách chính.

removeIf là phương thức xoá mọi phần tử thoả một điều kiện bạn đưa vào, trong một lần duyệt an toàn. Phần o -> o.equals("CANCELLED") đọc là "với mỗi đơn o, kiểm tra o có bằng CANCELLED không"; bài Lambda ở chương sau sẽ giải thích kỹ cú pháp này, bây giờ bạn chỉ cần dùng nó như một khuôn mẫu.

Đây chính là lỗi ở tình huống mở đầu. Đoạn code dưới đây là thủ phạm:

Skip.java

import java.util.ArrayList;
import java.util.List;

public class Skip {
    public static void main(String[] args) {
        // List.of chỉ đọc, nên phải bọc vào ArrayList mới xoá được
        List<String> orders = new ArrayList<>(
                List.of("Latte", "CANCELLED", "CANCELLED", "Mocha", "Tea", "Latte"));
        // size() được tính lại ở mỗi vòng, i luôn tăng dù có xoá hay không
        for (int i = 0; i < orders.size(); i++) {
            if (orders.get(i).equals("CANCELLED")) {
                orders.remove(i);  // các ghế sau dồn trái, phần tử kế tiếp lọt vào ghế i
            }
        }
        System.out.println(orders + " size " + orders.size());
    }
}

Kết quả khi chạy [Đã chạy, JDK 17.0.15]:

[Latte, CANCELLED, Mocha, Tea, Latte] size 5

Có 5 phần tử và vẫn còn một CANCELLED, đúng như tình huống ở đầu bài. Đọc code từng phần:

Hãy xem từng bước máy thực hiện:

Bản chữ tương đương của animation:

Bạn vừa làm được: hiểu danh sách trong ArrayList là một dãy ghế, và việc dồn ô khi chèn hoặc xoá là nguồn gốc của lỗi ở tình huống mở đầu.

Ví dụ đầu tiên (Worked Example) và "Xem từng bước"

Đây là chương trình đầu tiên của dự án: màn hình bếp nhận ba đơn, chèn một đơn khẩn, rồi gọi một đơn ra bếp.

CafeOrders.java

import java.util.ArrayList;
import java.util.List;

public class CafeOrders {
    public static void main(String[] args) {
        // Biến kiểu List (hợp đồng) trỏ tới một ArrayList (cách làm) đang rỗng
        List<String> orders = new ArrayList<>();
        orders.add("Latte");  // vào ghế 0
        orders.add("Mocha");  // vào ghế 1
        orders.add("Tea");    // vào ghế 2
        System.out.println(orders);

        // Chèn vào ghế 1: Mocha và Tea phải dồn sang phải
        orders.add(1, "Espresso");
        System.out.println(orders);

        // remove(2) lấy phần tử ở ghế 2 ra và trả về nó, các ghế sau dồn sang trái
        String removed = orders.remove(2);
        System.out.println(removed + " " + orders);

        // get chỉ đọc nên không ghế nào dịch chuyển
        System.out.println(orders.get(0) + " " + orders.size());
    }
}

Predict: hãy dừng lại, lấy giấy nháp và đoán: chương trình in ra những dòng nào, và sau dòng orders.add(1, "Espresso") thì Mocha nằm ở ghế số mấy? Đoán xong rồi hãy đọc tiếp.

Kết quả mong đợi [Đã chạy, JDK 17.0.15]:

[Latte, Mocha, Tea]
[Latte, Espresso, Mocha, Tea]
Mocha [Latte, Espresso, Tea]
Latte 3

Đọc code từng dòng:

Bây giờ xem từng bước. Mỗi bước nêu dòng code đang chạy, trạng thái các ghế và lý do:

Bảng trace (bản chữ tương đương của animation, [Suy luận] bằng cách đi từng dòng và khớp với kết quả chạy thật):

Bạn vừa làm được: đọc một chương trình ArrayList và nói đúng ghế nào chứa gì sau từng dòng.

Concept Check xen kẽ

Chọn đáp án của bạn trước, rồi đọc phần đáp án ngay bên dưới mỗi câu.

Concept Check 2. List<Integer> codes đang là [10, 20, 30, 1]. Chạy codes.remove(1). Danh sách trở thành gì?

• A. [10, 30, 1], vì số 1 được hiểu là chỉ số.
• B. [10, 20, 30], vì lệnh xoá giá trị 1.
• C. Lỗi biên dịch vì Java không biết chọn phiên bản remove nào.
• D. Ném IndexOutOfBoundsException vì không có ghế số 1.

Đáp án: A. Với số nguyên viết thẳng, Java chọn remove(int index), tức xoá theo ghế. B là hiểu lầm hay gặp nhất: muốn xoá theo giá trị phải viết remove(Integer.valueOf(1)). C sai vì hai phiên bản remove là hai phương thức nạp chồng (cùng tên, khác kiểu tham số), Java chọn được. D sai vì ghế 1 tồn tại. [Đã chạy, JDK 17.0.15, xem phần Thử phá nó đi.]

Concept Check 3. Danh sách đang là [Latte, CANCELLED, Mocha, Tea, Latte], vòng for vừa xoá CANCELLED ở i bằng 1 và sắp tăng i. Lần xét kế tiếp là ghế nào và phần tử gì?

• A. Ghế 1 vì vòng lặp tự lùi lại sau khi xoá.
• B. Ghế 2, và đó vẫn là CANCELLED thứ hai như ban đầu.
• C. Không xét gì cả, vì danh sách bị sửa nên ConcurrentModificationException ném ra ngay.
• D. Ghế 2, phần tử Mocha, nên CANCELLED ở ghế 1 bị bỏ qua.

Đáp án: D. Vòng for với i tăng dần không biết danh sách vừa dồn ô, nó cứ tăng i. B sai vì sau khi xoá, CANCELLED thứ hai đã dồn về ghế 1. C sai vì lỗi này chỉ do iterator ném, mà vòng for theo chỉ số không dùng iterator, nên mới im lặng sai.

Concept Check 4. Màn hình bếp là một LinkedList<String> có 50000 đơn và dùng for (int i = 0; i < orders.size(); i++) để đọc orders.get(i). Điều gì xảy ra?

• A. Nhanh như ArrayList, vì cùng là List.
• B. Chậm, vì mỗi lần get(i) phải đi qua các nút từ một đầu của chuỗi.
• C. Lỗi biên dịch vì LinkedList không có get.
• D. Nhanh hơn ArrayList, vì không phải giữ mảng.

Đáp án: B. Hình LinkedList cho thấy không có đường tắt tới nút i. A và D nhầm "cùng hợp đồng" với "cùng tốc độ". C sai vì get là một phần của hợp đồng List, nên LinkedList có đủ. Cách duyệt đúng cho LinkedList là for-each.

Làm cùng mình (Guided Practice)

Bạn sẽ dựng dần class KitchenBoard qua năm bước nhỏ. Mỗi bước thêm vào chương trình của bước trước, và hỗ trợ giảm dần: bước 1 gần như làm sẵn, bước 5 chỉ còn đề. Gõ code vào một file KitchenBoard.java rồi chạy bằng lệnh java KitchenBoard.java.

Bước 1: thêm ba đơn.

import java.util.ArrayList;
import java.util.List;

public class KitchenBoard {
    public static void main(String[] args) {
        List<String> orders = new ArrayList<>();
        orders.add("Latte");
        // TODO 1: thêm "Mocha", rồi thêm "Tea"
        System.out.println("step 1: " + orders);
    }
}

Chạy xong bạn sẽ thấy: step 1: [Latte, Mocha, Tea].

Bước 2: chèn đơn khẩn lên đầu. Ngay dưới dòng in của bước 1, thêm:

        // TODO 2: chèn "Espresso" vào đầu danh sách
        System.out.println("step 2: " + orders);

Chạy xong bạn sẽ thấy: step 2: [Espresso, Latte, Mocha, Tea].

Vẽ ra giấy: kẻ bốn ô ghế 0 đến 3, điền trạng thái trước và sau bước này. Vẽ xong, đối chiếu: trước bước 2, Latte ở ghế 0, Mocha ghế 1, Tea ghế 2. Sau bước 2, Espresso ở ghế 0, và cả ba người cũ đều dịch sang phải một ghế. Hình add(1, Espresso) ở khái niệm 2 là cùng ý, chỉ khác vị trí chèn.

Bước 3: huỷ một đơn theo tên và gọi đơn đầu ra bếp.

        // TODO 3: huỷ đơn "Mocha" theo tên, và lấy đơn ở ghế 0 ra khỏi danh sách
        boolean cancelled = false;
        String served = null;
        System.out.println("step 3: " + cancelled + " " + served + " " + orders);

Chạy xong bạn sẽ thấy: step 3: true Espresso [Latte, Tea].

Vẽ ra giấy: từ trạng thái [Espresso, Latte, Mocha, Tea], vẽ danh sách sau khi bỏ Mocha và sau khi bỏ Espresso. Đối chiếu: hai lần xoá làm Latte dồn về ghế 0 và Tea về ghế 1. Gợi ý: remove có hai phiên bản, một nhận tên (trả về boolean) và một nhận ghế (trả về phần tử bị lấy ra).

Bước 4: đếm số Latte. Bạn tự quyết cách viết.

        // TODO 4: thêm một "Latte" vào cuối, rồi đếm số "Latte" trong danh sách
        int lattes = 0;
        System.out.println("step 4: " + lattes + " " + orders);

Chạy xong bạn sẽ thấy: step 4: 2 [Latte, Tea, Latte]. Gợi ý: vòng for-each với equals là đủ.

Bước 5: xoá mọi Latte bằng một lệnh, không viết vòng lặp.

        // TODO 5: xoá mọi "Latte" khỏi danh sách
        System.out.println("step 5: " + orders);

Chạy xong bạn sẽ thấy: step 5: [Tea]. Gợi ý: phương thức bạn cần có tên nghe như "xoá nếu". Lời giải đầy đủ nằm ở cuối bài.

Bạn vừa làm được: tự dựng một chương trình xoay quanh ArrayList qua năm bước và tự dự đoán trạng thái các ghế trước khi chạy. Toàn bộ mã nguồn của bài cũng nằm trong thư mục 12-collections/02-list của kho GitHub, nhưng bạn không cần mở nó để học.

Thử phá nó đi (Lỗi thường gặp)

Bốn lỗi dưới đây là những lỗi người mới gặp nhiều nhất với List. Mỗi dòng trong bảng đã được chạy thật trên danh sách [Latte, Mocha, Tea] hoặc danh sách tương tự [Đã chạy, JDK 17.0.15; thông báo lỗi có thể khác chữ ở phiên bản Java khác]. Bạn có thể tự gõ từng dòng vào jshell để thấy.

Lỗi thứ ba có một điểm lạ: danh sách sau lỗi là [Latte, Tea, CANCELLED, Mocha], nghĩa là lần xoá đầu tiên đã xảy ra rồi mới có lỗi, và CANCELLED thứ hai còn sót lại. Lỗi thứ hai thuộc loại hiểu sai cơ chế, và hình dưới đây gom cả hai mô hình hiểu sai thường gặp về remove lại một chỗ.

Cách đọc hình: hàng trên màu đỏ nhạt là mô hình sai: nhiều người tưởng xoá một ghế thì ghế đó thành lỗ trống và các ghế khác đứng yên, nên get(1) cho null và size vẫn là 4. Hàng dưới màu lục là mô hình đúng: danh sách không có lỗ trống, các ghế sau dồn sang trái, get(1) cho Tea và size còn 3.

Mô hình đúng này giải thích luôn lỗi ở tình huống mở đầu: vì ghế dồn trái, phần tử đứng ngay sau phần tử vừa xoá đã đổi chỗ.

Bạn vừa làm được: đọc bốn thông báo lỗi phổ biến của List và nói được nguyên nhân bằng lời thường.

Tự tay làm (Bài tập)

Làm lần lượt từng mức. Mỗi bài có đề, dữ liệu vào, kết quả mong đợi, tiêu chí nghiệm thu và gợi ý. Lời giải nằm riêng ở cuối bài, hãy thử trước rồi mới so.

Mức Cơ bản

Bài 1. Vẽ trạng thái. Dữ liệu vào là đoạn code sau, chạy theo từng dòng:

List<String> q = new ArrayList<>(List.of("A", "B", "C", "D"));
q.add(2, "X");              // chèn vào ghế 2
q.remove("B");              // xoá theo giá trị
q.set(0, "Z");              // thay nội dung ghế 0
q.remove(q.size() - 1);     // số nguyên nên là xoá theo ghế

Điền bảng gồm ba cột: dòng vừa chạy, danh sách sau dòng đó, size. Kết quả mong đợi: một bảng năm dòng (kể cả dòng đầu tiên). Tiêu chí nghiệm thu: danh sách sau dòng cuối cùng trùng với kết quả chạy thật, và bạn nói được dòng nào làm các ghế sau dồn ô. Gợi ý: remove(q.size() - 1) nhận một số nguyên nên là xoá theo ghế.

Bài 2. Đưa Tea lên đầu. Dữ liệu vào: danh sách [Latte, Espresso, Tea]. Viết code đưa Tea lên ghế 0 mà không tạo danh sách mới. Kết quả mong đợi: in ra [Tea, Latte, Espresso]. Tiêu chí nghiệm thu: dùng đúng một lệnh lấy ra và một lệnh chèn lại, và kết quả in ra đúng. Gợi ý: remove(int) trả về phần tử vừa lấy.

Bài 3. Sửa vòng lặp bỏ sót. Dữ liệu vào: file Skip.java ở phần Khái niệm 4. Sửa theo hai cách: một cách dùng removeIf, một cách dùng vòng for đi ngược từ cuối về đầu. Kết quả mong đợi: cả hai cách in ra [Latte, Mocha, Tea, Latte] size 4. Tiêu chí nghiệm thu: không còn CANCELLED, và bạn giải thích được vì sao đi ngược thì không bỏ sót. Gợi ý: khi đi ngược, các ghế chưa xét nằm phía trước và không bị dồn ô.

Mức Vận dụng

Bài 4. Class OrderBoard cho màn hình bếp. Viết class OrderBoard bọc một ArrayList<String> bên trong với các phương thức sau:

Dữ liệu vào là hàm main sau (thêm vào class của bạn):

public static void main(String[] args) {
    OrderBoard board = new OrderBoard();
    board.add("Latte");
    board.add("Mocha");
    board.add("Latte");
    board.addUrgent("Espresso");
    System.out.println(board + " size " + board.size());
    System.out.println("cancel Tea: " + board.cancel("Tea"));
    System.out.println("cancelAll Latte: " + board.cancelAll("Latte") + " " + board);
    System.out.println("next: " + board.next() + " " + board);
    System.out.println("next: " + board.next() + " " + board);
    System.out.println("next: " + board.next() + " " + board);
}

Kết quả mong đợi:

[Espresso, Latte, Mocha, Latte] size 4
cancel Tea: false
cancelAll Latte: 2 [Espresso, Mocha]
next: Espresso [Mocha]
next: Mocha []
next: null []

Tiêu chí nghiệm thu: sáu dòng in ra khớp từng ký tự, cancelAll không dùng vòng for tăng dần theo chỉ số, và next() không ném lỗi khi rỗng. Gợi ý: removeIf không cho biết số phần tử bị xoá, nên hãy so size() trước và sau.

Mức Thử thách (tuỳ chọn)

Bài 5. Đo và chọn cấu trúc cho hàng đợi. Giờ cao điểm có 50000 đơn trong hàng đợi, bếp liên tục lấy đơn đầu ra. Viết một chương trình đo thời gian lấy hết 50000 đơn ra khỏi đầu danh sách cho ba cấu trúc: ArrayList với remove(0), LinkedList với removeFirst(), ArrayDeque (một hàng đợi hai đầu có sẵn của Java) với pollFirst(). Đo bằng System.nanoTime(). Kết quả mong đợi: ba số đo của riêng máy bạn [Có thể khác nhau]. Tiêu chí nghiệm thu: bạn xếp được thứ tự nhanh chậm, giải thích bằng hình dồn ô và hình chuỗi nút vì sao ArrayList ở vị trí đó, và viết 2 đến 3 câu khuyên cấu trúc nên dùng cho màn hình bếp. Gợi ý: nhớ rằng remove(0) làm toàn bộ ghế còn lại dồn trái.

Tự kiểm tra (Retrieval Practice)

Trả lời bằng trí nhớ, không xem lại bài. Mỗi câu ghi rõ nó kiểm tra mục tiêu nào trong bốn mục tiêu ở đầu bài.

Câu 1 (nhớ lại, mục tiêu 1). Nêu hai phiên bản của remove trên List, và cho ví dụ trên List<Integer> để chỉ ra chúng khác nhau thế nào.

Câu 2 (dự đoán kết quả code, mục tiêu 1 và 2). Đoạn sau in ra gì?

List<Integer> a = new ArrayList<>(List.of(5, 6, 7));
a.add(1, 9);
a.remove(2);           // số nguyên viết thẳng: xoá theo ghế
a.set(0, a.get(2));    // lấy giá trị ở ghế 2 gán vào ghế 0
System.out.println(a);

Câu 3 (dự đoán trạng thái sau nhiều bước, mục tiêu 2). Danh sách List<String> ban đầu là [A, B, C, D, E]. Chạy lần lượt add(0, "Z"), remove(3), add(2, "Y"). Viết danh sách sau mỗi bước.

Câu 4 (tìm lỗi, mục tiêu 4). Đoạn sau định xoá mọi số nhỏ hơn 4 nhưng in ra [2, 4]. Hãy chỉ ra lỗi và sửa bằng removeIf.

List<Integer> b = new ArrayList<>(List.of(1, 2, 3, 4));
for (int i = 0; i < b.size(); i++) {
    if (b.get(i) < 4) {
        b.remove(i);  // xoá xong, phần tử sau dồn về ghế i
    }
}
System.out.println(b);

Câu 5 (giải thích cho bạn chưa học, mục tiêu 3). Bạn của bạn chưa biết lập trình hỏi: "Vì sao đọc đồ uống ở ghế số 40000 thì nhanh, mà chèn đồ uống vào ghế 0 lại chậm?" Hãy giải thích bằng hình ảnh dãy ghế, rồi nói một việc mà LinkedList làm tốt hơn.

Điều cần nhớ

• ArrayList giữ phần tử trên một dãy ghế đánh số từ 0, nên add, get, set, remove theo chỉ số đều dùng được ngay (mục tiêu 1).
• Chèn hoặc xoá ở giữa làm các ghế sau dồn ô, và remove(i) trả về phần tử vừa lấy ra (mục tiêu 2).
• ArrayList là lựa chọn mặc định, LinkedList chỉ đáng dùng khi thao tác nhiều ở đầu và không đọc theo chỉ số (mục tiêu 3).
• Muốn xoá trong lúc duyệt, dùng removeIf thay vì tự viết vòng for hay for-each (mục tiêu 4).

Cheat sheet một trang.

Cách đọc hình: mỗi hàng là một câu hỏi bên trái và công cụ nên chọn bên phải. Đọc theo hàng ngang: cần đọc hoặc thay theo vị trí thì ArrayList, thêm hoặc xoá ở đầu thì LinkedList hoặc ArrayDeque nhưng phải đo, cần lọc khi duyệt thì removeIf hoặc Iterator.remove.

Câu hỏi để dành cho ngày mai: nếu màn hình bếp không được có hai đơn trùng tên, và bạn muốn tra "đơn của khách số 7" ngay lập tức, List còn phù hợp không? Hãy nghĩ trước khi sang bài sau.

Đào sâu

Phần này dành cho bạn tò mò. Bỏ qua cũng không thiếu gì ở trên.

Bên trong ArrayList. ArrayList giữ một mảng thật, và số ghế của mảng (dung lượng, capacity) thường lớn hơn size. Khi mảng đầy, add tạo một mảng mới lớn hơn rồi chép toàn bộ phần tử sang. Quan sát trong OpenJDK 17.0.15 bằng cách đọc trường nội bộ của ArrayList trong một lần thử riêng của người biên soạn [Đã chạy]: danh sách mới tạo có mảng rỗng, lần add đầu tiên mở mảng 10 ghế, rồi mảng lớn dần thành 15, 22, 33, 49 ghế mỗi khi đầy (tăng khoảng 1,5 lần). Đây là chi tiết cài đặt của OpenJDK, không nằm trong hợp đồng của List, nên đừng viết code phụ thuộc vào nó. Nếu bạn biết trước sẽ có nhiều phần tử, new ArrayList<>(50000) tránh được các lần chép đó.

So với lựa chọn khác. Số đo của Bench.java trong lần chạy của người biên soạn khi lấy 50000 đơn ra khỏi đầu danh sách [Có thể khác nhau, máy của bạn sẽ ra số khác nhưng thứ tự giữ nguyên]: ArrayList.remove(0) mất cỡ vài trăm mili giây, còn LinkedList.removeFirst và ArrayDeque.pollFirst mất vài mili giây. Vì cả hai đầu của ArrayDeque đều rẻ và không tốn một đối tượng nút cho mỗi phần tử, nó thường là lựa chọn tốt hơn LinkedList khi bạn cần một hàng đợi.

Hiểu lầm nâng cao. Nhiều người nghĩ xoá trong for-each luôn ném ConcurrentModificationException. Không luôn: với [1, 2, 3], xoá phần tử 2 trong for-each không báo lỗi và kết quả là [1, 3] [Đã chạy, JDK 17.0.15]. Lý do là sau khi xoá, hasNext() thấy danh sách đã hết phần tử nên vòng lặp dừng mà không gọi next(), và chính next() mới là nơi phát hiện thay đổi. Cơ chế này chỉ là "phát hiện theo khả năng", không phải bảo đảm.

Giới hạn của bài. Bài này chưa nói về sắp xếp danh sách (bài Comparator), về an toàn khi nhiều luồng cùng dùng một danh sách, và về subList hay ListIterator. Các danh sách tạo bằng List.of là chỉ đọc, và Arrays.asList có kích thước cố định, nên chúng không dùng được cho add hay remove.

Đọc thêm (tài liệu chính thống, Java SE 17):

• The Java Tutorials: The List Interface
• Javadoc: java.util.ArrayList
• Javadoc: java.util.LinkedList
• Javadoc: java.util.ConcurrentModificationException

Bài tiếp theo

Bài sau là Set và Map: hai cấu trúc trả lời câu hỏi mà List làm không tốt, đó là "đơn này đã có chưa" và "đơn của khách số 7 là gì" mà không phải đi qua từng ghế. Bạn cũng sẽ thấy hashCode và equals quyết định chúng đúng hay sai.

Mini-dự án nối tiếp: ở bài sau, màn hình bếp sẽ thêm hai việc: chặn một khách đặt trùng cùng một đơn bằng Set, và tra nhanh đơn của một khách bằng Map. Hãy giữ lại class OrderBoard bạn vừa viết làm điểm xuất phát.

Lời giải và đáp án

Hãy thử xong rồi mới đọc phần này.

Lời giải Làm cùng mình. Chỉ cần thay các dòng // TODO bằng những dòng dưới đây, ghép lại chạy ra đúng năm dòng step ở trên [Đã chạy, JDK 17.0.15]:

orders.add("Mocha");
orders.add("Tea");

orders.add(0, "Espresso");  // chèn có chỉ số nên ba đơn cũ dồn sang phải

boolean cancelled = orders.remove("Mocha");  // xoá theo giá trị, trả về boolean
String served = orders.remove(0);            // xoá theo ghế, trả về phần tử bị lấy

orders.add("Latte");
int lattes = 0;
for (String order : orders) {
    if (order.equals("Latte")) {
        lattes++;  // chỉ đọc, không xoá nên for-each an toàn
    }
}

orders.removeIf(order -> order.equals("Latte"));  // xoá mọi Latte trong một lần duyệt

Lời giải Bài 1. [Suy luận, khớp với kết quả chạy thật [Z, X, C] size 3]

Dòng 2 và dòng 3 làm ghế sau dồn ô. set không dồn ô vì chỉ thay nội dung một ghế. Dòng cuối là xoá theo ghế 3, lấy D ra.

Lời giải Bài 2. [Đã chạy, in ra [Tea, Latte, Espresso]]

String tea = orders.remove(2);  // lấy Tea ra và giữ trong biến
orders.add(0, tea);             // chèn lại vào ghế 0

Dòng một lấy Tea ra khỏi ghế 2 và giữ nó trong biến tea, lúc này Tea chưa còn nằm trong danh sách. Dòng hai chèn Tea vào ghế 0 nên Latte và Espresso dồn sang phải. Cần giữ Tea trong biến vì remove đã lấy nó ra khỏi danh sách: nếu không giữ, bạn mất đơn.

Lời giải Bài 3. Cách một: orders.removeIf(o -> o.equals("CANCELLED"));. Cách hai: đổi vòng lặp thành for (int i = orders.size() - 1; i >= 0; i--) giữ nguyên phần thân. Cả hai in ra [Latte, Mocha, Tea, Latte] size 4 [Suy luận]. Lý do: removeIf xử lý mỗi phần tử đúng một lần, còn đi ngược thì ghế còn lại phía trước không bị dồn ô.

Lời giải Bài 4. [Đã chạy, sáu dòng khớp với kết quả mong đợi]

Các phương thức add, cancel, size chỉ là một dòng gọi thẳng tới ArrayList bên trong (orders.add(drink), orders.remove(drink), orders.size()), và toString trả về orders.toString(). Ba phương thức đáng đọc kỹ:

public void addUrgent(String drink) {
    orders.add(0, drink);  // đơn khẩn đứng đầu
}

public int cancelAll(String drink) {
    int before = orders.size();
    orders.removeIf(order -> order.equals(drink));
    return before - orders.size();  // chênh lệch chính là số đơn đã huỷ
}

public String next() {
    if (orders.isEmpty()) {
        return null;  // tránh IndexOutOfBoundsException khi rỗng
    }
    return orders.remove(0);
}

Chạy main của đề bài với class này ra đúng sáu dòng mong đợi [Đã chạy, JDK 17.0.15].

Gợi ý lời giải Bài 5. Khuôn mẫu đo cho mỗi cấu trúc là như nhau, bạn chỉ đổi phần thân vòng lặp:

long start = System.nanoTime();
while (!array.isEmpty()) {
    array.remove(0);  // với LinkedList đổi thành removeFirst(), với ArrayDeque đổi thành pollFirst()
}
long elapsedMs = (System.nanoTime() - start) / 1_000_000;  // đổi nano giây ra mili giây

System.nanoTime() cho thời điểm tính bằng nano giây, lấy hiệu hai lần đo rồi chia cho một triệu để ra mili giây. Với LinkedList thay thân vòng bằng linked.removeFirst(), với ArrayDeque thay bằng deque.pollFirst(). Danh sách phải được nạp đủ 50000 phần tử trước khi bắt đầu đo. Một lần chạy của người biên soạn [Có thể khác nhau]:

ArrayList.remove(0): 147 ms
LinkedList.removeFirst: 1 ms
ArrayDeque.pollFirst: 1 ms

ArrayList.remove(0) chậm hơn hẳn vì mỗi lần lấy đơn đầu, toàn bộ ghế còn lại dồn trái. Hai cấu trúc còn lại chỉ đổi một liên kết hoặc một chỉ số đầu. Khuyến nghị: dùng ArrayDeque cho hàng đợi của bếp, và vẫn dùng ArrayList ở nơi cần đọc theo chỉ số.

Đáp án Tự kiểm tra.

1. remove(int index) xoá theo ghế và trả về phần tử bị lấy ra, remove(Object o) xoá theo giá trị và trả về boolean. Với List<Integer> đang là [10, 20, 30, 1]: remove(1) cho [10, 30, 1], còn remove(Integer.valueOf(1)) cho [10, 20, 30]. Kiểm tra mục tiêu 1.
2. In ra [7, 9, 7] [Đã chạy]. Từng dòng: [5, 6, 7], sau add(1, 9) là [5, 9, 6, 7], sau remove(2) (xoá theo ghế, lấy ra 6) là [5, 9, 7], sau set(0, a.get(2)) là [7, 9, 7]. Kiểm tra mục tiêu 1 và 2.
3. Sau add(0, "Z"): [Z, A, B, C, D, E]. Sau remove(3) lấy ra C: [Z, A, B, D, E]. Sau add(2, "Y"): [Z, A, Y, B, D, E] [Suy luận]. Kiểm tra mục tiêu 2.
4. Sau khi xoá 1 ở i bằng 0, số 2 dồn về ghế 0 nhưng i đã tăng lên 1 nên 2 bị bỏ qua, và vòng lặp dừng khi i bằng 2 vì size còn 2. Sửa: b.removeIf(n -> n < 4); cho [4] [Suy luận]. Kiểm tra mục tiêu 4.
5. Dãy ghế đánh số sẵn nên nhân viên rạp đi thẳng tới ghế 40000. Chèn vào ghế 0 thì tất cả người đang ngồi phải dịch sang phải một ghế. LinkedList làm tốt hơn việc thêm và bỏ ở đầu, vì chỉ đổi một liên kết. Kiểm tra mục tiêu 3.