List và Queue

Bài này đi qua hai nhóm cấu trúc tuyến tính của nhánh Collection: danh sách List cho truy cập theo chỉ số, và hàng đợi Queue/Deque cho thao tác ở hai đầu.

Hai nhóm này chiếm phần lớn công việc hằng ngày. Bất cứ khi nào ta gom một dãy phần tử rồi lần lượt lấy ra, hoặc cần xử lý theo trình tự đến trước làm trước, ta đang cần một trong hai nhóm ở đây. Điểm mấu chốt không phải là biết tên lớp, mà là biết mỗi thao tác tốn bao nhiêu, để khi dữ liệu lớn lên thì chương trình không chậm bất ngờ. Vì thế bài này gắn mỗi thao tác với độ phức tạp của nó và nói rõ khi nào nên chọn cài đặt nào.

Hãy hình dung một tình huống cụ thể để thấy vì sao chuyện chọn cài đặt lại quan trọng. Ta viết hệ thống xử lý đơn hàng cho một cửa hàng trực tuyến. Đơn mới đến thì xếp vào hàng chờ, nhân viên lấy đơn cũ nhất ra xử lý trước, đó là hàng đợi. Danh sách sản phẩm trong một đơn thì cần đọc theo vị trí để hiển thị, đó là danh sách. Còn đơn của khách VIP phải được ưu tiên xử lý trước bất kể đến lúc nào, đó là hàng đợi ưu tiên. Ba nhu cầu, ba cấu trúc, và chọn sai thì hệ thống vẫn chạy đúng nhưng chậm dần cho tới lúc không chịu nổi.

Điều đáng nói là chọn sai rất khó phát hiện lúc đầu. Với mười đơn hàng, mọi cấu trúc đều nhanh như nhau. Sự khác biệt chỉ lộ ra khi số phần tử lên hàng chục nghìn, và lúc đó nó không lộ ra êm ái mà lộ ra dưới dạng một trang web đột nhiên treo. Vì thế người lập trình phải quyết định dựa trên độ phức tạp chứ không dựa trên cảm giác khi chạy thử vài phần tử. Đó là toàn bộ tinh thần của bài này.

Thử ngay: xem ArrayList dời chỗ phần tử chạy từng bước

Trước khi bàn tới bảng độ phức tạp, hãy bấm ▶ Chạy (hoặc kéo thanh trượt) để tự nhìn chi phí ấy hiện ra: chèn và xoá ở giữa ArrayList tốn O(n) vì mỗi ô nhớ mang một chỉ số cố định, nên chèn vào giữa buộc mọi phần tử phía sau dịch sang phải một bậc, còn xoá thì chúng dịch sang trái để lấp chỗ trống. Phần dưới sẽ giải thích con số ấy và cách chọn cài đặt cho hợp.

ArrayList: thêm cuối, chèn giữa, xoá đầu java

1import java.util.ArrayList;
2import java.util.List;
3
4public class Demo {
5    public static void main(String[] args) {
6        List<String> ds = new ArrayList<>();
7        ds.add("A");        // [A]
8        ds.add("B");        // [A, B]
9        ds.add("C");        // [A, B, C]
10        ds.add(1, "X");     // insert at index 1: B and C shift right
11        ds.remove(0);       // remove index 0: the rest shift left
12        System.out.println(ds);
13    }
14}

Ngăn xếp stack

main()

ds→ #1

Bộ nhớ động heap

#1ArrayList

Tạo một ArrayList rỗng. Bên trong là một mảng động, hiện chưa có phần tử nào.

1/70.5×1×2×

Danh sách List

List là tập hợp có thứ tự, cho phép trùng lặp và truy cập theo chỉ số. Hai cài đặt thông dụng là ArrayList và LinkedList, khác nhau ở cấu trúc lưu trữ nên khác nhau về hiệu năng.

• ArrayList lưu phần tử trong một mảng động bên trong. Truy cập theo chỉ số rất nhanh, O(1), vì chỉ là phép tính địa chỉ. Nhưng chèn hoặc xoá ở giữa thì phải dịch chuyển các phần tử phía sau, mất O(n). Khi mảng đầy, nó cấp phát mảng lớn hơn rồi sao chép, gọi là tăng dung lượng (resize).
• LinkedList là danh sách liên kết kép: mỗi nút giữ dữ liệu cùng hai con trỏ tới nút trước và nút sau. Thêm hoặc xoá ở hai đầu chỉ tốn O(1), nhưng truy cập phần tử thứ i phải đi lần từ đầu, mất O(n).

