[Java Basics] ArrayList và LinkedList trong Java: Làm việc với Collection

Một array trong Java có độ dài cố định ngay khi object được tạo ra và không bao giờ thay đổi được nữa. Đúng một hạn chế đó là lý do java.util tồn tại: ngay khi chương trình không biết trước sẽ giữ bao nhiêu element, array không còn là công cụ phù hợp và List thay thế nó.

ArrayList và LinkedList là hai implementation của List mà lập trình viên Java gặp đầu tiên, và gần như mọi bài hướng dẫn đều kết thúc phần so sánh bằng câu "LinkedList insert và delete nhanh hơn". Câu đó sai nhiều hơn đúng, nên bài này sẽ đếm số thao tác thật sự mà mỗi implementation phải làm thay vì lặp lại khẩu hiệu.

Mọi dòng output, compiler error, stack trace và con số đếm được bên dưới đều lấy từ việc compile và chạy code trên OpenJDK 21.0.6.

Vì sao array có độ dài cố định là chưa đủ

Array chỉ được cấp phát kích thước một lần. Xin ô thứ tư trong một array ba ô là JVM chặn ngay:

public class FixedArray {
    public static void main(String[] args) {
        String[] names = new String[3];
        names[0] = "ada";
        names[1] = "linus";
        names[2] = "grace";
        names[3] = "ken";
    }
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
	at FixedArray.main(FixedArray.java:7)

Muốn chứa thêm một cái tên nữa, bạn phải cấp phát một array lớn hơn, copy ba reference cũ sang, rồi gán lại biến. Làm bằng tay một lần thì mệt; làm mỗi lần dữ liệu lớn lên, lại còn phải theo dõi xem thực sự có bao nhiêu ô đang được dùng, thì đó đã là một data structure nhỏ. ArrayList chính là data structure đó, đã viết sẵn và đã được kiểm chứng.

List khác array ở bốn điểm đáng nhớ:

Dòng thứ ba kéo theo cả một loạt hệ quả riêng, và phần nói về autoboxing bên dưới dành trọn cho chúng.

Interface Collection và List

List không phải class, nó là interface, và nó nằm ở cuối một chuỗi interface ngắn. Mỗi interface thêm vào một khả năng, và tất cả những gì nằm trên List đều dùng chung với các loại collection khác.

Chuỗi đó không phải hình vẽ theo trí nhớ. Nó đọc được thẳng từ runtime:

import java.util.*;

public class Shape {
    static void show(Class<?> c) {
        StringBuilder sb = new StringBuilder(c.getSimpleName() + " -> ");
        for (Class<?> i : c.getInterfaces()) sb.append(i.getSimpleName()).append(" ");
        Class<?> sup = c.getSuperclass();
        if (sup != null) sb.append("| extends ").append(sup.getSimpleName());
        System.out.println(sb.toString().trim());
    }

