🔗 Bài giảng: Linked List (có mô phỏng trực quan)

Linked List gồm các node được nối liên tiếp bằng con trỏ next. Ta có thể chèn/xoá node ở đầu hoặc giữa rất nhanh — không cần dời toàn bộ phần tử như mảng.

I. Mô phỏng Linked List

🛠 Thao tác

💡 Nhập giá trị và thao tác để thấy Linked List thay đổi.

💻 Code đang chạy

Node* head = NULL;
Node* p = new Node(x);
p->next = head;
head = p;
Node* p = new Node(x);
if(head == NULL) head = p;
else tail->next = p;
if(head->val == x) head = head->next;
cur->next = cur->next->next;
cout << head->val;

📊 Linked List

II. Lý thuyết cơ bản

Linked List là cấu trúc dữ liệu **linh hoạt**, đặc biệt mạnh trong thao tác chèn/xoá.

Insert đầu: O(1)
Insert cuối: O(1) nếu có tail
Delete node: O(1) nếu biết node trước đó
Duyệt: O(n)

III. Khi nào dùng Linked List

1) Khi có rất nhiều thao tác chèn/xoá 👉 Insert/Delete O(1) → mạnh hơn mảng.

2) Khi bài yêu cầu mô phỏng con trỏ 👉 Con trỏ trái/phải, xoá tại vị trí → đặc trưng Linked List.

3) Khi xử lý bằng slow/fast pointer 👉 Tìm giữa, tìm chu kỳ, tìm node thứ k từ cuối.

4) Khi bài yêu cầu đảo ngược dãy hoặc đảo một đoạn 👉 Đổi con trỏ, không phải đổi chỗ phần tử như array.

5) Khi bộ nhớ phân mảnh 👉 Linked List không cần vùng nhớ liên tục.

IV. Bài tập luyện tập

📘 Cơ bản

1️⃣ Chèn đầu/cuối danh sách

Node* push_front(Node* head, int x){
  Node* p = new Node(x);
  p->next = head;
  return p;
}

📗 Trung bình – Two pointers

2️⃣ Tìm phần tử giữa

Node* mid(Node* head){
  Node *slow=head, *fast=head;
  while(fast && fast->next){
    slow=slow->next;
    fast=fast->next->next;
  }
  return slow;
}

📙 Nâng cao

3️⃣ Reverse toàn bộ Linked List

🐉 HSG – khó

4️⃣ Floyd Cycle Detection

🔚 Mô phỏng giúp bạn hiểu rõ Linked List hoạt động thế nào trong thực tế.