C Academy · Lekcja

Wstawianie i usuwanie

Modyfikowanie listy

Wstawianie i usuwanie to bezpłatna lekcja C Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.

Modyfikowanie listy

Zaletą list wiązanych jest tanie wstawianie i usuwanie. Zamiast przesuwać elementy, jak w tablicy, zmienia się układ wskaźników.

W tej lekcji omówiono wstawianie i usuwanie węzłów w różnych pozycjach.

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

Wstawianie na początku

Wstawianie na początku, czyli przy głowie, ma złożoność O(1). Należy utworzyć nowy węzeł, ustawić jego next tak, aby wskazywał bieżącą głowę, a następnie zaktualizować głowę, wskazując na nowy węzeł.

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

Dlaczego przekazywać podwójny wskaźnik

Aby zmienić głowę wewnątrz funkcji, trzeba przekazać jej adres: struct Node **.

W przeciwnym razie funkcja zmodyfikuje tylko lokalną kopię, a głowa u wywołującego pozostanie bez zmian.

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

Wstawianie na końcu

Dołączanie wymaga przejścia do ostatniego węzła, a następnie podłączenia do jego next nowego węzła.

Jeśli lista jest pusta, nowy węzeł staje się głową.

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

Wstawianie za węzłem

Aby wstawić w środku listy, należy znaleźć węzeł, za którym ma nastąpić wstawienie, a następnie umieścić nowy węzeł między nim a jego obecnym następnikiem.

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

Kolejność operacji ma znaczenie

Podczas wstawiania nowego węzła należy zawsze ustawić jego next przed zmianą wartości next poprzedniego węzła.

W przeciwnym razie traci się odwołanie do reszty listy.

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

Usuwanie pierwszego węzła

Usunięcie głowy polega na zapisaniu jej, przesunięciu głowy na head->next, a następnie zwolnieniu pamięci zajmowanej przez starą głowę.

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

Usuwanie według wartości

Aby usunąć węzeł o określonej wartości, należy śledzić poprzedni węzeł, aby ominąć element docelowy, ustawiając 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;
}

Obsługa przypadku głowy

Usuwanie ma szczególny przypadek, gdy element docelowy jest głową: nie ma wtedy poprzedniego węzła, więc wskaźnik głowy należy zaktualizować bezpośrednio.

Podwójny wskaźnik upraszcza tę operację, jak pokazano powyżej.

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

Unikanie wycieków pamięci

Każdy węzeł usunięty z listy musi zostać zwolniony za pomocą free. Usunięcie węzła bez zwolnienia pamięci powoduje wyciek zajmowanej przez niego pamięci.

Nie należy również zwalniać węzła, który nadal jest połączony z listą, ponieważ prowadzi to do utworzenia wiszącego wskaźnika.

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

Opcjonalne zachowanie kolejności przy wstawianiu

Wstawianie w posortowanej kolejności jest częstym wariantem: należy przejść przez listę do miejsca, w którym wartość pasuje, a następnie wstawić tam nowy węzeł.

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

Szybki sprawdzian

Sprawdź swoją wiedzę na temat modyfikowania list.

Podsumowanie

Nauczył(a) się Pan/Pani wstawiać i usuwać węzły:

Wstawianie na początku ma złożoność O(1); dołączanie i wstawianie w odpowiedniej kolejności wymaga przejścia przez listę.
Należy używać podwójnego wskaźnika, gdy głowa może się zmienić.
Podczas wstawiania należy zachować ostrożność: ustawić next nowego węzła przed ponownym połączeniem elementów.
Przy usuwaniu należy śledzić poprzedni węzeł i zawsze wykonywać free dla usuniętych węzłów.

Często zadawane pytania

Czy lekcja „Wstawianie i usuwanie” jest bezpłatna?

Tak — pełny tekst „Wstawianie i usuwanie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Wstawianie i usuwanie”?

Modyfikowanie listy Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć C Academy?

Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.

Ile czasu zajmuje lekcja „Wstawianie i usuwanie”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?

Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do C Academy