    public static void main(String[] args) {
        show(Collection.class);
        show(List.class);
        show(SequencedCollection.class);
        show(ArrayList.class);
        show(LinkedList.class);
    }
}

Collection -> Iterable
List -> SequencedCollection
SequencedCollection -> Collection
ArrayList -> List RandomAccess Cloneable Serializable | extends AbstractList
LinkedList -> List Deque Cloneable Serializable | extends AbstractSequentialList

Đọc từ trên xuống, mỗi interface góp thêm đúng một ý:

Hai marker interface ở dưới cùng mới là thứ cho biết bạn đang cầm cái gì. ArrayList implement RandomAccess, đó là cách JDK nói "truy cập theo index trên list này rẻ". LinkedList không implement nó, đổi lại implement Deque. Ngôn ngữ không ép buộc gì ở đây, nhưng code trong chính JDK có rẽ nhánh dựa vào nó, và code của bạn cũng nên như vậy khi chọn class để khởi tạo.

Khai báo theo interface, khởi tạo bằng class

Hệ quả thực dụng của cây interface đó là một thói quen nên tập ngay: khai báo biến là List, và chỉ chọn implementation ở vế new.

List<String> names = new ArrayList<>();

Toàn bộ phần code phía sau dòng đó - các method khác, return type, field - chỉ nhìn thấy một List. Đổi ArrayList sang LinkedList khi ấy chỉ chạm đúng một chữ. Khai báo biến là ArrayList thì khóa lựa chọn đó ở mọi nơi biến đi qua, mà không đổi lại được gì.

Thứ duy nhất bạn mất là những method interface không khai báo. LinkedList có push, method này đến từ Deque chứ không phải từ List, nên một biến kiểu List không nhìn thấy nó:

List<String> names = new LinkedList<>();
names.push("ada");

IfaceOnly.java:6: error: cannot find symbol
        names.push("ada");
             ^
  symbol:   method push(String)
  location: variable names of type List<String>
1 error

Error đó là type system đang làm đúng việc của nó. Nếu bạn thật sự cần push, type bạn muốn là Deque chứ không phải LinkedList.

Tạo list và những method bạn sẽ dùng thật sự

List cần một type argument, và nó bắt buộc phải là reference type. Primitive bị từ chối thẳng:

List<int> numbers = new ArrayList<>();

PrimList.java:5: error: unexpected type
        List<int> numbers = new ArrayList<>();
             ^
  required: reference
  found:    int
1 error

Qua được chỗ đó rồi thì toàn bộ API cốt lõi gói gọn trong một chương trình:

import java.util.*;

public class Basics {
    public static void main(String[] args) {
        List<String> langs = new ArrayList<>();
        System.out.println("isEmpty on a new list: " + langs.isEmpty() + ", size " + langs.size());

        langs.add("Java");
        langs.add("Kotlin");
        langs.add("Scala");
        langs.add(1, "Groovy");
        System.out.println("after adds: " + langs + ", size " + langs.size());

        System.out.println("get(0)          = " + langs.get(0));
        System.out.println("set(2, \"Clojure\") returns " + langs.set(2, "Clojure") + " -> " + langs);
        System.out.println("indexOf(Scala)  = " + langs.indexOf("Scala"));
        System.out.println("contains(Java)  = " + langs.contains("Java"));
        System.out.println("remove(\"Groovy\") = " + langs.remove("Groovy") + " -> " + langs);
        System.out.println("remove(0)        = " + langs.remove(0) + " -> " + langs);

        List<String> dup = new ArrayList<>(List.of("a", "b", "a", "b"));
        System.out.println("  " + dup + " indexOf(b)=" + dup.indexOf("b") + " lastIndexOf(b)=" + dup.lastIndexOf("b"));

        try {
            langs.get(9);
        } catch (IndexOutOfBoundsException e) {
            System.out.println("get(9) threw " + e);
        }
    }
}

isEmpty on a new list: true, size 0
after adds: [Java, Groovy, Kotlin, Scala], size 4
get(0)          = Java
set(2, "Clojure") returns Kotlin -> [Java, Groovy, Clojure, Scala]
indexOf(Scala)  = 3
contains(Java)  = true
remove("Groovy") = true -> [Java, Clojure, Scala]
remove(0)        = Java -> [Clojure, Scala]
  [a, b, a, b] indexOf(b)=1 lastIndexOf(b)=3
get(9) threw java.lang.IndexOutOfBoundsException: Index 9 out of bounds for length 2

Có bốn chi tiết trong output đó đáng dừng lại:

• add(1, "Groovy") chèn vào một vị trí và đẩy mọi thứ phía sau sang phải; add("Scala") thì nối vào cuối.
• set trả về element bị thay thế, không trả về list và cũng không trả về boolean.
• remove(Object) trả về boolean, còn remove(int) trả về element đã bị xóa. Hai method khác nhau cùng tên, và phần gần cuối bài này nói về cái giá bạn phải trả cho chuyện đó.
• indexOf trả về -1 khi không tìm thấy, và list cho phép trùng lặp thoải mái - indexOf tìm cái đầu tiên, lastIndexOf tìm cái cuối cùng.

Toàn bộ tập method gom lại trong một bảng:

contains và indexOf so sánh bằng equals chứ không phải ==, nhờ vậy một List của String mới tìm được giá trị bạn dựng lúc runtime. Những quy tắc mà một class phải tuân theo để chuyện đó chạy đúng còn quan trọng hơn nhiều với collection dựa trên hash, và bài 34 sẽ nói về chúng.

ArrayList thật sự lưu element như thế nào

Bên trong mỗi ArrayList có đúng một field làm việc thật: Object[] elementData. size đếm số ô đang được dùng, còn elementData.length là capacity. Hai con số này gần như không bao giờ bằng nhau.

Bạn không cần tin điều đó một cách suông. Reflection đọc được field này ra khỏi một list đang sống sau mỗi lần add:

import java.lang.reflect.Field;
import java.util.ArrayList;

public class Capacity {
    public static void main(String[] args) throws Exception {
        Field f = ArrayList.class.getDeclaredField("elementData");
        f.setAccessible(true);

        ArrayList<Integer> list = new ArrayList<>();
        int previous = ((Object[]) f.get(list)).length;
        System.out.println("size 0   capacity " + previous);

        for (int i = 1; i <= 200; i++) {
            list.add(i);
            int capacity = ((Object[]) f.get(list)).length;
            if (capacity != previous) {
                System.out.println("size " + list.size() + "  capacity " + previous + " -> " + capacity);
                previous = capacity;
            }
        }
    }
}

Đọc một private field của java.util đòi hỏi mở module ngay trên dòng lệnh, nếu không nó ném InaccessibleObjectException:

java --add-opens java.base/java.util=ALL-UNNAMED Capacity

size 0   capacity 0
size 1  capacity 0 -> 10
size 11  capacity 10 -> 15
size 16  capacity 15 -> 22
size 23  capacity 22 -> 33
size 34  capacity 33 -> 49
size 50  capacity 49 -> 73
size 74  capacity 73 -> 109
size 110  capacity 109 -> 163
size 164  capacity 163 -> 244

Mười dòng đó cho ra ba sự thật.

Một ArrayList mới không cấp phát gì cả. new ArrayList<>() khởi đầu bằng một array rỗng dùng chung. Lần add đầu tiên mới là lúc cấp phát, và nó cấp phát mười ô.

Nó lớn thêm một nửa, không phải gấp đôi. Từ mười trở đi, dãy số là 10, 15, 22, 33, 49, 73, 109, 163, 244, tức là oldCapacity + (oldCapacity >> 1) lặp đi lặp lại - hệ số 1.5, với phép dịch bit làm tròn xuống. Các thanh trong hình trên vẽ đúng tỉ lệ nên hình dạng cấp số nhân nhìn thấy được chứ không phải chỉ nghe kể.

Mỗi lần grow là một lần cấp phát kèm copy. Grow nghĩa là một array mới cộng với việc copy toàn bộ element đang sống sang đó. Đếm số lần copy khi dựng một list 100.000 element bằng cách add liên tục:

Building 100000 elements
  grow() calls                       = 24
  ArrayList.add(e)    element copies = 213413
  copies per element                 = 2.13

Hai mươi bốn lần cấp phát và khoảng 2,1 reference được copy cho mỗi element thêm vào, tính trên toàn bộ quá trình. Đó chính là ý nghĩa thực tế của "amortised constant time": thỉnh thoảng có một lời gọi add đắt, và trung bình vẫn nhỏ vì capacity nhảy thêm một nửa của một con số vốn đã đang lớn dần.

Từ đây có hai cái núm để vặn. Nếu bạn biết đại khái sẽ có bao nhiêu element, new ArrayList<>(100) cấp phát array đúng một lần và bỏ qua cả dãy trên. Và capacity không bao giờ tự nhỏ lại - clear() dọn sạch list nhưng vẫn giữ nguyên array:

after 100 adds: size=100 capacity=109
after clear():  size=0 capacity=109
after trimToSize(): size=0 capacity=0

trimToSize() là thứ duy nhất trả lại bộ nhớ, và hiếm khi đáng gọi.

LinkedList thật sự lưu element như thế nào

LinkedList không lưu gì trong array cả. Mỗi element có một object Node riêng giữ ba reference: chính element đó, node phía trước và node phía sau. Bản thân list giữ reference tới node đầu và node cuối, cộng thêm một biến đếm size.

Cách bố trí đó có đúng một ưu điểm thật và đúng một cái giá thật, cả hai đều mang tính cấu trúc.

Ưu điểm là thêm hoặc xóa ở hai đầu chỉ là vài phép gán pointer, không phải dịch chuyển gì và không bao giờ phải cấp phát lại. Đó là lý do LinkedList đồng thời implement Deque:

import java.util.*;

public class Queue {
    public static void main(String[] args) {
        Deque<String> jobs = new ArrayDeque<>();
        jobs.addLast("build");
        jobs.addLast("test");
        jobs.addFirst("checkout");
        System.out.println("queue: " + jobs);
        while (!jobs.isEmpty()) System.out.println("  running " + jobs.removeFirst());
    }
}

queue: [checkout, build, test]
  running checkout
  running build
  running test

Để ý ví dụ đó khởi tạo class nào. ArrayDeque cũng là một Deque và nó dựa trên một array vòng, và chính javadoc của nó viết rằng class này "likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue". LinkedList là Deque bạn chọn khi cần nó đồng thời là một List.

Cái giá là không có chuyện nhảy thẳng tới index i. Muốn tới một vị trí, LinkedList phải đi theo reference next từng bước một. Implementation có khôn hơn một chút so với đi tuần tự ngây thơ - nó bắt đầu từ đầu nào gần index hơn - nhưng điều đó chỉ giảm quãng đường đi một nửa, chứ không đổi được bản chất của công việc.

ArrayList vs LinkedList: nên chọn cái nào?

Đây là chỗ lời khuyên phổ biến bị sai. Câu "LinkedList insert và delete nhanh hơn" chỉ đúng trong một trường hợp hẹp hơn nhiều so với vẻ ngoài của nó, và sai đúng ở trường hợp mà người ta thường nghĩ tới.

Insert và delete ở giữa list là hai bước chứ không phải một: tìm ra vị trí, rồi thay đổi cấu trúc. LinkedList thắng ở bước thứ hai và thua ở bước thứ nhất, mà với một vị trí ở giữa thì riêng bước thứ nhất đã tốn bằng cả thao tác của ArrayList.

Các con số dưới đây là số thao tác đếm được, không phải thời gian đo được. Một con số đếm thì tái lập lại được trên mọi máy, mọi mức tải, mọi bản JVM; một con số bấm giờ thì không. Chúng đến từ một chương trình tái hiện từng dòng những gì JDK làm - System.arraycopy cho size - index reference với ArrayList.add(int, E), cho (size - 1) - index với ArrayList.remove(int), còn LinkedList.node(int) thì đi từ đầu nào gần index hơn - trên một list 100.000 element:

Đọc dòng thứ tư hai lần. Xóa ở giữa tốn của LinkedList đúng bằng số đếm của ArrayList - nó chỉ tiêu số công đó vào việc đi bộ thay vì copy. Và đi bộ mới là cái đắt hơn trong hai thứ: System.arraycopy là một lần chuyển khối bộ nhớ liền mạch, còn đi theo 49.999 reference next là chạm vào từng ấy object cấp phát riêng lẻ nằm rải rác trong heap, mỗi lần chạm là một khả năng cache miss. Hai dòng bằng nhau trên bảng đếm và không hề bằng nhau trên phần cứng.

Những dòng mà LinkedList thắng thật sự là hai dòng cuối, và cả hai đều nói về hai đầu của list chứ không phải phần giữa.

⚠️ Dòng thứ ba mới là dòng biến một chương trình đang chạy thành một chương trình chậm. Vòng lặp for (int i = 0; i < list.size(); i++) list.get(i) bình thường là tuyến tính trên ArrayList và bậc hai trên LinkedList. Duyệt bằng vòng lặp for nâng cao tránh được hoàn toàn, vì iterator giữ sẵn vị trí thay vì đi lại từ một đầu.

Nên quy tắc thực dụng rất ngắn:

• Mặc định chọn ArrayList. Nó thắng ở truy cập theo index, thắng ở việc nối vào cuối, tốn ít bộ nhớ hơn cho mỗi element, và có locality tốt hơn. Gần như mọi đoạn code làm việc với list trong thực tế đều chỉ nối vào cuối rồi duyệt.
• Chỉ chọn LinkedList khi bạn cần hành vi của Deque - làm việc ở hai đầu, không truy cập theo index - và ngay cả khi đó hãy so nó với ArrayDeque trước.
• Cái "insert rẻ" của LinkedList đòi hỏi bạn đã đang giữ sẵn vị trí. Nghĩa là một Iterator hoặc ListIterator đang đậu đúng chỗ bạn muốn sửa. Nếu code của bạn viết list.add(i, x) hay list.remove(i) thì bạn không giữ vị trí, bạn giữ một index, và cái lượt đi bộ quay trở lại.

Còn một thứ nữa bảng trên không thể hiện: chi phí trên từng element. Mỗi element trong LinkedList là một object Node riêng, có object header và ba reference, cộng thêm chính element đó. ArrayList chỉ lưu một reference cho mỗi element trong một array dùng chung. Với list lớn thì đó là một bội số thật về bộ nhớ, mà bộ nhớ chính là thứ cache được làm ra để chứa.

Duyệt một list

Ba cách, xếp theo thứ tự nên ưu tiên.

List<String> names = new ArrayList<>(List.of("ada", "linus", "grace"));

for (String n : names) {
    System.out.println(n);
}

names.forEach(System.out::println);

for (int i = 0; i < names.size(); i++) {
    System.out.println(i + ": " + names.get(i));
}

Vòng lặp for nâng cao là lựa chọn mặc định. Compiler dịch nó thành một Iterator, nhờ vậy nó chạy được trên mọi Iterable và cũng vì vậy nó an toàn với LinkedList - iterator giữ nguyên vị trí và chỉ đi một bước next mỗi lần. Chỉ dùng vòng lặp theo index khi bạn thật sự cần i, và khi đó nhớ rằng đây là dạng bậc hai trên LinkedList.

Cả contains lẫn indexOf đều là quét tuyến tính trên cả hai implementation, và cả hai đều gọi equals trên các element đang lưu. Đếm số lần gọi thật bằng một class element có equals tăng biến đếm, trên list 1000 phần tử:

ArrayList size 1000
  first   indexOf -> 0, equals() calls = 1
  middle  indexOf -> 500, equals() calls = 501
  last    indexOf -> 999, equals() calls = 1000
  missing indexOf -> -1, equals() calls = 1000
LinkedList size 1000
  first   indexOf -> 0, equals() calls = 1
  middle  indexOf -> 500, equals() calls = 501
  last    indexOf -> 999, equals() calls = 1000
  missing indexOf -> -1, equals() calls = 1000

Giống hệt nhau, và đều tỉ lệ với vị trí. List là structure sai cho câu hỏi "giá trị này có trong đây không" khi list lớn và câu hỏi được hỏi thường xuyên - đó là việc của bài 34.

Xóa element trong lúc đang duyệt

Xóa khỏi list ngay trong lúc duyệt nó là cách phổ biến nhất để làm hỏng code làm việc với list. Đoạn này ném exception:

import java.util.*;

public class Cme {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("ada", "linus", "grace", "ken"));
        for (String n : names) {
            if (n.startsWith("l")) {
                names.remove(n);
            }
        }
        System.out.println(names);
    }
}

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1095)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1049)
	at Cme.main(Cme.java:6)

Để ý cái frame ở giữa: ArrayList$Itr.next. Chương trình này không có thread nào cả, và chẳng có gì concurrent ở đây. Cái tên nói tới việc sửa list trong khi một iterator trên nó còn sống, mà đó đúng là điều vòng lặp for nâng cao đang làm thay bạn.

Cơ chế nằm ở hai số nguyên. List giữ modCount, tăng lên sau mỗi thay đổi cấu trúc. Iterator copy giá trị đó vào expectedModCount lúc nó được tạo ra, rồi so hai số ở mỗi lần next(). Cả hai field đều đọc được bằng reflection, và điều đó làm mọi thứ trở nên cụ thể:

1 names.iterator()        modCount=0 expected=0
2 it.next() -> ada        modCount=0 expected=0
3 names.remove("ada")     modCount=1 expected=0
4 it.next()               throws ConcurrentModificationException

1 ok.iterator()           modCount=0 expected=0
2 j.next() -> ada         modCount=0 expected=0
3 j.remove()              modCount=1 expected=1
4 j.next() -> linus       modCount=1 expected=1

Iterator.remove() tăng modCount rồi copy ngược giá trị mới vào expectedModCount, nên hai số luôn khớp nhau. Xóa qua list thì chỉ làm nửa đầu mà bỏ nửa sau. LinkedList hành xử y hệt, chỉ khác tên class iterator trong stack trace:

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:977)
	at java.base/java.util.LinkedList$ListItr.next(LinkedList.java:899)
	at LlCme.main(LlCme.java:6)

