Linked list

Chèn một đơn gấp vào đầu ArrayList thì mọi đơn phía sau phải dời chỗ, tốn O(n). Linked list không xếp phần tử liền nhau, nên chèn vào đầu chỉ mất một bước. Đổi lại, muốn tới phần tử thứ 1000 thì phải đi qua 999 phần tử trước.

Khái niệm

⛓️ Linked list: danh sách mà mỗi phần tử (gọi là node) giữ giá trị và tham chiếu tới node kế tiếp, node cuối trỏ tới null.

Tham chiếu tới node kế tiếp (field next trong ví dụ) không chứa node đó, mà chỉ trỏ tới nó, như bài Kiểu nguyên thuỷ và kiểu tham chiếu của khoá Java Core.

Ví dụ

// Main.java
void main() {
    var first = new Node("DH1");
    first.setNext(new Node("DH2"));
    first.getNext().setNext(new Node("DH3"));

    Node current = first;
    while (current != null) {
        System.out.println(current.getValue());
        current = current.getNext();
    }
}

// Node.java
class Node {
    private String value;
    private Node next;

    public Node(String value) {
        this.value = value;
    }

    public String getValue() { return value; }
    public Node getNext() { return next; }

    public void setNext(Node next) {
        this.next = next;
    }
}

• Mỗi Node giữ value và next. next của DH3 chưa được gán nên là null, đánh dấu hết danh sách.
• Duyệt bằng cách đi theo getNext() từ node đầu, tới khi gặp null.
• Biến kiểu Node nhận được null như mọi kiểu tham chiếu, như bài null và Optional của khoá Java Core.

Java có sẵn LinkedList với addFirst, addLast, removeFirst, removeLast, đều O(1).

LinkedList thật nối node theo cả hai chiều: mỗi node có next và prev. Nhờ vậy get(i) đi từ đầu nào gần vị trí i hơn.

var orders = new LinkedList<String>();
orders.addLast("DH1");
orders.addLast("DH2");
orders.addLast("DH3");
orders.addLast("DH4");
System.out.println(orders.get(1));
System.out.println(orders.get(3));
orders.removeFirst();

Thử ngay

Thêm đơn gấp DH0 vào đầu danh sách. Đặt ba dòng này ngay trên dòng Node current = first;:

var urgent = new Node("DH0");
urgent.setNext(first);
first = urgent;

Đoán trước khi chạy: danh sách in ra theo thứ tự nào? Có node nào phải dời chỗ không?

DH0
DH1
DH2
DH3

Lỗi hay gặp

Lấy phần tử theo vị trí trên LinkedList. LinkedList có get(i), nhưng không có ô đánh số: mỗi lần gọi phải đi qua từng node tới vị trí i. Gọi get(i) trong vòng lặp là O(n²).

// SAI — mỗi get(i) lại đi qua từng node
var orders = new LinkedList<String>();
orders.addLast("DH1");
orders.addLast("DH2");
for (int i = 0; i < orders.size(); i++) {
    System.out.println(orders.get(i));
}

// ĐÚNG — cần lấy theo vị trí thì dùng ArrayList
var orders = new ArrayList<String>();
orders.add("DH1");
orders.add("DH2");
for (int i = 0; i < orders.size(); i++) {
    System.out.println(orders.get(i));
}

Tóm tắt

• Linked list gồm các node, mỗi node giữ giá trị và tham chiếu tới node kế.
• Thêm, bớt ở đầu là O(1). Lấy phần tử thứ i là O(n).
• Java có LinkedList. get(i) có, nhưng là O(n).
• Trong thực tế, ArrayList thường nhanh hơn vì các ô nằm liền nhau. Chỉ dùng linked list khi thêm bớt ở đầu hoặc giữa thật nhiều.