Linked list đơn, đôi và so sánh với mảng

Giới thiệu

Bài này học nút, con trỏ và hai loại linked list. Bạn biết khi nào dùng list thay mảng.

Kiến thức cần nhớ

Nút và list đơn

• Nút gồm dữ liệu và con trỏ next.
• Next trỏ tới nút kế tiếp trong chuỗi.
• Head là nút đầu, cửa vào duy nhất.
• Ví dụ đời thường: đoàn tàu, mỗi toa nối toa sau.
• Đọc phần tử thứ k phải duyệt từ head.

List đôi và list vòng

• List đôi thêm con trỏ prev trỏ ngược.
• Prev giúp duyệt hai chiều, xóa nhanh hơn.
• List vòng cho nút cuối trỏ về head.
• Ví dụ đời thường: lịch sử trình duyệt đi tới lui.
• Giá phải trả là tốn thêm bộ nhớ.

So sánh với mảng

• Mảng truy xuất thứ k trong $O(1)$.
• List chèn xóa đầu trong $O(1)$.
• Mảng thân thiện cache hơn list.
• Ví dụ đời thường: mảng như kệ sách đánh số.

Ví dụ

• Input: A -> B -> C, chèn X sau A. Output: A -> X -> B -> C.
• Giải thích: chỉ nối lại 2 con trỏ nên không mất nút nào.

# Chèn sau nút đã biết
new_node.next = cur.next  # nút mới trỏ tới nút kế
cur.next = new_node  # nút hiện tại trỏ sang nút mới

💻 Bài tập

Ngôn ngữ: C (hoặc C++ không dùng std::list). Nộp vào day-002/.

Bài 1: Singly linked list

typedef struct Node { int val; struct Node *next; } Node;
typedef struct { Node *head; Node *tail; size_t size; } SList;

Ràng buộc

• tail luôn đúng sau mọi thao tác, kể cả khi list còn 0 hoặc 1 nút.
• Viết thêm hàm void sl_print(const SList *l) in dạng [1 -> 2 -> 3] để debug.

Test mẫu

push_back 1, 2, 3                 -> [1 -> 2 -> 3], size=3
insert_after(find(1), 9)          -> [1 -> 9 -> 2 -> 3]
remove(3)                         -> [1 -> 9 -> 2], tail->val = 2
reverse                           -> [2 -> 9 -> 1], tail->val = 1
pop_front x3, pop_front lần 4     -> lần 4 trả false, head = tail = NULL
push_back 5 sau khi rỗng          -> [5], head == tail

Bài 2: Doubly linked list và lịch sử trình duyệt

Viết DList với nút có prev và next. Cài thêm dl_remove_node(DList *l, DNode *n) chạy $O(1)$.

Dùng DList làm lịch sử trình duyệt:

visit a, b, c           -> hiện tại c
back(2)                 -> a
forward(1)              -> b
visit d                 -> d (trang c bị xóa)
forward(1)              -> d (không còn trang sau)
back(10)                -> a

Bài 3: Đo mảng và list (nâng cao)

Dùng Dynamic Array ngày 1 và SList Bài 1. Đo thời gian với $n = 10^5$:

1. push_back $n$ phần tử.
2. Chèn đầu $n$ phần tử.
3. Duyệt tính tổng $n$ phần tử.

In bảng thời gian (ms). Viết 3 câu giải thích vì sao duyệt mảng nhanh hơn duyệt list dù cùng $O(n)$.

✅ Tiêu chí hoàn thành

• Mọi test mẫu pass bằng assert.
• AddressSanitizer và valgrind sạch: không leak, không use-after-free.
• Bảng đo Bài 3 có số thật kèm giải thích về cache.
• Vẽ tay được các con trỏ đổi thế nào khi insert_after và reverse.

❓ Câu hỏi ôn tập

• Nút gồm những gì, head là gì?
• List đơn khác list đôi ở điểm nào?
• Chèn đầu list tốn bao nhiêu bước?
• Khi nào nên dùng mảng thay list?

🌕 Bạn đã hoàn thành ngày 2. Làm hết bài tập phía trên rồi sang ngày tiếp theo.