List Interface

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

Sau bài này, bạn sẽ:

• Hiểu List interface - collection có thứ tự, cho phép duplicates, có index-based access
• So sánh ArrayList vs LinkedList về cấu trúc, performance (O(1) vs O(n)), và use cases
• Thành thạo các operations: add, get, set, remove, indexOf, subList
• Biết các cách iteration: for, for-each, Iterator, ListIterator, forEach, Stream
• Phân biệt List.of(), Arrays.asList(), Collections.unmodifiableList()

Bài trước: Giới thiệu Collections Framework — Đã học về Collections hierarchy và lý do dùng Collections. Bài này sẽ đi sâu vào List interface và hai implementation phổ biến: ArrayList và LinkedList.

List Interface là gì?

List là một interface trong Collections Framework đại diện cho một tập hợp có thứ tự (ordered) các phần tử, cho phép:

• Ordered: Duy trì thứ tự thêm vào (insertion order)
• Duplicates allowed: Cho phép các phần tử trùng lặp
• Index-based access: Truy cập phần tử qua chỉ số (0, 1, 2, ...)
• Positional access: Thêm/xóa/sửa phần tử ở vị trí cụ thể

public interface List<E> extends Collection<E> {
    // Positional access
    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);

    // Search
    int indexOf(Object o);
    int lastIndexOf(Object o);

    // Range-view
    List<E> subList(int fromIndex, int toIndex);

    // List iterator
    ListIterator<E> listIterator();
}

ArrayList - Dynamic Array

ArrayList là implementation phổ biến nhất của List, sử dụng mảng động (dynamic array) bên trong.

Đặc điểm

• Dựa trên mảng động, tự động mở rộng khi đầy
• Random access nhanh: O(1) để truy cập phần tử qua index
• Thêm vào cuối nhanh: O(1) amortized
• Thêm/xóa ở giữa chậm: O(n) do phải shift các phần tử
• Không thread-safe

import java.util.*;

public class ArrayListDemo {
    public static void main(String[] args) {
        // Khởi tạo
        List<String> fruits = new ArrayList<>();  // Initial capacity = 10
        List<String> fruitsWithCapacity = new ArrayList<>(100);  // Custom capacity
        List<String> fruitsFromCollection = new ArrayList<>(Arrays.asList("Apple", "Banana"));

        // Thêm phần tử
        fruits.add("Apple");           // Thêm vào cuối
        fruits.add("Banana");
        fruits.add("Cherry");
        fruits.add(1, "Avocado");      // Thêm vào index 1
        // Kết quả: [Apple, Avocado, Banana, Cherry]

        // Truy cập phần tử
        String first = fruits.get(0);   // "Apple"
        String second = fruits.get(1);  // "Avocado"

        // Sửa phần tử
        fruits.set(1, "Apricot");      // Thay "Avocado" bằng "Apricot"

        // Xóa phần tử
        fruits.remove(0);               // Xóa theo index
        fruits.remove("Banana");        // Xóa theo object
        // Kết quả: [Apricot, Cherry]

        // Tìm kiếm
        int index = fruits.indexOf("Cherry");     // 1
        boolean contains = fruits.contains("Apple");  // false

        // Kích thước
        int size = fruits.size();      // 2
        boolean isEmpty = fruits.isEmpty();  // false

        System.out.println(fruits);
    }
}

Performance của ArrayList

Operation	Time Complexity	Note
get(index)	O(1)	Random access
add(element)	O(1) amortized	Có thể O(n) khi resize
add(index, element)	O(n)	Phải shift các phần tử
remove(index)	O(n)	Phải shift các phần tử
contains(object)	O(n)	Linear search
indexOf(object)	O(n)	Linear search

Capacity Planning

ArrayList có initial capacity mặc định là 10. Khi đầy, nó tự động tăng kích thước lên 50% (capacity mới = capacity cũ * 1.5).

Nếu biết trước số lượng phần tử, nên khởi tạo với capacity phù hợp:

// Tốt: tránh resize nhiều lần
List<String> bigList = new ArrayList<>(10000);

// Không tốt: resize nhiều lần từ 10 → 15 → 22 → ... → 10000+
List<String> bigList = new ArrayList<>();

ArrayList Internal Growth - Công thức chính xác

ArrayList không mở rộng gấp đôi (2x) như nhiều người nghĩ, mà mở rộng 1.5x:

Công thức thực tế trong source code:

// Từ ArrayList.java source code
int newCapacity = oldCapacity + (oldCapacity >> 1);

Tại sao dùng right shift >> 1?

oldCapacity >> 1 = chia 2 (sử dụng bit shift, nhanh hơn chia thông thường)

Ví dụ:

• oldCapacity = 10
• oldCapacity >> 1 = 5 (10 / 2)
• newCapacity = 10 + 5 = 15

// Demo ArrayList growth
List<Integer> list = new ArrayList<>();  // capacity = 10
for (int i = 0; i < 100; i++) {
    list.add(i);
    // Resize xảy ra ở: 10, 15, 22, 33, 49, 73, 109...
}

// Visualization of capacity growth
System.out.println("Capacity growth: 10 → 15 → 22 → 33 → 49 → 73 → 109");

// Với initial capacity phù hợp:
List<Integer> efficientList = new ArrayList<>(100);
for (int i = 0; i < 100; i++) {
    efficientList.add(i);  // Không resize!
}

Tại sao 1.5x thay vì 2x?

• 1.5x: Cân bằng giữa memory overhead và số lần resize
• 2x: Tốn memory hơn (capacity lớn quá nhanh)
• 1.25x: Phải resize nhiều hơn (overhead)

📖 Theo Oracle Docs

ArrayList capacity tăng theo factor 1.5 (50%) mỗi lần resize. Đây là compromise tốt giữa memory efficiency và số lần copy operations.

ArrayList vs LinkedList Internal Structure

So sánh:

• ArrayList: Mảng liên tục, random access O(1), insert/delete ở giữa O(n)
• LinkedList: Nodes với pointers, sequential access O(n), insert/delete ở đầu/cuối O(1)

ArrayList Internal Structure Diagram

Sơ đồ minh họa cách ArrayList lưu trữ và mở rộng:

LinkedList - Doubly-Linked List

LinkedList là implementation dựa trên danh sách liên kết đôi (doubly-linked list).

Đặc điểm

• Mỗi node chứa data và 2 con trỏ (prev, next)
• Thêm/xóa đầu/cuối nhanh: O(1)
• Thêm/xóa ở giữa: O(n) để tìm vị trí, O(1) để thêm/xóa
• Random access chậm: O(n) do phải traverse từ đầu hoặc cuối
• Tốn bộ nhớ hơn: mỗi node cần thêm 2 con trỏ
• Implements cả List và Deque

import java.util.*;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        // List operations
        list.add("B");
        list.add("C");
        list.add(0, "A");    // Thêm vào đầu
        list.add("D");
        // Kết quả: [A, B, C, D]

        // Deque operations (đầu và cuối)
        list.addFirst("Start");   // Thêm vào đầu
        list.addLast("End");      // Thêm vào cuối
        // Kết quả: [Start, A, B, C, D, End]

        String first = list.getFirst();   // "Start"
        String last = list.getLast();     // "End"

        list.removeFirst();    // Xóa đầu
        list.removeLast();     // Xóa cuối
        // Kết quả: [A, B, C, D]

        // Queue operations
        list.offer("E");       // Thêm vào cuối (như add)
        String head = list.poll();  // Lấy và xóa phần tử đầu: "A"
        String peek = list.peek();  // Xem phần tử đầu không xóa: "B"

        System.out.println(list);
    }
}

Performance của LinkedList

Operation	Time Complexity	Note
get(index)	O(n)	Phải traverse danh sách
add(element)	O(1)	Thêm vào cuối
add(index, element)	O(n)	O(n) để tìm, O(1) để thêm
addFirst/addLast	O(1)	Direct access đầu/cuối
remove(index)	O(n)	O(n) để tìm, O(1) để xóa
removeFirst/removeLast	O(1)	Direct access đầu/cuối

ArrayList vs LinkedList - So sánh chi tiết

