Ôn bài một chút, Arrays và Linked Lists

Chúng ta sẽ đi qua: Array, Singly Linked List, Circular Linked List, và Doubly Linked List

Arrays: Bê tông liền khối

Một chút bối cảnh

Khoảng thập niên 1940–1950, khi tư duy lập trình còn rất gần với máy, việc biểu diễn dữ liệu liên tục trong bộ nhớ là lựa chọn tự nhiên: dễ tính offset, dễ ánh xạ vào phần cứng. Chuyện 0-based indexing không phải “làm khó sinh viên” mà đơn giản là: địa chỉ phần tử i = base + i * size. Tránh thêm một phép trừ. Tối ưu nhỏ, nhưng ở thời máy tính chậm, điều đó đáng kể.

Arrays trong Java: Bên trong có gì?

Khi bạn viết int[] numbers = new int[5] trong Java, điều gì thực sự xảy ra?

int[] numbers = new int[5];
// JVM tạo ra:
// - Object header (thông tin GC)
// - Class metadata 
// - Array length (5)
// - 5 × 4 bytes cho các int

Điều quan trọng: bộ nhớ liền kề. Hình dung một dãy hộp đánh số. Muốn phần tử thứ 10? Địa chỉ = địa chỉ đầu + 10 * kích_thước. Không vòng lặp, không pointer chasing.

Cache locality: lợi thế ít khi được dạy rõ

CPU không đọc từng phần tử; nó kéo nguyên cache line (thường 64 bytes). Duyệt tuần tự nghĩa là phần tử tiếp theo hầu như luôn “đang chờ sẵn” trong L1/L2 cache.

// Cache-friendly: CPU đoán được pattern
int sum = 0;
for (int i = 0; i < array.length; i++) {
    sum += array[i]; // Các phần tử tiếp theo đã sẵn sàng trong cache!
}

Hệ quả: so với linked list (mỗi node trôi nổi đâu đó trong heap), duyệt tuần tự array có thể nhanh hơn hàng chục đến vài trăm lần tùy workload, không phải vì thuật toán khác – mà vì phần cứng biết dự đoán.

Mặt trái

Sai phạm kinh điển: vượt biên (out-of-bounds). Trong Java được chặn bằng ArrayIndexOutOfBoundsException, nhưng ở C/C++ vượt biên có thể trở thành lỗ hổng bảo mật. Nhiều sự cố lớn trong thực tế bắt nguồn từ việc tin vào kích thước dữ liệu bên ngoài.

// Đừng bao giờ làm thế này:
int[] arr = new int[10];
arr[15] = 42; // ArrayIndexOutOfBoundsException incoming!

Singly Linked List: Linh hoạt tối giản

Ra đời từ nhu cầu biểu diễn tập hợp mở rộng linh hoạt khi bộ nhớ phân mảnh, singly linked list dùng mỗi node chứa (giá trị, next). Không cache-friendly, nhưng thêm/xóa đầu danh sách thì rẻ.

class Node<T> {
    T data;           // Dữ liệu của node
    Node<T> next;     // Con trỏ đến node tiếp theo
    
    Node(T data) {
        this.data = data;
        this.next = null; // Cuối danh sách
    }
}

So sánh ngắn gọn với array

Array mạnh ở truy cập chỉ số O(1). Singly list mạnh ở chèn / xóa đầu O(1) không phải dời phần tử. Truy cập phần tử thứ k phải đi tuần tự: O(k).

// Array: Truy cập O(1), nhưng thêm/xóa O(n)
int[] arr = new int[1000];
int value = arr[500]; // Nhanh như chớp!

// Linked List: Truy cập O(n), nhưng thêm/xóa O(1)
Node<Integer> head = new Node<>(42);
head.next = new Node<>(84);
// Thêm node mới vào đầu? Chỉ cần 2 dòng code!

Ứng dụng

• Cấu trúc nền của nhiều hàng đợi / stack đơn giản
• Bộ nhớ bị phân mảnh mạnh (nhúng, cấu trúc tạm thời)
• Một số nghiệm pháp (hash chaining trong hash table open-chaining)
• Log đơn tuyến (append ở đầu / cuối)

Circular Linked List: Khi điểm kết thúc nối về điểm đầu

Thay vì tail.next = null, ta để tail.next = head. Điều này loại bỏ một số điều kiện đặc biệt khi xoay vòng.

Ví dụ dùng:

• Lập lịch vòng tròn (round-robin) cho tiến trình / thread
• Mô phỏng game lượt: sau người chơi cuối quay về người chơi đầu
• Playlist “repeat all”
• Bộ đệm vòng (dù triển khai hiệu quả hơn hay dùng array + hai chỉ số)

Josephus thường được nhắc như ví dụ lịch sử, nhưng trong thực tế, điều bạn quan tâm hơn là: làm sao duy trì con trỏ “hiện tại” và xoay vòng ổn định mà không phải liên tục kiểm tra null.

public class CircularLinkedList<E> {
    private Node<E> tail = null;
    
    public void addFirst(E element) {
        Node<E> newNode = new Node<>(element);
        
        if (tail == null) {
            tail = newNode;
            newNode.next = newNode; // Trỏ về chính nó - magic!
        } else {
            newNode.next = tail.next;
            tail.next = newNode;
        }
    }
}

Lưu ý

Duyệt vòng phải cẩn thận điều kiện kết thúc để tránh loop vô hạn.

// NGUY HIỂM: Có thể chạy mãi mãi!
Node current = head;
while (current != null) { // Sai! Trong circular list không bao giờ null
    current = current.next;
}

// ĐÚNG:
Node current = head;
do {
    // Làm gì đó
    current = current.next;
} while (current != head);

Doubly Linked List: Hỗ trợ hai chiều – trả giá bằng bộ nhớ

Thêm con trỏ prev giúp:

• Xóa node biết sẵn tham chiếu: O(1)
• Duyệt hai chiều
• Là nền cho LRU cache (kết hợp HashMap)

class Node<T> {
    T data;
    Node<T> prev;     // Con trỏ về phía trước
    Node<T> next;     // Con trỏ về phía sau
    
    // Magic method: Xóa chính mình mà không cần duyệt!
    void removeSelf() {
        if (prev != null) prev.next = next;
        if (next != null) next.prev = prev;
        // That's it! O(1) deletion! 🎉
    }
}

Ứng dụng (Doubly)

java.util.LinkedList là doubly linked list. Ngoài ra:

• LRU cache (HashMap + DoublyList)
• Kết nối lá trong B+Tree (liên kết tuần tự theo khóa)
• Undo/redo (danh sách trạng thái hai chiều)
• Một số cấu trúc trong nhân hệ điều hành

Ghi chú về XOR list

XOR linked list (lưu prev XOR next) từng là mẹo tiết kiệm bộ nhớ pointer, ngày nay hiếm dùng: khó debug, phá vỡ giả định bộ nhớ an toàn (Java không hỗ trợ kiểu này).

Performance Showdown: Ai Thắng Ai?

Bảng tổng kết (tập trung vào bản chất)

*Amortized cho dynamic arrays
**O(1) nếu có tail pointer

Khi Nào Dùng Gì?

Array – Dùng khi:

• Cần random access nhanh
• Kích thước tương đối ổn định hoặc chấp nhận resize theo khối
• Duyệt tuần tự nhiều (tận dụng cache)

Singly linked list – Dùng khi:

• Thêm / xóa đầu thường xuyên
• Không cần truy cập ngẫu nhiên
• Môi trường bộ nhớ phân mảnh

Circular list – Dùng khi:

• Mô hình hóa vòng lặp tuần hoàn rõ ràng (round-robin)
• Giảm if/else kiểm tra null ở cuối

Doubly linked list – Dùng khi:

• Xóa node giữa với tham chiếu có sẵn
• Cần duyệt hai chiều
• LRU / undo–redo

Ví dụ tổng hợp: Music Player tối giản

Một thiết kế đơn giản kết hợp đặc tính mỗi cấu trúc:

public class MusicPlayer {
    // Doubly linked list cho playlist (prev/next songs)
    private LinkedList<Song> playlist = new LinkedList<>();
    
    // Circular behavior cho repeat-all
    private boolean repeatAll = false;
    private int currentIndex = 0;
    
    // Array cho real-time audio visualization
    private int[] frequencyData = new int[1024];
    
    // Singly linked list cho undo history
    private Node<PlayerAction> undoHistory;
    
    public void nextSong() {
        if (repeatAll && currentIndex == playlist.size() - 1) {
            currentIndex = 0; // Vòng tròn!
        } else {
            currentIndex++;
        }
    // O(1) khi đã có danh sách liên kết hai chiều
    }
    
    public void updateVisualizer(byte[] audioData) {
    // Duyệt tuyến tính trong mảng: tận dụng cache
        for (int i = 0; i < frequencyData.length; i++) {
            frequencyData[i] = processFrequency(audioData[i]);
        }
    }
    
    public void addToUndoHistory(PlayerAction action) {
    // Lưu lịch sử thao tác kiểu stack đơn
        Node<PlayerAction> newNode = new Node<>(action);
        newNode.next = undoHistory;
        undoHistory = newNode; // O(1) insert!
    }
}

Memory layout (ước lượng trong JVM 64-bit)

Ước tính sơ bộ (bỏ qua alignment chi tiết):

Array 1000 ints:     ~4KB liền kề
Singly linked 1000:  ~24KB rải rác  
Doubly linked 1000:  ~32KB rải rác

Array được hưởng lợi từ:

• Bounds check elimination (trình JIT chứng minh chỉ số an toàn)
• Loop vectorization
• Prefetch tuyến tính

Linked list không có những tối ưu đó vì bước nhảy địa chỉ không đoán trước.

Famous Bugs: Lessons From The Dark Side

Một vài lỗi kinh điển

• Null / uninitialized reference → NullPointerException
• Off-by-one (<= thay vì <) trong vòng lặp
• Tin vào kích thước dữ liệu phía client → lỗi bảo mật (ví dụ lớp lỗi kiểu Heartbleed trong hệ thống cấp thấp)

Những Điều Chúng Ta Đã Học

Tóm gọn:

• Array: nhanh, sát phần cứng, nhưng ít linh hoạt
• Singly list: thêm/xóa đầu rẻ, truy cập ngẫu nhiên chậm
• Circular list: mô hình hóa chu kỳ gọn
• Doubly list: trả thêm bộ nhớ để đổi lấy thao tác giữa O(1)

Performance Rules of Thumb

• Random access nhiều? → Arrays
• Insert/delete liên tục? → Linked Lists
• Round-robin cần? → Circular
• Bidirectional navigation? → Doubly

Kết luận

Không có cấu trúc “tuyệt đối”. Mỗi lựa chọn là một tuyên bố về ưu tiên: tốc độ truy cập, linh hoạt kích thước, dễ xóa giữa, hay mô hình vòng lặp.

Điểm mấu chốt:

1. Hiểu mô hình bộ nhớ phía dưới (cache lines, pointer chasing)
2. Rõ pattern truy cập chính trước khi chọn
3. Đừng tối ưu sớm – nhưng hãy biết mình đang trả giá gì

Hy vọng bài viết giúp bạn nhìn chúng ít “giáo trình” hơn và nhiều “tư duy thiết kế” hơn.

Chúc bạn build được những cấu trúc gọn, đúng và có chủ ý.