Cấu trúc dữ liệu trong C/C++

Singly linked list

Mỗi node giữ value cùng link tới node sau, cho phép insert mà không dịch phần tử liên tục.

Singly linked list là gì?

Mỗi node giữ value cùng link tới node sau, cho phép insert mà không dịch phần tử liên tục.

Tạo, duyệt và hủy danh sách liên kết đơn.

Điểm quan trọng

Xác định invariant trước khi cài đặt operation.
Xử lý trường hợp rỗng, đầy và cấp phát thất bại.
Đánh giá đồng thời complexity và ownership.

Code ví dụ bằng C và 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;
}

Output dự kiến

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';
}

Output dự kiến

1 2 3

So sánh C và C++

C cấp phát node bằng malloc và phải free từng node; C++ unique_ptr tự giải phóng chain khi head bị hủy.

Struct và operation thường tách rời, cấp phát được quản lý thủ công.

C++

Class và container có thể bảo vệ invariant và tự quản lý tài nguyên.

Bài tập mở rộng

Chạy cả hai phiên bản rồi thay đổi để quan sát khác biệt về bảo đảm của từng ngôn ngữ.

Thêm test cho trạng thái rỗng và capacity boundary.
Cài đặt cleanup rồi kiểm tra memory leak.
So sánh complexity với standard container.