Đặc điểm	ArrayList	LinkedList
Cấu trúc	Dynamic array	Doubly-linked list
Memory	Compact, ít overhead	Nhiều overhead (2 pointers/node)
Random access	O(1) - Rất nhanh	O(n) - Chậm
Add/remove ở cuối	O(1) amortized	O(1) - Rất nhanh
Add/remove ở đầu	O(n) - Chậm	O(1) - Rất nhanh
Add/remove ở giữa	O(n) - Chậm	O(n) - Chậm
Search	O(n)	O(n)
Iterator remove	Slow (shift required)	Fast (O(1))
Cache locality	Tốt (contiguous memory)	Kém (scattered nodes)
Use case	Đọc nhiều, truy cập ngẫu nhiên	Thêm/xóa đầu/cuối nhiều

Khi nào dùng ArrayList?

// ✅ TỐT: Truy cập ngẫu nhiên nhiều
List<User> users = new ArrayList<>();
User user = users.get(500);  // O(1)

// ✅ TỐT: Thêm vào cuối nhiều
List<String> logs = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    logs.add("Log entry " + i);  // O(1) amortized
}

// ✅ TỐT: Iteration đơn giản
for (String log : logs) {
    System.out.println(log);  // Cache-friendly
}

// ❌ KHÔNG TỐT: Thêm vào đầu nhiều
for (int i = 0; i < 10000; i++) {
    list.add(0, "Item " + i);  // O(n) mỗi lần!
}

Khi nào dùng LinkedList?

// ✅ TỐT: Thêm/xóa đầu và cuối
LinkedList<Task> queue = new LinkedList<>();
queue.addFirst(urgentTask);   // O(1)
queue.addLast(normalTask);    // O(1)
Task next = queue.removeFirst();  // O(1)

// ✅ TỐT: Implement Queue hoặc Deque
Queue<String> fifoQueue = new LinkedList<>();
Deque<String> deque = new LinkedList<>();

// ✅ TỐT: Xóa trong khi iterate
Iterator<String> iter = linkedList.iterator();
while (iter.hasNext()) {
    String item = iter.next();
    if (shouldRemove(item)) {
        iter.remove();  // O(1) với LinkedList
    }
}

// ❌ KHÔNG TỐT: Random access
String item = linkedList.get(5000);  // O(n) - rất chậm!

Trong thực tế

99% trường hợp, ArrayList là lựa chọn tốt hơn LinkedList!

LinkedList chỉ tốt hơn khi bạn thực sự cần thêm/xóa đầu danh sách liên tục. Ngay cả với thêm/xóa ở giữa, ArrayList thường vẫn nhanh hơn vì cache locality tốt.

Common Operations trên List

1. Thêm và xóa phần tử

List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));

// Thêm
list.add("D");                    // [A, B, C, D]
list.add(1, "X");                 // [A, X, B, C, D]
list.addAll(Arrays.asList("E", "F"));  // [A, X, B, C, D, E, F]

// Xóa
list.remove(1);                   // Xóa index 1: [A, B, C, D, E, F]
list.remove("E");                 // Xóa object "E": [A, B, C, D, F]
list.removeAll(Arrays.asList("A", "F"));  // [B, C, D]
list.clear();                     // []

2. Truy cập và tìm kiếm

List<String> fruits = new ArrayList<>(Arrays.asList("Apple", "Banana", "Cherry", "Banana"));

// Truy cập
String first = fruits.get(0);     // "Apple"
String last = fruits.get(fruits.size() - 1);  // "Banana"

// Tìm kiếm
int index = fruits.indexOf("Banana");      // 1 (first occurrence)
int lastIndex = fruits.lastIndexOf("Banana");  // 3 (last occurrence)
boolean has = fruits.contains("Cherry");   // true

// Sửa
fruits.set(2, "Coconut");        // [Apple, Banana, Coconut, Banana]

3. SubList - View của List

SubList VIEW Behavior Diagram

Lưu ý: SubList là VIEW, không phải copy. Modifications propagate, nhưng structural changes làm invalidate view!

List<Integer> numbers = new ArrayList<>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));

// SubList là VIEW, không phải copy!
List<Integer> subList = numbers.subList(2, 7);  // [2, 3, 4, 5, 6] (fromIndex inclusive, toIndex exclusive)
System.out.println(subList);  // [2, 3, 4, 5, 6]

// Thay đổi subList ảnh hưởng đến list gốc
subList.set(0, 99);
System.out.println(numbers);  // [0, 1, 99, 3, 4, 5, 6, 7, 8, 9]