Hai trường hợp không ném exception nhưng vẫn sai

Phép kiểm tra nằm bên trong next() chứ không nằm trong hasNext(). Nên xóa element áp chót sẽ kết thúc vòng lặp sớm một cách im lặng:

List<String> quiet = new ArrayList<>(List.of("a", "b", "c", "d"));
for (String s : quiet) if (s.equals("c")) quiet.remove(s);
System.out.println(quiet);

[a, b, d]

Trường hợp này tình cờ cho ra kết quả đúng, thuần túy do may: sau khi xóa thì size bằng 3 và con trỏ cũng bằng 3, nên hasNext() trả về false và next() không bao giờ được gọi nữa. Đổi dữ liệu một chút là nó ném exception ngay.

Trường hợp còn lại là vòng lặp theo index, vốn không dính tới iterator nên không bao giờ ném exception - nó chỉ bỏ sót element:

List<String> skip = new ArrayList<>(List.of("ada", "linus", "lisa", "grace", "ken"));
for (int i = 0; i < skip.size(); i++) {
    if (skip.get(i).startsWith("l")) skip.remove(i);
}
System.out.println(skip);

[ada, lisa, grace, ken]

Xóa index 1 làm lisa tụt xuống index 1, rồi i++ nhảy thẳng qua nó sang index 2. Element nào đứng ngay sau một element vừa bị xóa cũng đều bị bỏ sót, nên lisa sống sót qua một bộ lọc lẽ ra phải xóa nó.

