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

Зачем нужен список

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

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

Аналогия. Список — как вагонетки: в каждом вагоне лежит груз и есть крючок, за который прицеплен следующий вагон. Последний вагон ни за что не прицеплен — там NULL.

Узел списка

struct Node
{
    int value;            /* полезные данные */
    struct Node *next;    /* адрес следующего узла, NULL — конец */
};

next — указатель на такую же структуру (самоссылочная структура). Без указателя описать цепочку невозможно: поле должно «знать» адрес следующего узла.

Список задаётся указателем на первый узел — головой:

struct Node *head = NULL;   /* пустой список */

Создание узла

Память под узел выделяют динамически, иначе узел исчезнет при выходе из функции:

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

struct Node *make_node(int value)
{
    struct Node *node = malloc(sizeof(*node));
    if (node == NULL)
    {
        return NULL;
    }

    node->value = value;
    node->next = NULL;
    return node;
}

sizeof(*node) — размер узла, а не указателя. node->value — то же, что (*node).value: короткая запись доступа к полю через указатель.

Добавление в начало

Самый простой и быстрый способ: новый узел становится первым.

struct Node *push_front(struct Node *head, int value)
{
    struct Node *node = make_node(value);
    if (node == NULL)
    {
        return head;        /* память не выделилась — список не изменился */
    }

    node->next = head;      /* прицепляем старый список к новому узлу */
    return node;            /* новый узел становится головой */
}

Вызов: head = push_front(head, 10);.

Порядок двух последних строк важен: сначала новый узел цепляется к старому списку, и только потом голова переставляется на него. Если сделать наоборот — потеряете весь список.

Добавление в конец

Для этого нужно дойти до последнего узла:

struct Node *push_back(struct Node *head, int value)
{
    struct Node *node = make_node(value);
    if (node == NULL)
    {
        return head;
    }

    if (head == NULL)
    {
        return node;        /* список был пуст */
    }

    struct Node *p = head;
    while (p->next != NULL)
    {
        p = p->next;        /* ищем последний узел */
    }
    p->next = node;         /* прицепляем */
    return head;
}

Если конец списка нужен часто, держат второй указатель tail — тогда добавление в конец делается за один шаг, как и в начало. Но при удалении хвоста tail придётся обновлять.

Можно также передавать указатель на голову по указателю:

void push_back(struct Node **head, int value)
{
    struct Node *node = make_node(value);
    if (node == NULL)
    {
        return;
    }

    if (*head == NULL)
    {
        *head = node;
        return;
    }

    struct Node *p = *head;
    while (p->next != NULL)
    {
        p = p->next;
    }
    p->next = node;
}

Вызов: push_back(&head, 10);. Здесь struct Node ** нужен, потому что функция может изменить саму переменную head. Это два равноправных способа; в одной программе используйте только один из них, чтобы не путаться с сигнатурами.

Обход и печать

for (struct Node *p = head; p != NULL; p = p->next)
{
    printf("%d ", p->value);
}
printf("\n");

Условие остановки — p != NULL, переход к следующему — p = p->next. Не используйте p->next != NULL как условие всего цикла, если нужно обработать последний узел.

Поиск

struct Node *find(struct Node *head, int value)
{
    for (struct Node *p = head; p != NULL; p = p->next)
    {
        if (p->value == value)
        {
            return p;       /* нашли узел */
        }
    }
    return NULL;            /* не нашли */
}

Функция возвращает указатель на узел или NULL. Вызывающий код обязан проверить результат.

Удаление узла

Удаление первого узла с заданным значением. Нужно помнить предыдущий узел, чтобы перецепить его next через удаляемый:

struct Node *remove_first(struct Node *head, int value)
{
    struct Node *prev = NULL;
    struct Node *cur = head;

    while (cur != NULL && cur->value != value)
    {
        prev = cur;
        cur = cur->next;
    }