// Xóa trong subList
subList.clear();
System.out.println(numbers);  // [0, 1, 7, 8, 9]

SubList Structural Change Breaks View

Structural change (add/remove) trên parent list (KHÔNG qua subList) sẽ invalidate subList:

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
List<Integer> sub = list.subList(1, 4);  // [2, 3, 4]

// Structural change trên parent (bypass subList)
list.add(6);  // Thêm vào parent trực tiếp

// SubList bị invalidate → Exception!
try {
    sub.get(0);  // ConcurrentModificationException!
} catch (ConcurrentModificationException e) {
    System.out.println("SubList invalidated after parent structural change");
}

// ✅ CÁCH TRÁNH: Tạo independent copy
List<Integer> subCopy = new ArrayList<>(list.subList(1, 4));
list.add(7);  // Không ảnh hưởng subCopy
System.out.println(subCopy);  // [2, 3, 4] - unchanged

Tại sao subList là view?

• Performance: Tránh copy data khi chỉ cần thao tác trên range
• Use case: Bulk operations trên một phần của list

  list.subList(2, 5).clear();  // Xóa phần tử từ index 2-4
  list.subList(0, 10).replaceAll(String::toUpperCase);  // Uppercase 10 phần tử đầu

💡 Cách nhớ: SubList = "Cửa sổ nhìn vào nhà"

SubList giống cửa sổ nhìn vào căn nhà (parent list). Bạn có thể sắp xếp đồ trong nhà qua cửa sổ (modify via subList). Nhưng nếu ai đó phá tường nhà (structural change on parent), cửa sổ sẽ bị hỏng (invalidated)!

Fail-Fast trong For-Each Loop

For-each loop tạo Iterator ngầm. Khi modify collection trực tiếp (không qua Iterator), ConcurrentModificationException xảy ra:

List<String> fruits = new ArrayList<>(Arrays.asList("Apple", "Banana", "Cherry", "Date"));

// ❌ SAI: Modify trong for-each
try {
    for (String fruit : fruits) {
        if (fruit.startsWith("C")) {
            fruits.remove(fruit);  // External modification!
        }
    }
} catch (ConcurrentModificationException e) {
    System.out.println("Caught: " + e.getClass().getSimpleName());
    // Output: Caught: ConcurrentModificationException
}

// ✅ ĐÚNG: Dùng Iterator.remove()
fruits = new ArrayList<>(Arrays.asList("Apple", "Banana", "Cherry", "Date"));
Iterator<String> iter = fruits.iterator();
while (iter.hasNext()) {
    String fruit = iter.next();
    if (fruit.startsWith("C")) {
        iter.remove();  // Safe removal
    }
}
System.out.println(fruits);  // Output: [Apple, Banana, Date]

For-each loop được compiler convert thành:

// Code bạn viết:
for (String fruit : fruits) {
    fruits.remove(fruit);  // Dangerous!
}

// Compiler tạo ra:
Iterator<String> iter = fruits.iterator();
while (iter.hasNext()) {
    String fruit = iter.next();
    fruits.remove(fruit);  // Modify qua list, không qua iterator
    // → modCount++ nhưng iter.expectedModCount không đổi
    // → next() call: if (modCount != expectedModCount) throw CME!
}

ListIterator vs Iterator

ListIterator là iterator đặc biệt cho List, có thể duyệt 2 chiều và modify safely:

List<String> names = new ArrayList<>(Arrays.asList("Alice", "Bob", "Charlie", "David"));
ListIterator<String> listIter = names.listIterator();

// Forward iteration với index tracking
System.out.println("Forward:");
while (listIter.hasNext()) {
    int index = listIter.nextIndex();
    String name = listIter.next();
    System.out.println(index + ": " + name);

    // set() - Thay thế phần tử vừa next()
    if (name.equals("Bob")) {
        listIter.set("Robert");
    }

    // add() - Thêm AFTER current position
    if (name.equals("Charlie")) {
        listIter.add("Chuck");
    }
}
// Output:
// 0: Alice
// 1: Bob
// 2: Charlie
// 3: David

System.out.println("\nAfter modifications: " + names);
// Output: [Alice, Robert, Charlie, Chuck, David]