Trong thực tế ArrayList thắng ở đa số trường hợp nhờ tận dụng tốt bộ nhớ đệm (cache) của bộ xử lý; chỉ chọn LinkedList khi thao tác chủ yếu là thêm hoặc xoá ở hai đầu.

ArrayList nới dung lượng thế nào

Bên trong ArrayList là một mảng thường, cộng thêm một biến đếm số phần tử đang dùng. Khi mảng đầy mà ta còn muốn thêm, nó cấp một mảng mới lớn hơn, thường là gấp rưỡi, chép toàn bộ phần tử sang rồi bỏ mảng cũ. Việc chép này tốn O(n), nghe có vẻ đắt, nhưng nó hiếm khi xảy ra vì mỗi lần nới lại tăng dung lượng theo cấp số nhân.

Đây là chỗ cần hiểu cho đúng ý nghĩa của chữ trung bình. Nếu ta thêm n phần tử liên tiếp, tổng chi phí của tất cả các lần chép cộng lại vẫn chỉ cỡ n, vì sau mỗi lần nới thì số phần tử ta thêm được trước lần nới kế tiếp lại lớn hơn lần trước theo đúng hệ số nhân đó, nên các lần nới thưa dần rất nhanh. Chia đều ra, mỗi lần add tốn một lượng hằng số. Người ta gọi đó là chi phí O(1) khấu hao: một vài lần add lẻ tẻ rất đắt, nhưng tính bình quân trên cả dãy thì rẻ. Nếu biết trước sẽ có bao nhiêu phần tử, ta nên nói luôn với hàm dựng để nó cấp đủ ngay từ đầu và tránh mọi lần chép.

List<Integer> ds = new ArrayList<>(100_000);  // reserve capacity up front, no resizing
for (int i = 0; i < 100_000; i++) {
    ds.add(i);                                // each add is O(1) amortized
}

Vì sao ArrayList thường thắng dù lý thuyết nói LinkedList chèn giữa tốt hơn

Bảng độ phức tạp nói rằng chèn vào giữa LinkedList tốn O(1) còn ArrayList tốn O(n). Nghe vậy thì LinkedList phải thắng. Thực tế gần như luôn ngược lại, và lý do rất đáng học.

Thứ nhất, O(1) của LinkedList chỉ tính riêng động tác nối lại con trỏ, sau khi ta đã cầm sẵn nút cần chèn. Nhưng muốn chèn vào giữa thì trước hết phải đi tới giữa, mà đi tới phần tử thứ i của danh sách liên kết mất O(n) vì phải lần từng nút. Cộng lại, list.add(i, x) trên LinkedList vẫn là O(n), hệt như ArrayList. Cái O(1) kia chỉ đúng khi ta đang duyệt bằng iterator và chèn ngay tại chỗ đang đứng.

Thứ hai, hai phép O(n) này rất khác nhau về hằng số. ArrayList dịch một khối ô nhớ liền kề, và đó là việc mà phần cứng làm cực nhanh: bộ xử lý nạp cả một dải ô nhớ vào bộ nhớ đệm một lần, rồi dùng lệnh chép khối. LinkedList thì phải nhảy theo con trỏ từ nút này sang nút khác, mỗi nút nằm một nơi rải rác trên vùng nhớ động, nên gần như mỗi bước là một lần trượt bộ nhớ đệm và phải chờ nạp từ bộ nhớ chính. Một lần trượt như vậy đắt hơn hàng chục phép so sánh.

Thứ ba, LinkedList tốn bộ nhớ hơn nhiều. Mỗi phần tử phải gói trong một nút mang thêm hai tham chiếu trước và sau, nên chi phí phụ có thể gấp vài lần bản thân dữ liệu.

Kết luận thực dụng: mặc định dùng ArrayList. Chỉ cân nhắc LinkedList khi công việc chính là thêm và xoá ở hai đầu, mà ngay cả khi đó thì ArrayDeque ở phần sau còn nhanh hơn nữa. Nói cách khác, LinkedList hiếm khi là lựa chọn đúng trong mã Java hiện đại.

List<String> ds = new ArrayList<>();   // program to the List interface
ds.add("An");                          // append, amortized O(1)
ds.add("Binh");
ds.add(1, "Cuong");                    // insert at index 1, O(n)
String x = ds.get(0);                  // random access by index, O(1)
ds.remove("Binh");                     // remove by value, O(n)
System.out.println(ds.size());         // number of elements

