PricingLoginStart free
C Academy · Урок

Вставка и удаление

Изменяйте список

Урок 2 из 413 шагов

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

Изменение списка

Преимущество связных списков — дешёвые вставка и удаление. Вместо сдвига элементов, как в массиве, Вы перестраиваете указатели.

В этом уроке рассматриваются вставка и удаление узлов в разных позициях.

#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(2);
    printf("start: %d\n", head->value);
    free(head);
    return 0;
}

Вставка в начало

Вставка в голову списка выполняется за O(1). Создайте новый узел, установите его 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(2);
    struct Node *fresh = make(1);
    fresh->next = head;
    head = fresh;
    printf("%d -> %d\n", head->value, head->next->value);
    return 0;
}

Зачем передавать двойной указатель

Чтобы изменить голову списка внутри функции, необходимо передать её адрес: struct Node **.

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

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

void push(struct Node **head, int v) {
    struct Node *n = make(v);
    n->next = *head;
    *head = n;
}

int main(void) {
    struct Node *head = NULL;
    push(&head, 5);
    push(&head, 4);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

Вставка в конец

Для добавления в конец нужно дойти до последнего узла, а затем присоединить к его 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;}

void append(struct Node **head, int v) {
    struct Node *n = make(v);
    if (!*head) { *head = n; return; }
    struct Node *p = *head;
    while (p->next) p = p->next;
    p->next = n;
}

int main(void) {
    struct Node *head = NULL;
    append(&head, 1); append(&head, 2);
    printf("%d %d\n", head->value, head->next->value);
    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*n);n->value=v;n->next=NULL;return n;}

void insert_after(struct Node *node, int v) {
    struct Node *n = make(v);
    n->next = node->next;
    node->next = n;
}

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

Порядок действий имеет значение

При вставке всегда устанавливайте next нового узла до изменения 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 *a = make(1), *c = make(3);
    a->next = c;
    struct Node *b = make(2);
    b->next = a->next;
    a->next = b;
    printf("%d %d %d\n", a->value, b->value, c->value);
    return 0;
}

Удаление первого узла

Удаление головы списка означает: сохранить её, переместить голову на head->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;}

void pop(struct Node **head) {
    if (!*head) return;
    struct Node *old = *head;
    *head = old->next;
    free(old);
}

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

Удаление по значению

Чтобы удалить узел с заданным значением, отслеживайте предыдущий узел, чтобы обойти целевой узел, установив prev->next = target->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;}

void del(struct Node **head, int v) {
    struct Node *cur = *head, *prev = NULL;
    while (cur && cur->value != v) { prev = cur; cur = cur->next; }
    if (!cur) return;
    if (prev) prev->next = cur->next; else *head = cur->next;
    free(cur);
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    del(&head, 2);
    printf("%d %d\n", head->value, head->next->value);
    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*n);n->value=v;n->next=NULL;return n;}

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

Избегайте утечек памяти

Каждый узел, удалённый из списка, необходимо освободить с помощью free. Если удалить узел, не освободив его, занятая им память утечёт.

Также никогда не освобождайте узел, пока он остаётся связанным со списком, иначе создаётся висячий указатель.

#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 *n = make(7);
    free(n);
    printf("node freed, no leak\n");
    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*n);n->value=v;n->next=NULL;return n;}

void insert_sorted(struct Node **head, int v) {
    struct Node *n = make(v);
    if (!*head || (*head)->value >= v) { n->next = *head; *head = n; return; }
    struct Node *p = *head;
    while (p->next && p->next->value < v) p = p->next;
    n->next = p->next; p->next = n;
}

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

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

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

Ответь в интерактивном уроке

Итоги

Вы научились вставлять и удалять узлы:

  • Вставка в начало выполняется за O(1), а добавление в конец или вставка с сохранением порядка требуют обхода списка.
  • Используйте двойной указатель, если голова списка может измениться.
  • Вставляйте узлы аккуратно: устанавливайте next нового узла до переподключения связей.
  • Отслеживайте предыдущий узел при удалении и всегда освобождайте удалённые узлы с помощью free.
Можно начать бесплатно

Изучай C с ИИ-репетитором — бесплатно

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

Курсы
39
Уроки
144
Начать учиться бесплатноПосмотреть полный курс

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

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

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

Чему я научусь в уроке «Вставка и удаление»?

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

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

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

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

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

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

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

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

  1. Односвязные списки
  2. Вставка и удаление
  3. Обход и поиск
  4. Двусвязные списки
← Назад к C Academy