C Academy · Урок

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

Узлы и указатели

«Односвязные списки» — бесплатный урок C Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.

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

Связный список — это цепочка небольших структур, называемых узлами. Каждый узел содержит значение и указатель на следующий узел.

В отличие от массивов, элементы не обязаны располагаться в памяти непрерывно, а список можно легко увеличивать или уменьшать.

#include <stdio.h>

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

int main(void) {
    printf("A node holds a value and a next pointer\n");
    return 0;
}

Определение узла

Структура узла содержит данные и указатель struct Node *next, указывающий на следующий узел.

Тип указателя ссылается на ту же структуру — так узлы соединяются в цепочку.

#include <stdio.h>

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

int main(void) {
    struct Node n;
    n.value = 42;
    n.next = NULL;
    printf("value=%d, next is NULL: %d\n", n.value, n.next == NULL);
    return 0;
}

Указатель на начало списка

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

Пустой список — это просто начало, равное NULL.

#include <stdio.h>

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

int main(void) {
    struct Node *head = NULL;
    printf("List is empty: %d\n", head == NULL);
    return 0;
}

Выделение памяти для узла

Обычно узлы создаются в динамической памяти с помощью malloc, чтобы они продолжали существовать после завершения функции, которая их создаёт.

Всегда проверяйте возвращаемое значение и не забывайте позже освобождать память узлов.

#include <stdio.h>
#include <stdlib.h>

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

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 7;
    n->next = NULL;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Оператор стрелки

Если у Вас есть указатель на структуру, используйте -> для доступа к её членам. n->value означает то же, что и (*n).value.

При работе со связными списками оператор стрелки используется постоянно.

#include <stdio.h>
#include <stdlib.h>

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

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 99;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Соединение двух узлов

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

#include <stdio.h>
#include <stdlib.h>

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

int main(void) {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    a->value = 1; a->next = b;
    b->value = 2; b->next = NULL;
    printf("%d -> %d\n", a->value, a->next->value);
    free(a); free(b);
    return 0;
}

Вспомогательная функция для создания узлов

Повторное выделение памяти утомительно, поэтому заключите его во вспомогательную функцию, которая выделяет память, инициализирует и возвращает новый узел.

#include <stdio.h>
#include <stdlib.h>

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

struct Node *make(int v) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = v;
    n->next = NULL;
    return n;
}

int main(void) {
    struct Node *n = make(5);
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Создание небольшого списка

Используя вспомогательную функцию, создайте список из трёх узлов 1 -> 2 -> 3, соединяя указатели next.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    printf("%d %d %d\n", head->value, head->next->value, head->next->next->value);
    return 0;
}

Вывод списка

Чтобы вывести каждое значение, начните с начала списка и переходите по указателям next, пока не достигнете NULL.

Этот способ обхода лежит в основе почти всех операций со списками.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    for (struct Node *p = head; p; p = p->next)
        printf("%d ", p->value);
    printf("\n");
    return 0;
}

Массивы и связные списки

Массивы обеспечивают быстрый доступ по индексу, но имеют фиксированный размер. Связные списки позволяют легко вставлять и удалять элементы, но доступ к ним медленнее: чтобы добраться до элемента, нужно пройти по списку.

Выбирайте структуру с учётом того, какие операции преобладают в Вашей программе.

#include <stdio.h>

int main(void) {
    printf("Array: O(1) index, costly resize\n");
    printf("List:  O(n) index, cheap insert/delete\n");
    return 0;
}

Освобождение всего списка

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

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    struct Node *p = head;
    while (p) {
        struct Node *nxt = p->next;
        free(p);
        p = nxt;
    }
    printf("freed all nodes\n");
    return 0;
}

Быстрая проверка

Проверьте своё понимание структуры связного списка.

Итоги

Вы изучили основы односвязных списков:

Узел хранит значение и указатель next; голова указывает на первый узел.
Выделяйте память под узлы с помощью malloc, а доступ к членам структуры выполняйте через ->.
У последнего узла next равен NULL; выполняйте обход, переходя по указателям.
Всегда освобождайте каждый узел, сохраняя next до освобождения.

Часто задаваемые вопросы

Урок «Односвязные списки» бесплатный?

Да — полный текст урока «Односвязные списки» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.

Чему я научусь в уроке «Односвязные списки»?

Узлы и указатели Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C Academy?

Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Односвязные списки»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C Academy?

Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к C Academy