Linked list

Chèn một đơn gấp vào đầu List<T> 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 (property Next trong ví dụ) không chứa node đó, mà chỉ trỏ tới nó, như bài Value type và reference type của khoá C# Core.

Ví dụ

var first = new Node("DH1");
first.Next = new Node("DH2");
first.Next.Next = new Node("DH3");

Node? current = first;
while (current != null)
{
    Console.WriteLine(current.Value);
    current = current.Next;
}

class Node
{
    public string Value { get; }
    public Node? Next { get; set; }

    public Node(string value)
    {
        Value = value;
    }
}

• Mỗi Node giữ Value và Next. Next của DH3 là null, đánh dấu hết danh sách.
• Duyệt bằng cách đi theo Next từ node đầu, tới khi gặp null.
• Node? cho phép biến chứa null, như string? ở bài null và nullable của khoá C# Core.

.NET có sẵn LinkedList<T> với AddFirst, AddLast, RemoveFirst, RemoveLast, đều O(1).

LinkedList<T> nối node theo cả hai chiều: mỗi node có Next và Previous. Nó không có list[i], lấy theo vị trí bằng ElementAt(i) thì phải đi từ node đầu.

var orders = new LinkedList<string>();
orders.AddLast("DH1");
orders.AddLast("DH2");
orders.AddLast("DH3");
orders.AddLast("DH4");
Console.WriteLine(orders.ElementAt(1));
Console.WriteLine(orders.ElementAt(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.Next = 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<T>. Linked list không có ô đánh số, nên không có [i].

// SAI — lỗi compile: LinkedList không có [i]
var orders = new LinkedList<string>();
orders.AddLast("DH1");
orders.AddLast("DH2");
Console.WriteLine(orders[1]);

// ĐÚNG — cần lấy theo vị trí thì dùng List<T>
var orders = new List<string>();
orders.Add("DH1");
orders.Add("DH2");
Console.WriteLine(orders[1]);

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).
• .NET có LinkedList<T>. Không có [i].
• Trong thực tế, List<T> 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.