Công cụ trực quan hoá Cấu trúc dữ liệu trong trình duyệt

Chào mừng bạn đến với bài viết cuối cùng của series tự học ngôn ngữ lập trình C. Đến lúc này, chúng ta đã hiểu về biến, hàm, con trỏ, cấp phát bộ nhớ động và cách gom nhóm chúng lại để tạo thành danh sách liên kết, Stack và Queue. Tuy nhiên, việc hình dung cách các con trỏ kết nối và di chuyển địa chỉ ô nhớ khi chạy code vẫn có phần hơi trừu tượng. Để giải quyết việc đó, tôi đã xây dựng một Công cụ trực quan hóa cấu trúc dữ liệu tương tác (Data Structure Visualizer) chạy trực tiếp trên trình duyệt ở phía dưới.

1. Trực quan hóa con trỏ hoạt động như thế nào?

Khi bạn thao tác chèn đầu, chèn cuối hoặc xóa node, thực chất máy tính thực hiện các phép thay đổi địa chỉ của con trỏ next:

• Chèn đầu (Insert Head): Node mới được tạo ra, con trỏ next của nó trỏ tới địa chỉ cũ của head. Sau đó con trỏ head được cập nhật lại trỏ trực tiếp tới Node mới này.
• Chèn cuối (Insert Tail): Duyệt từ đầu danh sách tới Node cuối cùng (Node có next == NULL). Sau đó gán con trỏ next của Node cuối trỏ tới Node mới tạo.
• Xóa đầu (Delete Head): Lưu địa chỉ của Node đầu tiên vào biến tạm temp. Dịch chuyển con trỏ head sang Node kế tiếp (head = head->next). Cuối cùng giải phóng (free) vùng nhớ của Node đầu cũ thông qua con trỏ tạm temp.

2. Công cụ mô phỏng Cấu trúc dữ liệu tương tác

Hãy thử thêm, bớt các nút dưới đây để nhìn thấy mô phỏng vùng nhớ RAM và sự kết nối của con trỏ next thay đổi theo thời gian thực!

📥 Tải về mã nguồn công cụ mô phỏng: ds_visualizer.html

3. Ba nút bấm đó viết bằng C thì trông thế nào?

Dòng Log dưới công cụ mô phỏng không phải lời kể chung chung — nó đọc lại đúng những dòng C sẽ chạy nếu bạn tự viết. Dưới đây là cả ba thao tác, viết đầy đủ để bạn biên dịch và chạy được ngay, đối chiếu từng dòng với hoạt ảnh phía trên.

// Insert Head: O(1) - no traversal, only two pointer assignments
void insertAtHead(Node **head, int value) {
    Node *newNode = createNode(value);
    newNode->next = *head;   // The new node points at the old first node
    *head = newNode;         // head now points at the new node
}

// Insert Tail: O(N) - the whole list has to be walked to find the last node
void insertAtTail(Node **head, int value) {
    Node *newNode = createNode(value);
    if (*head == NULL) {     // An empty list: the new node becomes the head
        *head = newNode;
        return;
    }
    Node *cur = *head;
    while (cur->next != NULL) {  // Walk until the node whose next is NULL
        cur = cur->next;
    }
    cur->next = newNode;
}

// Delete Head: O(1) - keep the old head in temp so it can still be freed
void deleteHead(Node **head) {
    if (*head == NULL) {
        printf("The list is empty, nothing to delete\n");
        return;
    }
    Node *temp = *head;      // Remember the address before losing it
    *head = (*head)->next;   // Move head one node forward
    free(temp);              // Only now is it safe to release the old node
}

Hai điểm đáng để ý khi so với hoạt ảnh. Thứ nhất, insertAtHead và deleteHead không hề có vòng lặp — chúng là O(1), nên dù danh sách có 3 node hay 3 triệu node thì cũng nhanh như nhau. Ngược lại insertAtTail phải duyệt hết danh sách để tìm node cuối, nên nó là O(N): bấm Insert Tail trên danh sách càng dài, đường đi càng xa (đó cũng là lý do các cài đặt thực tế thường giữ thêm một con trỏ tail, y như Queue ở Bài 10).

Thứ hai, hãy nhìn kỹ deleteHead: bắt buộc phải lưu temp = *head trước khi dời head đi. Nếu bạn đảo thứ tự — dời head trước rồi mới free — thì địa chỉ của node cũ đã mất, không còn cách nào giải phóng nó nữa; đó chính xác là một rò rỉ bộ nhớ như Bài 9 đã mô tả.

4. Tại sao học cấu trúc dữ liệu lại quan trọng?

Mỗi cấu trúc dữ liệu sinh ra đều được thiết kế tối ưu cho một mục đích sử dụng nhất định:

• Danh sách liên kết (Linked List): Tối ưu cho việc chèn và xóa dữ liệu ở bất kỳ vị trí nào (độ phức tạp O(1) nếu đã biết vị trí), khắc phục nhược điểm kích thước tĩnh của Mảng.
• Ngăn xếp (Stack): Cực kỳ hiệu quả khi cần lưu trữ lịch sử để "quay lui" (Undo trong MS Word, nút Back trên trình duyệt, xử lý lời gọi đệ quy trong hệ thống).
• Hàng đợi (Queue): Tối ưu cho việc điều phối tiến trình chạy trước chạy sau (hàng đợi in ấn máy in, lập lịch tác vụ CPU, cơ chế truyền gói tin mạng).