Trong Java Collections Framework, LinkedList là một triển khai của giao diện List và Deque, nổi bật với cấu trúc dữ liệu dựa trên danh sách liên kết kép. Điều này mang lại những đặc tính và hiệu suất khác biệt đáng kể so với các triển khai dựa trên mảng như ArrayList.

Cấu Trúc Kế Thừa và Giao Diện

Lớp LinkedList trong Java được định nghĩa như sau:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
  // ... Nội dung lớp
}

Từ định nghĩa này, chúng ta có thể suy ra các đặc điểm chính của LinkedList:

1. Serializable và Cloneable: Tương tự như ArrayList, LinkedList hỗ trợ tuần tự hóa (lưu trữ và khôi phục trạng thái đối tượng) và nhân bản (tạo một bản sao của đối tượng).
2. List: Giao diện List cung cấp các phương thức cơ bản cho một danh sách có thứ tự, cho phép thêm, xóa, truy cập phần tử theo chỉ mục. Mặc dù là danh sách liên kết, LinkedList vẫn cung cấp các thao tác dựa trên chỉ mục nhờ việc triển khai giao diện này.
3. Deque (Double-Ended Queue): Đây là một điểm mạnh đặc biệt của LinkedList. Giao diện Deque mở rộng giao diện Queue, cho phép thêm và xóa phần tử từ cả hai đầu của danh sách. Điều này biến LinkedList thành một cấu trúc dữ liệu đa năng, có thể hoạt động như một hàng đợi (Queue - FIFO) hoặc một ngăn xếp (Stack - LIFO).
4. AbstractSequentialList: Lớp trừu tượng này cung cấp một triển khai cơ bản cho các hoạt động dựa trên chỉ mục cho các danh sách tuần tự (liên kết), chủ yếu thông qua việc sử dụng các iterator. Nó giúp LinkedList kế thừa các phương thức xử lý chỉ mục một cách hiệu quả, mặc dù việc truy cập ngẫu nhiên không phải là ưu điểm của danh sách liên kết.

Thành Phần Cốt Lõi của LinkedList

LinkedList sử dụng cấu trúc danh sách liên kết kép, nghĩa là mỗi phần tử (gọi là "nút" hoặc "đầu mục") không chỉ biết phần tử tiếp theo mà còn biết phần tử trước đó.

Các Trường Dữ Liệu Quan Trọng

transient int totalElements = 0; // Tổng số phần tử hiện có

transient NodeEntry<E> headNode; // Tham chiếu đến nút đầu tiên

transient NodeEntry<E> tailNode; // Tham chiếu đến nút cuối cùng

• totalElements: Đếm số lượng phần tử hiện tại trong danh sách.
• headNode: Luôn trỏ đến nút đầu tiên của danh sách. Nếu danh sách rỗng, nó sẽ là null.
• tailNode: Luôn trỏ đến nút cuối cùng của danh sách. Nếu danh sách rỗng, nó sẽ là null.

Lớp Nút Bên Trong (NodeEntry)

LinkedList quản lý dữ liệu thông qua các đối tượng nút nội bộ. Mỗi nút chứa dữ liệu và các tham chiếu đến nút trước và nút sau.

private static class NodeEntry<E> {
    E dataValue; // Dữ liệu của nút
    NodeEntry<E> nextRef; // Tham chiếu đến nút kế tiếp
    NodeEntry<E> previousRef; // Tham chiếu đến nút trước đó

    NodeEntry(NodeEntry<E> prev, E value, NodeEntry<E> next) {
        this.dataValue = value;
        this.nextRef = next;
        this.previousRef = prev;
    }
}

Các Bộ Lặp (Iterators)

LinkedList cung cấp nhiều loại bộ lặp để duyệt và thao tác với các phần tử:

• Iterator: Bộ lặp tiêu chuẩn, duyệt tiến về phía trước và hỗ trợ loại bỏ phần tử.
• ListIterator: Bộ lặp nâng cao, cho phép duyệt cả hai chiều (tiến và lùi), và hỗ trợ các thao tác thêm, đặt lại (set) và xóa phần tử.
• DescendingIterator: Bộ lặp đặc biệt để duyệt danh sách theo chiều ngược lại.
• Spliterator: Hỗ trợ duyệt song song hiệu quả, thường được sử dụng trong Stream API.

Các Hàm Khởi Tạo

// Hàm khởi tạo mặc định, tạo một danh sách liên kết rỗng
public LinkedList() {
}

// Hàm khởi tạo với một Collection, sao chép tất cả phần tử từ collection đó
public LinkedList(Collection<? extends E> c) {
    this(); // Gọi hàm khởi tạo mặc định
    addAll(c); // Thêm tất cả các phần tử từ collection
}

Thao Tác Thêm Phần Tử

Phương thức add(E e) thường được dùng để thêm một phần tử vào cuối danh sách. Nó ủy quyền công việc cho một phương thức nội bộ:

public boolean add(E element) {
    addLastElement(element); // Gọi phương thức nội bộ để thêm vào cuối
    return true;
}

private void addLastElement(E newElement) {
    final NodeEntry<E> currentTail = tailNode; // Lấy tham chiếu đến nút cuối hiện tại
    // Tạo nút mới, liên kết với nút cuối hiện tại và không có nút sau nó
    final NodeEntry<E> newNode = new NodeEntry<>(currentTail, newElement, null);
    tailNode = newNode; // Cập nhật nút cuối cùng là nút mới

    if (currentTail == null) { // Nếu danh sách rỗng (nút cuối cũ là null)
        headNode = newNode; // Nút mới trở thành nút đầu tiên
    } else {
        currentTail.nextRef = newNode; // Nút cuối cũ trỏ đến nút mới
    }
    totalElements++; // Tăng số lượng phần tử
    modCount++; // Tăng biến đếm sửa đổi cho các iterator
}

Thao Tác Lấy Phần Tử

Lấy Phần Tử Đầu và Cuối

Việc truy cập phần tử ở đầu và cuối danh sách là rất hiệu quả (O(1)) vì LinkedList duy trì các tham chiếu trực tiếp đến headNode và tailNode.

public E getFirst() {
    final NodeEntry<E> firstItem = headNode;
    if (firstItem == null)
        throw new NoSuchElementException("Danh sách rỗng, không có phần tử đầu tiên.");
    return firstItem.dataValue;
}

public E getLast() {
    final NodeEntry<E> lastItem = tailNode;
    if (lastItem == null)
        throw new NoSuchElementException("Danh sách rỗng, không có phần tử cuối cùng.");
    return lastItem.dataValue;
}

Lấy Phần Tử Theo Chỉ Mục

Đây là điểm khác biệt lớn so với ArrayList. Vì LinkedList không hỗ trợ truy cập ngẫu nhiên, việc lấy phần tử theo chỉ mục yêu cầu duyệt qua danh sách. Tuy nhiên, do là danh sách liên kết kép, LinkedList tối ưu hóa việc duyệt:

public E get(int index) {
    checkIndexValidity(index); // Kiểm tra xem chỉ mục có hợp lệ không
    return retrieveNodeByIndex(index).dataValue; // Lấy nút và trả về dữ liệu
}

private NodeEntry<E> retrieveNodeByIndex(int targetIndex) {
    // Tối ưu hóa việc tìm kiếm bằng cách chọn hướng duyệt
    // Nếu chỉ mục nằm ở nửa đầu danh sách, duyệt từ đầu.
    // Nếu chỉ mục nằm ở nửa sau, duyệt từ cuối.
    if (targetIndex < (totalElements / 2)) {
        NodeEntry<E> current = headNode;
        for (int i = 0; i < targetIndex; i++) {
            current = current.nextRef;
        }
        return current;
    } else { // Duyệt ngược từ cuối danh sách
        NodeEntry<E> current = tailNode;
        for (int i = totalElements - 1; i > targetIndex; i--) {
            current = current.previousRef;
        }
        return current;
    }
}

Phương thức retrieveNodeByIndex kiểm tra xem chỉ mục có gần đầu hay gần cuối danh sách hơn để quyết định hướng duyệt. Điều này giúp giảm thiểu số bước duyệt trung bình xuống còn O(n/2), thay vì O(n) nếu chỉ duyệt một chiều.

Đặc Tính Tổng Quan và Hiệu Suất

• Cấu trúc: Dựa trên danh sách liên kết kép (doubly linked list), mỗi phần tử là một nút chứa dữ liệu và tham chiếu đến nút trước và sau.
• Tính chất: Giữ nguyên thứ tự các phần tử được thêm vào, cho phép phần tử trùng lặp và chấp nhận giá trị null. Không an toàn cho môi trường đa luồng (non-thread-safe).
• Hàng đợi/Ngăn xếp: Hoạt động hiệu quả như một hàng đợi (FIFO) hoặc ngăn xếp (LIFO) nhờ triển khai giao diện Deque, với các thao tác thêm/xóa ở hai đầu có độ phức tạp O(1).
• Truy cập ngẫu nhiên: Không có khả năng truy cập ngẫu nhiên nhanh chóng (không triển khai RandomAccess). Truy cập phần tử theo chỉ mục có độ phức tạp thời gian O(n/2) (trung bình O(n)).
• Thêm/Xóa phần tử:
  • Thêm/xóa ở đầu hoặc cuối danh sách: O(1).
  • Thêm/xóa ở giữa danh sách: O(n), do cần duyệt đến vị trí đó trước khi thao tác.
• Bộ lặp: Cung cấp ba loại bộ lặp chính: Iterator (duyệt tiến, xóa), ListIterator (duyệt hai chiều, thêm/đặt/xóa), và DescendingIterator (duyệt lùi, xóa).