// addFirst/addLast khong nam tren giao tiep List, nen khai bao kieu cu the o day
LinkedList<Integer> dq = new LinkedList<>(); // choose when adding at both ends
dq.addFirst(1);                        // insert at the head, O(1)
dq.addLast(2);                         // insert at the tail, O(1)

Thao tác thường dùng trên List

Bốn thao tác gặp nhiều nhất là thêm, đọc, ghi đè và xoá. Ngoài ra List còn có nhóm tìm kiếm như contains, indexOf và nhóm cắt lát như subList. Nắm chi phí của từng nhóm giúp tránh những vòng lặp chậm không đáng có.

• add(phần_tử) nối vào cuối, trung bình O(1); add(i, phần_tử) chèn tại chỉ số i, mất O(n) vì phải dịch phần đuôi.
• get(i) và set(i, phần_tử) đọc và ghi đè tại chỉ số i, với ArrayList là O(1).
• remove(i) xoá tại chỉ số, còn remove(Object) xoá theo giá trị đầu tiên khớp; cả hai đều mất O(n) với ArrayList.
• contains và indexOf quét tuần tự nên O(n); cần kiểm tra tồn tại thường xuyên thì dùng Set sẽ nhanh hơn hẳn.

List<Integer> a = new ArrayList<>(List.of(10, 20, 30, 20));
a.set(0, 99);                 // ghi đè phần tử đầu -> [99, 20, 30, 20]
int idx = a.indexOf(20);      // vị trí khớp đầu tiên -> 1
boolean co = a.contains(30);  // true
List<Integer> lat = a.subList(1, 3);  // view [20, 30], không sao chép

remove(int) khác remove(Object)

List<Integer> có cả remove(int index) lẫn remove(Object o). Khi gọi a.remove(1), Java chọn bản theo chỉ số và xoá phần tử thứ 1, không phải giá trị 1. Muốn xoá theo giá trị phải ép về Integer: a.remove(Integer.valueOf(1)). Đây là bẫy kinh điển do autoboxing gây ra, dễ tạo lỗi âm thầm.

Hàng đợi Queue và Deque

Queue mô tả hàng đợi, thường theo nguyên tắc vào trước ra trước (FIFO). Deque (double-ended queue) là hàng đợi hai đầu, thêm và lấy được ở cả hai phía, nên dùng làm cả ngăn xếp lẫn hàng đợi.

Khác biệt cốt lõi giữa Queue và List không nằm ở chỗ lưu trữ mà nằm ở ý định. List nói rằng phần tử có vị trí và ta muốn với tới vị trí bất kỳ. Queue nói rằng ta chỉ quan tâm tới đầu và cuối, còn ở giữa thì không đụng tới. Thu hẹp lời hứa như vậy là có chủ đích: khi kiểu chỉ hứa ít hơn, cài đặt được tự do tối ưu hơn, và người đọc mã hiểu ngay ý đồ mà không phải dò. Thấy một biến khai báo Deque là biết ngay nó được dùng như hàng đợi hoặc ngăn xếp, không ai chọc vào giữa.

Ghi nhớ hai quy ước tên. Với hàng đợi FIFO, phần tử vào ở đuôi và ra ở đầu, nên offer thêm vào đuôi còn poll lấy ở đầu. Với ngăn xếp LIFO, cả thêm lẫn lấy đều ở cùng một phía gọi là đỉnh, nên push và pop cùng làm việc ở đầu danh sách. Cùng một ArrayDeque phục vụ được cả hai kiểu, chỉ khác ở chỗ ta gọi bộ phương thức nào.

ArrayDeque

ArrayDeque cài Deque bằng mảng vòng, cho thao tác hai đầu ở O(1). Tài liệu Java khuyến nghị dùng nó thay cho lớp Stack cũ và thường nhanh hơn LinkedList khi làm hàng đợi. Các phương thức chính: offer/poll cho đầu hàng đợi, push/pop khi dùng như ngăn xếp.

Deque<String> hangCho = new ArrayDeque<>();
hangCho.offer("job1");        // enqueue at tail, O(1)
hangCho.offer("job2");
String dau = hangCho.poll();  // dequeue from head, O(1) -> "job1"

Deque<Integer> nganXep = new ArrayDeque<>();
nganXep.push(10);             // push onto stack top
nganXep.push(20);
int dinh = nganXep.pop();     // pop from stack top -> 20

PriorityQueue