// Backward iteration
System.out.println("\nBackward:");
while (listIter.hasPrevious()) {
    int index = listIter.previousIndex();
    String name = listIter.previous();
    System.out.println(index + ": " + name);
}
// Output:
// 4: David
// 3: Chuck
// 2: Charlie
// 1: Robert
// 0: Alice

Comparison Table:

Feature	Iterator	ListIterator
Direction	Forward only	Bidirectional (forward + backward)
Methods	hasNext(), next(), remove()	+ hasPrevious(), previous(), nextIndex(), previousIndex()
Modification	Remove only	remove(), set(), add()
Index access	No	nextIndex(), previousIndex()
Collections	All Collections	List only
Safe modification	✅ remove() updates modCount	✅ All methods update modCount

📖 Theo JLS: ListIterator modifications are safe

ListIterator.set() và add() được thiết kế để safe during iteration. Chúng tự động update expectedModCount của iterator, nên không gây ConcurrentModificationException. Đây là sự khác biệt quan trọng so với list.add() trực tiếp.

List.of() vs Arrays.asList() vs new ArrayList<>()

Ba cách tạo List với behavior khác nhau hoàn toàn:

So sánh:

• List.of(): Immutable, không null, nhanh nhất
• Arrays.asList(): Fixed-size, backed by array, thay đổi array → list cũng đổi
• new ArrayList(): Fully mutable, independent copy, use case phổ biến nhất

// 1. List.of() - Truly immutable (Java 9+)
List<String> list1 = List.of("A", "B", "C");
// list1.add("D");       // ❌ UnsupportedOperationException
// list1.set(0, "X");    // ❌ UnsupportedOperationException
// list1.remove(0);      // ❌ UnsupportedOperationException
System.out.println(list1);  // Output: [A, B, C]

// Null không được phép
// List<String> withNull = List.of("A", null);  // ❌ NullPointerException

// 2. Arrays.asList() - Fixed-size, backed by array
String[] array = {"A", "B", "C"};
List<String> list2 = Arrays.asList(array);
list2.set(0, "X");      // ✅ OK - can set
System.out.println(list2);  // Output: [X, B, C]

// list2.add("D");      // ❌ UnsupportedOperationException - cannot add/remove
// list2.remove(0);     // ❌ UnsupportedOperationException

// ⚠️ NGUY HIỂM: Backed by array, thay đổi array → ảnh hưởng list
array[1] = "Y";
System.out.println(list2);  // Output: [X, Y, C] - changed!

// 3. new ArrayList<>() - Fully mutable
List<String> list3 = new ArrayList<>(Arrays.asList("A", "B", "C"));
list3.add("D");         // ✅ OK
list3.set(0, "X");      // ✅ OK
list3.remove(0);        // ✅ OK
list3.add(null);        // ✅ OK - allows null
System.out.println(list3);  // Output: [B, C, D, null]

Comprehensive Comparison Table:

Feature	List.of()	Arrays.asList()	new ArrayList<>()
Java version	9+	1.2+	1.2+
Mutability	Immutable	Fixed-size	Fully mutable
add/remove	❌ Exception	❌ Exception	✅ OK
set(index, elem)	❌ Exception	✅ OK	✅ OK
Null elements	❌ NullPointerException	✅ OK	✅ OK
Backed by	Internal array (immutable)	External array	Own array
Changes propagate	N/A	✅ From array to list	❌ Independent
Performance	Best (immutable)	Good	Good
Use case	Constants, config	Quick array→list wrapper	General mutable list

🔥 Bẫy OCP: Arrays.asList() pitfalls

// Trap 1: Fixed size
List<Integer> list = Arrays.asList(1, 2, 3);
list.add(4);  // ❌ UnsupportedOperationException

// Trap 2: Backed by array
String[] arr = {"A", "B", "C"};
List<String> list = Arrays.asList(arr);
arr[0] = "X";
System.out.println(list.get(0));  // Output: "X" - changed!

// Trap 3: Primitive array pitfall
int[] nums = {1, 2, 3};
List<int[]> wrong = Arrays.asList(nums);  // ❌ List of ONE array, not integers!
System.out.println(wrong.size());  // Output: 1 (not 3!)

