Java Collections Framework: ArrayList vs LinkedList

Giới thiệu

ArrayList và LinkedList là 2 implementation phổ biến của List interface trong Java. Hiểu rõ sự khác biệt giữa chúng giúp chọn đúng data structure cho từng bài toán.

1. Cấu trúc dữ liệu

ArrayList

• Sử dụng dynamic array bên trong
• Các phần tử được lưu liên tiếp trong bộ nhớ
• Kích thước tăng tự động (capacity x 1.5 khi đầy)

ArrayList<String> list = new ArrayList<>();
list.add("Java");  // O(1) - amortized
list.get(0);       // O(1) - truy cập trực tiếp

LinkedList

• Sử dụng doubly linked list
• Mỗi node chứa: data, pointer đến next và previous
• Không cần memory liên tiếp

LinkedList<String> list = new LinkedList<>();
list.add("Java");     // O(1)
list.get(0);          // O(n) - phải duyệt từ đầu

2. Performance Comparison

| Operation | ArrayList | LinkedList | |-----------|-----------|------------| | get(index) | O(1) | O(n) | | add(element) | O(1)* | O(1) | | add(index, element) | O(n) | O(n) | | remove(index) | O(n) | O(n) |

*: Amortized time - đôi khi O(n) khi resize

3. Khi nào dùng cái nào?

Dùng ArrayList khi:

• Cần truy cập random nhiều (get/set by index)
• Thêm/xóa chủ yếu ở cuối list
• Memory overhead thấp hơn

Dùng LinkedList khi:

• Thêm/xóa ở đầu list thường xuyên
• Duyệt tuần tự (iterator)
• Không cần random access

4. Ví dụ thực tế

// ArrayList - Truy cập nhanh
List<Student> students = new ArrayList<>();
students.add(new Student("Nam", 20));
students.add(new Student("Hân", 21));

// Truy cập index nhanh O(1)
Student first = students.get(0);

// LinkedList - Thêm/xóa đầu nhanh
Deque<Task> taskQueue = new LinkedList<>();
taskQueue.addFirst(new Task("Urgent"));  // O(1)
taskQueue.removeFirst();                 // O(1)

5. Benchmark thực tế

// Test với 100,000 phần tử
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

// Add operations
long start = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
}
System.out.println("ArrayList add: " + (System.nanoTime() - start) / 1000000 + "ms");
// Output: ~5ms

start = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
System.out.println("LinkedList add: " + (System.nanoTime() - start) / 1000000 + "ms");
// Output: ~8ms

// Get operations
start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
    arrayList.get(50000);
}
System.out.println("ArrayList get: " + (System.nanoTime() - start) / 1000000 + "ms");
// Output: ~0.1ms

start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
    linkedList.get(50000);
}
System.out.println("LinkedList get: " + (System.nanoTime() - start) / 1000000 + "ms");
// Output: ~150ms (!!!)

6. Kết luận

• ArrayList: Default choice cho hầu hết trường hợp
• LinkedList: Chỉ khi cần thao tác đầu/cuối thường xuyên
• Luôn benchmark với data thực tế!

Rule of thumb: Nếu nghi ngờ, dùng ArrayList.