PriorityQueue không theo FIFO mà luôn trả phần tử nhỏ nhất (theo thứ tự ưu tiên) ra trước. Bên trong là một đống nhị phân (binary heap), nên thêm phần tử và lấy phần tử nhỏ nhất đều mất O(log n), còn xem phần tử nhỏ nhất tốn O(1). Thứ tự ưu tiên lấy từ Comparable của phần tử, hoặc từ Comparator truyền vào hàm dựng.

PriorityQueue<Integer> pq = new PriorityQueue<>();  // min-heap by natural order
pq.offer(5); pq.offer(1); pq.offer(3);
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");   // prints 1 3 5, smallest first
}
// Use a Comparator to reverse into a max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

Vì sao PriorityQueue lại hữu ích đến vậy? Vì nó giải quyết một nhu cầu rất phổ biến: luôn lấy ra phần tử quan trọng nhất mà không phải sắp lại cả tập mỗi lần. Nếu giữ một danh sách rồi mỗi lần cần lại gọi sắp xếp, ta trả O(n log n) cho từng lần lấy. Nếu quét tuyến tính tìm nhỏ nhất, ta trả O(n) mỗi lần. Đống nhị phân cho ta O(log n), và nó làm được vậy nhờ chỉ duy trì một bất biến yếu: cha luôn nhỏ hơn con. Nó không sắp toàn bộ, nó chỉ bảo đảm đúng cái nhỏ nhất nằm trên đỉnh, và đó là tất cả những gì ta cần.

Hệ quả cần nhớ: duyệt một PriorityQueue bằng for-each sẽ ra thứ tự lộn xộn chứ không tăng dần, bởi bên trong nó chỉ là một đống chứ không phải một dãy đã sắp. Muốn lấy đúng thứ tự tăng dần thì phải poll lần lượt cho tới khi rỗng, đúng như ví dụ trên.

Ngăn xếp thì dùng ArrayDeque

Lớp Stack cũ kế thừa Vector và đồng bộ hoá mọi thao tác nên chậm. Cần một ngăn xếp, hãy khai báo Deque rồi tạo ArrayDeque, dùng push/pop/peek.

Nói thêm vì sao nên bỏ lớp Stack cũ. Stack ra đời từ Java 1.0 và kế thừa Vector, mà Vector đồng bộ hoá mọi phương thức để an toàn đa luồng. Cái giá phải trả là mọi lời gọi đều phải xin khoá, kể cả khi chương trình chỉ có một luồng và chẳng cần khoá nào. Tệ hơn, vì Stack là một List, nó phơi ra cả get(i) lẫn add(i, x), tức là cho phép chọc vào giữa một ngăn xếp, điều mà khái niệm ngăn xếp vốn cấm. Và do kế thừa Vector, thứ tự duyệt của nó lại ngược với thứ tự lấy ra, một cái bẫy khó chịu. ArrayDeque không mắc lỗi nào trong số đó: nó nhanh hơn, không khoá, và chỉ phơi ra đúng những thao tác hợp lệ ở hai đầu.

Bốn lớp cài đặt: bấm để xem đặc tính

Hai bộ phương thức: ném lỗi hay trả tín hiệu

Queue và Deque có hai bộ phương thức song song cho cùng thao tác, khác nhau ở cách báo thất bại. Bộ thứ nhất ném ngoại lệ khi không làm được, bộ thứ hai trả về một giá trị đặc biệt như false hoặc null. Chọn đúng bộ giúp mã sạch và không sập bất ngờ.

• Thêm vào hàng đợi: add ném IllegalStateException khi đầy, còn offer trả false.
• Lấy và bỏ phần tử đầu: remove ném NoSuchElementException khi rỗng, còn poll trả null.
• Xem phần tử đầu mà không bỏ: element ném ngoại lệ khi rỗng, còn peek trả null.

Khi hàng đợi có giới hạn dung lượng hoặc có thể rỗng trong luồng chạy bình thường, nên dùng bộ offer/poll/peek rồi kiểm tra giá trị trả về. Dùng bộ ném ngoại lệ khi rỗng là tình huống bất thường mà ta muốn dừng ngay để lộ lỗi.

Bảng sau tóm lại ba cặp để tiện tra.

Thao tác	Bản ném ngoại lệ	Bản trả tín hiệu	Trả về khi thất bại
Thêm vào đuôi	add	offer	false
Lấy và bỏ phần tử đầu	remove	poll	null
Xem phần tử đầu	element	peek	null