// Correct:
Integer[] nums = {1, 2, 3};
List<Integer> correct = Arrays.asList(nums);
System.out.println(correct.size());  // Output: 3

4. Immutable List với List.of() (Java 9+)

// Tạo immutable list
List<String> immutableList = List.of("A", "B", "C");

// Không thể thay đổi
// immutableList.add("D");        // UnsupportedOperationException
// immutableList.remove(0);       // UnsupportedOperationException
// immutableList.set(0, "X");     // UnsupportedOperationException

// Không chứa null
// List<String> withNull = List.of("A", null);  // NullPointerException

// Immutable nhưng có thể gán lại biến
immutableList = List.of("X", "Y", "Z");  // OK

List.of() vs Arrays.asList() vs Collections.unmodifiableList()

// Arrays.asList() - fixed-size, có thể set() nhưng không add/remove
List<String> list1 = Arrays.asList("A", "B", "C");
list1.set(0, "X");  // OK
// list1.add("D");  // UnsupportedOperationException

// List.of() - truly immutable, không thể thay đổi gì
List<String> list2 = List.of("A", "B", "C");
// list2.set(0, "X");  // UnsupportedOperationException

// Collections.unmodifiableList() - wrapper unmodifiable
List<String> mutableList = new ArrayList<>(Arrays.asList("A", "B"));
List<String> list3 = Collections.unmodifiableList(mutableList);
// list3.add("C");  // UnsupportedOperationException
mutableList.add("C");  // OK, ảnh hưởng đến list3!
System.out.println(list3);  // [A, B, C]

Iteration - Các cách duyệt List

1. For-each loop (Enhanced for)

List<String> names = Arrays.asList("Alice", "Bob", "Charlie");

for (String name : names) {
    System.out.println(name);
}
// Không có index, không thể remove

2. Traditional for loop

for (int i = 0; i < names.size(); i++) {
    String name = names.get(i);
    System.out.println(i + ": " + name);
}
// Có index, có thể remove nhưng phải cẩn thận

3. Iterator

Iterator<String> iter = names.iterator();
while (iter.hasNext()) {
    String name = iter.next();
    System.out.println(name);
    if (name.equals("Bob")) {
        iter.remove();  // Safe remove trong khi iterate
    }
}

4. ListIterator (chỉ có trong List)

ListIterator<String> listIter = names.listIterator();

// Forward iteration
while (listIter.hasNext()) {
    int index = listIter.nextIndex();
    String name = listIter.next();
    System.out.println(index + ": " + name);

    // Có thể thêm/sửa/xóa
    if (name.equals("Bob")) {
        listIter.set("Robert");  // Sửa
        listIter.add("Bobby");   // Thêm sau vị trí hiện tại
    }
}

// Backward iteration
while (listIter.hasPrevious()) {
    String name = listIter.previous();
    System.out.println(name);
}

5. forEach với Lambda (Java 8+)

names.forEach(name -> System.out.println(name));

// Hoặc method reference
names.forEach(System.out::println);

6. Stream API (Java 8+)

names.stream()
     .filter(name -> name.startsWith("A"))
     .map(String::toUpperCase)
     .forEach(System.out::println);

OCP Traps - Bẫy thường gặp trong kỳ thi

🔥 Bẫy 1: List.of() không cho phép modification

List<String> list = List.of("A", "B", "C");
list.add("D");  // ❌ UnsupportedOperationException - immutable!

Giải thích: List.of() tạo truly immutable list. Mọi attempt to modify đều throw exception.

🔥 Bẫy 2: Arrays.asList() là fixed-size

List<Integer> nums = Arrays.asList(1, 2, 3);
nums.add(4);     // ❌ UnsupportedOperationException - fixed size!
nums.set(0, 10); // ✅ OK - set() works

Giải thích: Arrays.asList() trả về fixed-size list backed by array. Có thể set() nhưng không thể add()/remove().

🔥 Bẫy 3: LinkedList.get(index) là O(n)!

LinkedList<String> list = new LinkedList<>();
// ... thêm 10000 phần tử

String item = list.get(5000);  // O(n) - phải traverse từ head hoặc tail!

// ArrayList.get(5000) sẽ là O(1) - direct array access

Giải thích: LinkedList phải traverse từ head hoặc tail để đến index, không phải direct access như ArrayList.

