Singly linked list là gì và khi nào bạn nên dùng nó?

Question

Accepted Answer

**Singly linked list** (danh sách liên kết đơn) là một chuỗi các **node**, trong đó mỗi node chứa một giá trị và một pointer trỏ tới node **kế tiếp** (next). Không giống array, các node không liền kề — chúng có thể nằm ở bất kỳ đâu trong bộ nhớ, được kết nối bằng các tham chiếu.

## Cấu trúc

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## Ví dụ

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# Chèn ở đầu -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # trỏ node mới vào head cũ
    return node          # head mới

# Tìm kiếm -> O(n): phải đi qua cả chuỗi
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## Độ phức tạp

| Thao tác | Thời gian |
|---|---|
| Chèn/xóa ở head | O(1) |
| Truy cập theo index | O(n) |
| Tìm kiếm | O(n) |

## Đánh đổi

- **Điểm mạnh:** chèn/xóa O(1) ở đầu; phát triển mà không cần cấp phát lại; không lãng phí dung lượng.
- **Điểm yếu:** không truy cập ngẫu nhiên; mỗi node mang chi phí pointer; tính cục bộ cache kém (bộ nhớ rải rác).

## Tại sao điều này quan trọng

Linked list tỏa sáng khi bạn thường xuyên thêm hoặc xóa ở hai đầu và hiếm khi truy cập index vào giữa — ví dụ, làm xương sống cho stack, queue, và adjacency list.

Hiểu việc thao tác pointer ở đây là nền tảng cho tree, graph, và nhiều bài toán phỏng vấn.

Thao tác	Thời gian
Chèn/xóa ở head	O(1)
Truy cập theo index	O(n)
Tìm kiếm	O(n)