Cách chọn nên dựa trên một câu hỏi: rỗng là chuyện bình thường hay là dấu hiệu hỏng? Trong một vòng lặp tiêu thụ hàng đợi cho tới khi hết việc, rỗng là kết thúc bình thường, nên poll trả null là đúng cái ta cần để dừng vòng lặp. Ngược lại, nếu mã của ta vừa kiểm tra hàng đợi có phần tử rồi lập tức lấy ra, mà lại rỗng, thì chương trình đang sai ở đâu đó và ta muốn nó ném ngay để lộ lỗi thay vì âm thầm trả null rồi đổ vỡ ở chỗ khác. Đây chính là lý do thư viện cho ta hai bộ thay vì một.

Deque<String> hangCho = new ArrayDeque<>();
hangCho.offer("job1");
hangCho.offer("job2");

String job;
while ((job = hangCho.poll()) != null) {   // empty is the normal exit condition
    System.out.println("xu ly " + job);
}

Đoạn mã trên là mẫu hay gặp nhất khi tiêu thụ một hàng đợi. Ta gán kết quả poll vào biến ngay trong điều kiện, rồi so với null. Khi hàng đợi cạn, poll trả null, vòng lặp dừng gọn gàng mà không cần gọi thêm isEmpty. Nếu ở đây ta dùng remove thay cho poll, vòng lặp sẽ ném NoSuchElementException ngay lần chạm đáy, và ta buộc phải bọc thêm isEmpty hoặc bắt ngoại lệ, dài dòng hơn mà chẳng được gì.

Deque<Integer> q = new ArrayDeque<>();
if (q.poll() == null) {              // rỗng thì poll trả null, không ném lỗi
    System.out.println("hang doi rong");
}
q.offer(1);
Integer dau = q.peek();              // xem đầu mà không bỏ -> 1

Đừng để null lọt vào ArrayDeque

ArrayDeque không cho chứa phần tử null, vì null được dùng làm tín hiệu hàng đợi rỗng của poll và peek. Cố offer(null) sẽ ném NullPointerException. Nếu thật sự cần chứa giá trị vắng mặt, hãy bọc nó lại thay vì đẩy null trực tiếp.

Lỗi thường gặp với List và Queue

Vừa duyệt vừa xoá bằng for-each. Gọi ds.remove(x) ngay trong vòng for-each sẽ ném ConcurrentModificationException. Nguyên nhân gốc: iterator giữ một bộ đếm sửa đổi và phát hiện danh sách đã đổi sau lưng nó. Muốn xoá trong lúc duyệt, hãy dùng Iterator rồi gọi it.remove(), hoặc gọn hơn là ds.removeIf(dieuKien).

Dùng contains trong một vòng lặp. Mỗi lần contains trên ArrayList là một lần quét O(n), nên đặt nó trong vòng lặp n bước thì tổng chi phí thành O(n^2). Với vài trăm phần tử không sao, với vài chục nghìn thì chương trình đứng hình. Nguyên nhân gốc: List không có chỉ mục tra cứu. Cần kiểm tra tồn tại nhiều lần thì đổi sang HashSet để mỗi lần chỉ tốn O(1).

Tưởng List.of tạo ra danh sách sửa được. List.of(1, 2, 3) trả về một danh sách bất biến, gọi add hay set lên nó sẽ ném UnsupportedOperationException. Muốn sửa thì bọc lại: new ArrayList<>(List.of(1, 2, 3)).

Bài tập thực hành

Bài tập 1: kiểm tra tồn tại trên một triệu phần tử

Cho mảng int[] cỡ một triệu phần tử. So sánh chi phí kiểm tra một giá trị có mặt hay không khi dùng ArrayList<Integer> so với HashSet<Integer>. Nêu độ phức tạp Big-O của mỗi cách.

Lời giải chi tiết

Với ArrayList<Integer>, phương thức contains phải quét tuần tự, mỗi lần kiểm tra mất O(n); với một triệu phần tử đó là cả triệu phép so sánh. Với HashSet<Integer>, contains băm khoá rồi nhảy thẳng tới ngăn, trung bình O(1). Nếu bài toán hỏi tồn tại nhiều lần, HashSet nhanh hơn hẳn; chỉ phải trả thêm bộ nhớ cho bảng băm.

Bài tập 2: trộn k danh sách đã sắp

Dùng PriorityQueue để trộn k danh sách số nguyên đã sắp tăng dần thành một danh sách sắp tăng dần duy nhất. Phân tích độ phức tạp của lời giải.

Lời giải chi tiết

Đẩy phần tử đầu của mỗi danh sách vào một PriorityQueue nhỏ nhất, kèm thông tin nó đến từ danh sách nào. Mỗi vòng lấy ra phần tử nhỏ nhất rồi đẩy tiếp phần tử kế của chính danh sách đó vào hàng đợi.

// minimal sketch: queue holds [value, listIndex, posInList]
PriorityQueue<int[]> pq =
    new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));   // by value
// ... seed with the first element of each of the k lists ...
// each poll() and offer() costs O(log k)

Tổng cộng N phần tử, mỗi phần tử qua hàng đợi cỡ k một lần, nên độ phức tạp là O(N log k).

Bài tập 3: kiểm tra dấu ngoặc cân bằng

Cho một chuỗi chỉ gồm các ký tự (, ), [, ], {, }. Dùng Deque làm ngăn xếp để kiểm tra chuỗi có cân bằng ngoặc hay không. Nêu độ phức tạp.

Lời giải chi tiết

Duyệt từng ký tự: gặp ngoặc mở thì push vào ngăn xếp, gặp ngoặc đóng thì pop ra và so xem có khớp cặp không. Cuối cùng ngăn xếp phải rỗng.

Deque<Character> st = new ArrayDeque<>();
String s = "([]{})";
boolean ok = true;
for (char c : s.toCharArray()) {
    if (c == '(' || c == '[' || c == '{') {
        st.push(c);                     // ngoặc mở thì đẩy vào đỉnh
    } else {
        if (st.isEmpty()) { ok = false; break; }
        char m = st.pop();              // lấy ngoặc mở gần nhất
        if ((c == ')' && m != '(') ||
            (c == ']' && m != '[') ||
            (c == '}' && m != '{')) { ok = false; break; }
    }
}
ok = ok && st.isEmpty();                // còn dư ngoặc mở thì không cân bằng

Mỗi ký tự vào và ra ngăn xếp đúng một lần, mỗi thao tác O(1), nên tổng chi phí là O(n) với n là độ dài chuỗi.

Câu hỏi tự kiểm

Kiểm tra nhanh: List và Queue0/4 đúngchưa trả lời

1. 1Với List<Integer> a, lời gọi a.remove(1) làm gì?
2. 2Khi mảng bên trong đầy, ArrayList nới dung lượng thêm khoảng bao nhiêu?
3. 3Gọi ds.remove(x) ngay trong vòng for-each trên một ArrayList gây ra lỗi gì?
4. 4ArrayDeque có cho phép chứa phần tử null không?

Tóm tắt và ghi nhớ

• List có thứ tự và chỉ số, cho trùng lặp; ArrayList thắng ở đa số trường hợp, chỉ chọn LinkedList khi chủ yếu thêm hoặc xoá ở hai đầu.
• Nhớ chi phí: get và set trên ArrayList là O(1), còn chèn hoặc xoá ở giữa và contains là O(n).
• Cần hàng đợi hoặc ngăn xếp thì dùng ArrayDeque, thao tác hai đầu O(1), tránh lớp Stack cũ.
• Cần luôn lấy phần tử nhỏ nhất thì dùng PriorityQueue, thêm và lấy O(log n).
• Ưu tiên bộ offer/poll/peek và kiểm tra giá trị trả về khi rỗng là chuyện bình thường.

Nếu chỉ nhớ được một điều từ bài này, hãy nhớ rằng bảng độ phức tạp không phải là toàn bộ câu chuyện. LinkedList có O(1) đẹp hơn trên giấy nhưng thua ArrayList trong hầu hết phép đo thật, vì hằng số ẩn sau ký hiệu Big-O và cách bộ nhớ đệm hoạt động mới là thứ quyết định. Quy tắc làm việc rút ra khá gọn: mặc định ArrayList cho danh sách, ArrayDeque cho hàng đợi và ngăn xếp, PriorityQueue khi cần luôn lấy phần tử quan trọng nhất, và HashSet khi câu hỏi chính là phần tử này có tồn tại không. Chỉ đi chệch khỏi bốn lựa chọn đó khi có một lý do cụ thể và đo được.

Cũng nên nhớ thói quen khai báo biến bằng kiểu giao tiếp: viết List<String> ds = new ArrayList<>() chứ đừng viết ArrayList<String> ds = new ArrayList<>(). Nhờ vậy, ngày nào đổi cài đặt ta chỉ sửa đúng một chỗ sau new, còn toàn bộ mã dùng không phải đụng tới.