CodeUtility
Lập trình thông minh, làm việc hiệu quả!
Cấu trúc dữ liệu trong C/C++

Danh sách liên kết đơn trong C, C++

Trong bài học này, bạn sẽ xây dựng, duyệt và giải phóng một danh sách liên kết đơn trong C và C++.

Giới thiệu

Danh sách liên kết đơn (singly linked list) gồm các nút (node), mỗi nút lưu một giá trị và một con trỏ trỏ đến nút kế tiếp. Khác với mảng, các nút không cần nằm liên tiếp trong bộ nhớ, nên bạn có thể thêm phần tử mới mà không phải dịch chuyển các phần tử khác.

Những điểm quan trọng

  • Xác định những điều kiện luôn phải đúng (invariant) của cấu trúc dữ liệu trước khi viết các thao tác.
  • Xử lý đầy đủ các trường hợp rỗng, đầy và cấp phát bộ nhớ thất bại.
  • Đánh giá cả độ phức tạp lẫn cách quản lý vùng nhớ của từng thao tác.

Xem cách hoạt động

Thêm node ở đầu hoặc cuối và nhấp vào một node để xóa. Nhấn Phát để đi theo các con trỏ next từ head tới NULL.

Code ví dụ bằng C và C++

C
Chạy code →
main.c
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *head = NULL;
    for (int value = 3; value >= 1; --value) {
        Node *node = malloc(sizeof *node);
        if (!node) return 1;
        *node = (Node){value, head};
        head = node;
    }
    while (head) {
        Node *next = head->next;
        printf("%d ", head->value);
        free(head);
        head = next;
    }
    puts("");
    return 0;
}
Kết quả khi chạy
1 2 3
C++
Chạy code →
main.cpp
#include <iostream>
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

int main() {
    std::unique_ptr<Node> head;
    for (int value = 3; value >= 1; --value) {
        head = std::make_unique<Node>(Node{value, std::move(head)});
    }
    for (Node *node = head.get(); node; node = node->next.get()) {
        std::cout << node->value << ' ';
    }
    std::cout << '\n';
}
Kết quả khi chạy
1 2 3

So sánh C và C++

Trong phiên bản C, mỗi nút được cấp phát bằng malloc, và chương trình phải duyệt toàn bộ danh sách để gọi free cho từng nút khi dùng xong. Trong phiên bản C++, các nút được nối với nhau bằng std::unique_ptr, nên khi nút đầu tiên bị hủy, toàn bộ chuỗi phía sau cũng tự động được giải phóng.

C

Dữ liệu (struct) và các thao tác thường tách rời, bộ nhớ được cấp phát và giải phóng thủ công.

C++

Class và container có thể tự bảo vệ tính đúng đắn của dữ liệu và tự quản lý tài nguyên.

Bài tập mở rộng

Hãy chạy cả hai phiên bản, sau đó thử thay đổi code để quan sát sự khác biệt về mức độ an toàn mà mỗi ngôn ngữ mang lại.

  • Thêm kiểm thử cho trạng thái rỗng và khi đạt giới hạn dung lượng.
  • Viết phần giải phóng bộ nhớ và kiểm tra rò rỉ bộ nhớ.
  • So sánh độ phức tạp với container tương ứng của thư viện chuẩn.

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách