Структуры данных в C/C++

Односвязный список

Каждый узел хранит значение и ссылку на следующий.

Что такое Односвязный список?

Каждый узел хранит значение и ссылку на следующий.

Создайте, обойдите и удалите linked list.

Важные моменты

Определите инварианты до реализации операций.
Обрабатывайте пустое, полное состояние и отказ памяти.
Оценивайте сложность вместе с ownership.

Примеры кода на C и C++

Запустить →

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

Ожидаемый результат

1 2 3

C++

Запустить →

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

Ожидаемый результат

1 2 3

Сравнение C и C++

C выделяет узлы через malloc и освобождает каждый; unique_ptr C++ освобождает цепочку при уничтожении головы.

Структуры и операции разделены, выделение памяти явно.

C++

Классы и контейнеры защищают инварианты и ресурсы.

Практические задания

Запустите обе версии и изменяйте их, сравнивая гарантии языков.

Проверьте пустое и полное состояния.
Реализуйте очистку и найдите утечки.
Сравните со стандартным контейнером.