Danh sách liên kết là một cấu trúc dữ liệu động, không yêu cầu các phần tử phải nằm liền kề trong bộ nhớ. Mỗi phần tử (gọi là nút) chứa dữ liệu và tham chiếu đến nút tiếp theo.

Đặc điểm của danh sách đơn hướng

Mỗi nút gồm hai thành phần: giá trị dữ liệu và con trỏ next chỉ đến nút kế tiếp. Nút đầu tiên gọi là head, nút cuối cùng trỏ đến null.

static class ListNode {
    int value;
    ListNode link;

    ListNode(int val) {
        this.value = val;
    }
}

Danh sách kép hướng

Ngoài con trỏ link đến nút sau, mỗi nút còn có thêm con trỏ prev trỏ ngược về nút trước đó, cho phép duyệt hai chiều.

Các thao tác cơ bản

Tìm kiếm: O(n)

Duyệt tuần tự từ đầu đến vị trí cần tìm.

Cập nhật: O(1) sau khi đã xác định vị trí

Chỉ cần gán lại giá trị tại nút đã tìm thấy.

Chèn nút: O(1)

• Chèn đầu: Gán next của nút mới vào head hiện tại, rồi cập nhật head.
• Chèn cuối: Gán next của tail hiện tại vào nút mới, rồi cập nhật tail.
• Chèn giữa: Điều chỉnh con trỏ next của nút trước và nút mới để nối vào chuỗi.

Xóa nút: O(1)

• Xóa đầu: Cập nhật head = head.link.
• Xóa cuối: Tìm nút áp chót, gán link của nó thành null và cập nhật tail.
• Xóa giữa: Nối trực tiếp nút trước với nút sau nút bị xóa.

public class LinkedListManager {
    private ListNode first;
    private ListNode last;
    private int length;

    public void addElement(int value, int position) throws Exception {
        if (position < 0 || position > length) 
            throw new IndexOutOfBoundsException("Vị trí không hợp lệ!");

        ListNode newNode = new ListNode(value);

        if (length == 0) {
            first = last = newNode;
        } else if (position == 0) {
            newNode.link = first;
            first = newNode;
        } else if (position == length) {
            last.link = newNode;
            last = newNode;
        } else {
            ListNode prior = getNode(position - 1);
            newNode.link = prior.link;
            prior.link = newNode;
        }
        length++;
    }

    public ListNode deleteElement(int position) throws Exception {
        if (position < 0 || position >= length)
            throw new IndexOutOfBoundsException("Vị trí không hợp lệ!");

        ListNode target = null;

        if (position == 0) {
            target = first;
            first = first.link;
        } else if (position == length - 1) {
            ListNode prev = getNode(position - 1);
            target = prev.link;
            prev.link = null;
            last = prev;
        } else {
            ListNode prev = getNode(position - 1);
            target = prev.link;
            prev.link = target.link;
        }
        length--;
        return target;
    }

    public ListNode getNode(int index) throws Exception {
        if (index < 0 || index >= length)
            throw new IndexOutOfBoundsException("Vị trí không hợp lệ!");

        ListNode current = first;
        for (int i = 0; i < index; i++) {
            current = current.link;
        }
        return current;
    }

    public void display() {
        ListNode walker = first;
        while (walker != null) {
            System.out.println(walker.value);
            walker = walker.link;
        }
    }

    public static void main(String[] args) throws Exception {
        LinkedListManager list = new LinkedListManager();
        list.addElement(3, 0);
        list.addElement(7, 1);
        list.addElement(9, 2);
        list.addElement(5, 3);
        list.addElement(6, 1);
        list.deleteElement(0);
        list.display();
    }
}