CodeUtility
Кодить проще - жить легче!
Структуры данных в C/C++

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

В этом уроке вы создадите, обойдёте и освободите односвязный список на C и на C++.

Введение

Односвязный список (singly linked list) состоит из узлов (nodes), каждый из которых хранит значение и указатель на следующий узел. В отличие от массива, узлам не нужно лежать в памяти рядом, поэтому элемент можно добавить, не сдвигая остальные.

Главное

  • Определите условия, которые всегда должны выполняться (инварианты), прежде чем писать операции.
  • Обрабатывайте случаи пустой и заполненной структуры и ошибки выделения памяти.
  • Оценивайте вместе сложность и управление памятью для каждой операции.

Как это работает

Добавляйте узлы в начало или конец и щёлкните по узлу, чтобы удалить его. Нажмите Запуск, чтобы пройти по указателям next от head до NULL.

Примеры кода на C и 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, а в конце программа должна пройти весь список и вызвать free для каждого узла. В версии на C++ узлы связаны через std::unique_ptr, поэтому при уничтожении первого узла вся цепочка за ним освобождается автоматически.

C

Данные (struct) и операции разделены, а память выделяется и освобождается вручную.

C++

Классы и контейнеры защищают целостность данных и сами управляют своими ресурсами.

Упражнения для практики

Запустите обе версии, а затем измените код, чтобы увидеть разницу в безопасности, которую даёт каждый язык.

  • Добавьте тесты для пустого состояния и момента, когда достигнута максимальная ёмкость.
  • Напишите освобождение памяти и убедитесь, что утечек нет.
  • Сравните сложность с аналогичным контейнером стандартной библиотеки.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи