C Academy · Lekcja

Jednokierunkowe listy wiązane

Węzły i wskaźniki

Jednokierunkowe listy wiązane to bezpłatna lekcja C Academy na CoddyKit. To lekcja 1 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.

Czym jest lista jednokierunkowa?

Lista jednokierunkowa to łańcuch małych struktur nazywanych węzłami. Każdy węzeł przechowuje wartość i wskaźnik do następnego węzła.

W przeciwieństwie do tablic elementy nie muszą zajmować sąsiadujących obszarów pamięci, a listę można łatwo powiększać i zmniejszać.

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

Definiowanie węzła

Struktura węzła zawiera dane oraz struct Node *next wskazujący na następny węzeł.

Typ wskaźnika odwołuje się do tej samej struktury, co umożliwia łączenie węzłów w łańcuch.

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

Wskaźnik head

Listę identyfikuje pojedynczy wskaźnik do jej pierwszego węzła, nazywany głową (head).

Pusta lista to po prostu głowa równa 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;
}

Alokowanie węzła

Węzły zwykle tworzy się na stercie za pomocą malloc, aby przetrwały funkcję, która je tworzy.

Zawsze sprawdzaj zwracaną wartość i pamiętaj, aby później zwolnić węzły.

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

Operator strzałki

Gdy masz wskaźnik do struktury, użyj ->, aby uzyskać dostęp do jej składowych. n->value oznacza to samo co (*n).value.

Operatora strzałki będziesz stale używać podczas pracy z listami jednokierunkowymi.

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

Łączenie dwóch węzłów

Aby połączyć węzły, ustaw pole next pierwszego tak, aby wskazywało na drugi. Pole next ostatniego węzła pozostaje równe NULL, oznaczając koniec listy.

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

Funkcja pomocnicza do tworzenia węzłów

Powtarzające się alokowanie jest uciążliwe, dlatego warto umieścić je w funkcji pomocniczej, która alokuje, inicjalizuje i zwraca 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(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;
}

Budowanie małej listy

Korzystając z funkcji pomocniczej, zbuduj listę trzech węzłów 1 -> 2 -> 3, łącząc wskaźniki 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;
}

Wypisywanie listy

Aby wypisać każdą wartość, rozpocznij od głowy i podążaj za wskaźnikami next, aż dotrzesz do NULL.

Ten schemat przechodzenia stanowi podstawę niemal wszystkich operacji na listach.

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

Tablice a listy jednokierunkowe

Tablice zapewniają szybki dostęp za pomocą indeksu, ale mają stały rozmiar. Listy jednokierunkowe ułatwiają wstawianie i usuwanie elementów, lecz dostęp do nich jest wolniejszy, ponieważ trzeba przejść listę, aby dotrzeć do wybranego elementu.

Wybór zależy od tego, które operacje dominują w programie.

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

Zwalnianie całej listy

Każdy węzeł zaalokowany za pomocą malloc musi zostać zwolniony. Przejdź przez listę, ale przed zwolnieniem każdego węzła zapisz wskaźnik do następnego, inaczej utraci Pan/Pani resztę łańcucha.

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

Szybki sprawdzian

Sprawdź swoją wiedzę na temat struktury list jednokierunkowych.

Podsumowanie

Poznał(a) Pan/Pani podstawy list jednokierunkowych:

Węzeł przechowuje wartość i wskaźnik next; głowa wskazuje pierwszy węzeł.
Węzły należy alokować za pomocą malloc, a dostęp do pól uzyskiwać za pomocą ->.
Wartość next ostatniego węzła to NULL; listę należy przemierzać, podążając za wskaźnikami.
Zawsze należy wykonać free dla każdego węzła, zapisując next przed zwolnieniem pamięci.

Często zadawane pytania

Czy lekcja „Jednokierunkowe listy wiązane” jest bezpłatna?

Tak — pełny tekst „Jednokierunkowe listy wiązane” 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 „Jednokierunkowe listy wiązane”?

Węzły i wskaźniki Ć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 1 z 4.

Ile czasu zajmuje lekcja „Jednokierunkowe listy wiązane”?

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