Bốn cách làm đúng

// 1. removeIf - ngắn nhất, và là lựa chọn nên dùng
list.removeIf(s -> s.startsWith("l"));

// 2. Iterator.remove - khi điều kiện cần nhiều hơn một predicate
for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
    if (it.next().startsWith("l")) it.remove();
}

// 3. duyệt index từ cuối về đầu, để việc xóa không làm dịch element chưa duyệt
for (int i = list.size() - 1; i >= 0; i--) {
    if (list.get(i).startsWith("l")) list.remove(i);
}

// 4. dựng một list mới và giữ nguyên list gốc
List<String> kept = new ArrayList<>();
for (String s : list) if (!s.startsWith("l")) kept.add(s);

Cả bốn cách đều biến [ada, linus, lisa, grace, ken] thành [ada, grace, ken]. removeIf gọi predicate đúng một lần cho mỗi element - đã kiểm bằng cách đếm, năm lần cho list năm phần tử - và chỉ cập nhật modCount một lần, sau khi duyệt xong.

List của Integer: autoboxing và cái bẫy remove

List chỉ chứa object, nên một list số là List của Integer. Autoboxing giấu phép chuyển đổi ở cả hai chiều:

List<Integer> scores = new ArrayList<>();
scores.add(90);            // autoboxed: Integer.valueOf(90)
scores.add(85);
int first = scores.get(0); // unboxed: first.intValue()
System.out.println("first + 5 = " + (first + 5));
System.out.println("element class = " + scores.get(0).getClass().getName());

first + 5 = 95
element class = java.lang.Integer

Tiện, và hầu như vô hình - cho tới khi có một element là null. Một reference Integer có thể là null; một int thì không, nên phép unbox thất bại:

unboxing null threw java.lang.NullPointerException
  message: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.List.get(int)" is null

remove(int) và remove(Object)

Giờ tới cái bẫy. List khai báo hai method remove: remove(int index) và remove(Object o). Trên List của String thì không đời nào nhầm được. Trên List của Integer thì chúng đụng nhau, và compiler chọn đúng cái bạn không định gọi:

import java.util.*;

public class RemoveTrap {
    public static void main(String[] args) {
        List<Integer> ids = new ArrayList<>(List.of(10, 20, 30, 40));

        List<Integer> a = new ArrayList<>(ids);
        a.remove(2);
        System.out.println("remove(2)                  -> " + a);

        List<Integer> b = new ArrayList<>(ids);
        b.remove(Integer.valueOf(20));
        System.out.println("remove(Integer.valueOf(20))-> " + b);

        List<Integer> c = new ArrayList<>(ids);
        System.out.println("remove(Object 20) returned " + c.remove((Object) 20) + " -> " + c);

        List<Integer> d = new ArrayList<>(ids);
        try {
            d.remove(20);
        } catch (IndexOutOfBoundsException e) {
            System.out.println("remove(20) threw " + e);
        }
    }
}