🔥 Bẫy 4: SubList là view, modification propagates

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
List<Integer> sub = list.subList(1, 4);  // [2, 3, 4]

sub.set(0, 99);
System.out.println(list);  // [1, 99, 3, 4, 5] - list gốc cũng đổi!

list.add(6);  // Structural change trên parent
// sub.get(0);  // ❌ ConcurrentModificationException!

Giải thích: subList() trả về view, không phải copy. Modifications propagate, nhưng structural changes làm invalidate view.

Ví dụ thực hành

Ví dụ 1: Todo List Manager

import java.util.*;

public class TodoListManager {
    private List<String> todos;

    public TodoListManager() {
        this.todos = new ArrayList<>();
    }

    public void addTodo(String task) {
        todos.add(task);
        System.out.println("Added: " + task);
    }

    public void removeTodo(int index) {
        if (index >= 0 && index < todos.size()) {
            String removed = todos.remove(index);
            System.out.println("Removed: " + removed);
        } else {
            System.out.println("Invalid index!");
        }
    }

    public void markComplete(int index) {
        if (index >= 0 && index < todos.size()) {
            String task = todos.get(index);
            todos.set(index, "✓ " + task);
        }
    }

    public void displayTodos() {
        System.out.println("\n=== Todo List ===");
        for (int i = 0; i < todos.size(); i++) {
            System.out.println(i + ". " + todos.get(i));
        }
    }

    public static void main(String[] args) {
        TodoListManager manager = new TodoListManager();

        manager.addTodo("Buy groceries");
        manager.addTodo("Write code");
        manager.addTodo("Exercise");
        manager.displayTodos();

        manager.markComplete(1);
        manager.displayTodos();

        manager.removeTodo(0);
        manager.displayTodos();
    }
}

Ví dụ 2: Remove duplicates nhưng giữ thứ tự

public class RemoveDuplicates {
    public static <T> List<T> removeDuplicates(List<T> list) {
        // Cách 1: Dùng LinkedHashSet để giữ thứ tự
        return new ArrayList<>(new LinkedHashSet<>(list));
    }

    public static <T> List<T> removeDuplicatesManual(List<T> list) {
        // Cách 2: Manual check
        List<T> result = new ArrayList<>();
        for (T item : list) {
            if (!result.contains(item)) {
                result.add(item);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 3, 2, 4, 1, 5, 3);
        System.out.println("Original: " + numbers);

        List<Integer> unique = removeDuplicates(numbers);
        System.out.println("Unique: " + unique);
        // Output: [1, 2, 3, 4, 5]
    }
}

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

Bài 1: Student Grade Manager

Tạo class StudentGradeManager với:

• List lưu điểm của học sinh
• Method addGrade(double grade): thêm điểm
• Method removeLowestGrade(): xóa điểm thấp nhất
• Method getAverage(): tính điểm trung bình
• Method getTopThreeGrades(): lấy 3 điểm cao nhất

Bài 2: Merge Two Sorted Lists

Viết method mergeSortedLists(List<Integer> list1, List<Integer> list2) để merge 2 list đã sắp xếp thành 1 list sắp xếp.

Bài 3: Rotate List

Viết method rotate(List<T> list, int k) để xoay list sang phải k vị trí. Ví dụ: [1,2,3,4,5] rotate 2 positions → [4,5,1,2,3]

Tổng kết

Trong bài này, bạn đã học:

• List là collection ordered, cho phép duplicates, có index-based access
• ArrayList: Dynamic array, nhanh cho random access (O(1)), chậm cho insert/delete ở giữa (O(n))
• LinkedList: Doubly-linked list, nhanh cho insert/delete đầu/cuối (O(1)), chậm cho random access (O(n))
• Khi nào dùng gì: 99% dùng ArrayList, LinkedList chỉ khi cần thêm/xóa đầu danh sách liên tục
• Common operations: add, get, set, remove, indexOf, subList
• Immutable list với List.of() (Java 9+)
• Các cách iteration: for, for-each, Iterator, ListIterator, forEach, Stream

Quy tắc vàng: Khi không chắc, dùng ArrayList!

Đọc thêm

• List Interface - Oracle
• ArrayList API - Oracle
• LinkedList API - Oracle