    if (cur == NULL)
    {
        return head;        /* такого значения нет */
    }

    if (prev == NULL)
    {
        head = cur->next;   /* удаляем первый узел */
    }
    else
    {
        prev->next = cur->next;   /* «перепрыгиваем» удаляемый узел */
    }

    free(cur);
    return head;
}

Удаление всех узлов с заданным значением:

struct Node *remove_all(struct Node *head, int value)
{
    struct Node *cur = head;
    struct Node *prev = NULL;

    while (cur != NULL)
    {
        if (cur->value == value)
        {
            struct Node *next = cur->next;
            if (prev == NULL)
            {
                head = next;
            }
            else
            {
                prev->next = next;
            }
            free(cur);
            cur = next;     /* prev не двигаем: следующий узел может тоже совпасть */
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }

    return head;
}

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

void free_list(struct Node *head)
{
    while (head != NULL)
    {
        struct Node *next = head->next;   /* СНАЧАЛА запоминаем следующий узел */
        free(head);
        head = next;
    }
}

Если вызвать free(head) до сохранения head->next, обратиться к next будет уже нельзя — это классическая ошибка. После освобождения вызывающий код должен обнулить свою голову: head = NULL;.

Разворот списка

Разворот делается за один проход, без создания нового списка:

struct Node *reverse(struct Node *head)
{
    struct Node *prev = NULL;
    struct Node *cur = head;

    while (cur != NULL)
    {
        struct Node *next = cur->next;   /* запоминаем следующий */
        cur->next = prev;                /* разворачиваем ссылку */
        prev = cur;                      /* сдвигаем prev */
        cur = next;                      /* сдвигаем cur */
    }

    return prev;                         /* новая голова */
}

Вызов: head = reverse(head);.

Длина и сумма

int list_length(struct Node *head)
{
    int count = 0;
    for (struct Node *p = head; p != NULL; p = p->next)
    {
        count++;
    }
    return count;
}

int list_sum(struct Node *head)
{
    int sum = 0;
    for (struct Node *p = head; p != NULL; p = p->next)
    {
        sum += p->value;
    }
    return sum;
}

Список или массив

	Массив	Список
Размер	фиксирован при объявлении	растёт по мере надобности
Доступ к элементу `i`	сразу, `a[i]`	по цепочке от начала
Вставка/удаление в середину	со сдвигом элементов	перецепка ссылок
Память	один непрерывный блок	узлы в разных местах
Дополнительная память	нет	указатель `next` в каждом узле

Отсюда правило: если нужен быстрый доступ по номеру — массив; если много вставок и удалений — список.

Список структур

В узле может храниться не только число, но и структура:

typedef struct
{
    int id;
    int course;
    double score;
} Student;

typedef struct StudentNode
{
    Student data;
    struct StudentNode *next;
} StudentNode;

Тогда обращение к полям идёт по цепочке: node->data.score. Такой список используется в basic- и advanced-вариантах ЛР3.

Частые ошибки

Ошибка	Что не так
`free(head); head = head->next;`	обращение к уже освобождённой памяти
потеряли `head` при добавлении	список больше не найти
не проверили `malloc` на `NULL`	падение при нехватке памяти
условие обхода `p->next != NULL`	последний узел не обрабатывается
`sizeof(struct Node *)` вместо `sizeof(struct Node)`	выделен размер указателя, а не узла
забыли `free`	утечка памяти
после `free(cur)` читают `cur->next`	неопределённое поведение
`head` не обновили после удаления первого узла	потеря начала списка

Документация

Что запомнить

Список — цепочка узлов; каждый хранит значение и адрес следующего.
Конец списка обозначается NULL.
Добавление в начало — две строки; в конец — обход до последнего узла (или указатель tail).
Удаление перецепляет next предыдущего узла через удаляемый.
Перед free узла сохраните его next.
Доступ к полям через указатель — ->.
После работы освободите все узлы и обнулите голову.