remove(2)                  -> [10, 20, 40]
remove(Integer.valueOf(20))-> [10, 30, 40]
remove(Object 20) returned true -> [10, 30, 40]
remove(20) threw java.lang.IndexOutOfBoundsException: Index 20 out of bounds for length 4

a.remove(2) đã xóa 30, tức element ở index 2. Nó không hề đi tìm giá trị 2. Overload resolution ưu tiên method không cần boxing, nên một literal int luôn chọn remove(int), và compiler không hề cảnh báo - cả hai overload đều hợp lệ và một cái khớp tốt hơn.

Cách sửa là làm cho argument trở thành một Object để overload còn lại được chọn. remove(Integer.valueOf(20)) là dạng rõ ràng nhất; ép kiểu remove((Object) 20) cũng chạy. Còn khi index vượt phạm vi, như trường hợp cuối, thì ít nhất bạn nhận được một exception thay vì một lần xóa nhầm im lặng - đó là phiên bản may mắn của con bug này.

Chuyện identity của Integer

Thêm một chi tiết về autoboxing đáng biết khi làm việc với List của Integer:

127 == 127 (Integer) : true
128 == 128 (Integer) : false
indexOf(128) = 1 (indexOf uses equals, not ==)

Integer.valueOf cache khoảng từ -128 tới 127, nên các giá trị boxed nhỏ tình cờ bằng nhau khi so bằng ==, còn giá trị lớn hơn thì không. Các method của list không bị ảnh hưởng vì tất cả đều dùng equals. Code của bạn thì có: đừng bao giờ so sánh giá trị boxed bằng ==.

List.of và Arrays.asList không phải là ArrayList

Hai câu lệnh một dòng cực kỳ phổ biến lại tạo ra những list không giống điều người ta tưởng.

import java.util.*;

public class Immutable {
    public static void main(String[] args) {
        List<String> of = List.of("a", "b", "c");
        System.out.println("List.of class      = " + of.getClass().getName());

        String[] arr = {"a", "b", "c"};
        List<String> asList = Arrays.asList(arr);
        System.out.println("Arrays.asList class = " + asList.getClass().getName());
        asList.set(0, "z");
        System.out.println("after set: list " + asList + ", backing array " + Arrays.toString(arr));
    }
}

List.of class      = java.util.ImmutableCollections$ListN
Arrays.asList class = java.util.Arrays$ArrayList
after set: list [z, b, c], backing array [z, b, c]

Không cái nào là java.util.ArrayList. Đây là những gì mỗi cái từ chối:

List.of bất biến hoàn toàn, và nó từ chối null quyết liệt tới mức ngay cả contains(null) cũng ném NullPointerException. Arrays.asList thì cố định kích thước chứ không bất biến: nó là một view mỏng đặt lên chính array bạn truyền vào, nên set chạy được và ghi thẳng xuống array, đúng như output ở trên.

Khi bạn muốn một list thật sự thay đổi được từ một danh sách viết sẵn, hãy bọc nó lại:

List<String> copy = new ArrayList<>(List.of("a", "b", "c"));
copy.add("d");
System.out.println(copy);

[a, b, c, d]

Đó là idiom cần thuộc. List.of cho hằng số không bao giờ sửa; new ArrayList<>(List.of(...)) cho mọi trường hợp còn lại.

FAQ

size và capacity khác nhau ở đâu?

size() là số element list đang giữ và là một phần của interface List. Capacity là elementData.length bên trong ArrayList, không lộ ra qua bất kỳ method public nào, và luôn lớn hơn hoặc bằng size(). LinkedList không có capacity: nó cấp phát một node cho mỗi element và không dư ra gì cả.

ArrayList hay LinkedList nhanh hơn?

ArrayList, cho gần như mọi việc code thật sự làm. Nó thắng tuyệt đối ở truy cập theo index, thắng ở việc nối vào cuối, tốn ít bộ nhớ hơn cho mỗi element, và các element nằm liền nhau nên cache của CPU làm việc giúp bạn chứ không chống lại bạn. LinkedList chỉ thắng khi bạn làm việc ở hai đầu mà không cần index, hoặc khi bạn đã giữ sẵn một Iterator đặt đúng chỗ cần sửa - và với vế đầu thì ArrayDeque thường mới là câu trả lời đúng.

Vì sao remove(1) lại xóa nhầm element trong list Integer?

Vì nó không phải method bạn nghĩ mình đang gọi. remove(1) với một literal int sẽ khớp vào remove(int index) và xóa element ở index 1. Muốn xóa giá trị 1, phải ép chọn overload còn lại: remove(Integer.valueOf(1)).

ArrayList có thread-safe không?

Không. LinkedList cũng không. Hai thread cùng sửa có thể làm hỏng trạng thái bên trong, và ConcurrentModificationException chỉ là một phép kiểm tra nỗ lực-tối-đa cho trường hợp một thread, chứ không phải bảo đảm cho trường hợp nhiều thread. Collections.synchronizedList(...) và các class trong java.util.concurrent mới là câu trả lời, và chúng thuộc về một khóa học sau.

Một list có chứa được nhiều kiểu dữ liệu khác nhau không?

Một List của Object thì được:

List<Object>          -> [text, 42, 3.5]
  String text
  Integer 42
  Double 3.5

Nó hợp lệ, và gần như luôn là một lỗi thiết kế - bạn mất sạch bảo đảm ở compile time và phải ép kiểu ở đầu ra. Hãy mô hình hóa dữ liệu bằng một class cho đàng hoàng.

Sắp xếp một list như thế nào?

list.sort(null) sắp theo thứ tự tự nhiên, list.sort(Comparator.reverseOrder()) đảo ngược lại, còn Collections.sort(list) là dạng cũ tương đương cái đầu tiên:

sort(null)            -> [ada, grace, linus]
reverseOrder          -> [linus, grace, ada]

Sắp xếp sửa trực tiếp trên list, nên nó thất bại với List.of.

Kết luận

ArrayList và LinkedList là hai cách hiện thực hóa cùng một hợp đồng List, và lựa chọn giữa chúng lệch hẳn về một bên chứ không cân bằng như thường được trình bày. ArrayList giữ mọi element trong một array, tăng thêm một nửa mỗi khi đầy, và tới được bất kỳ index nào chỉ bằng một lần đọc. LinkedList giữ một node cho mỗi element, khiến hai đầu rất rẻ còn mọi vị trí ở giữa thì đắt để tìm. Hãy khai báo List, khởi tạo ArrayList, và chỉ rời khỏi lựa chọn đó khi bạn có một lý do cụ thể ở hai đầu của list.

Phần còn lại là thói quen: dùng vòng lặp for nâng cao, dùng removeIf hoặc Iterator.remove khi cần xóa trong lúc duyệt, nhớ rằng remove(1) trên list Integer là một vị trí chứ không phải một giá trị, và nhớ rằng List.of là bất biến còn Arrays.asList chỉ là cố định kích thước.

Bài 34 chuyển từ vị trí sang key với HashMap - Map lưu entry ra sao, vì sao tra cứu không cần quét, và hợp đồng hashCode với equals giúp chuyện đó thành hiện thực.