C Academy · leksjon

Enkelt lenkede lister

Noder og pekere

Leksjon 1 av 413 trinn

Enkelt lenkede lister er en gratis leksjon i C Academy på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i C Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i C Academy inneholder totalt 4 leksjoner.

Hva er en lenket liste?

En lenket liste er en kjede av små strukturer som kalles noder. Hver node inneholder en verdi og en peker til den neste noden.

I motsetning til tabeller trenger ikke elementene å ligge sammenhengende i minnet, og listen kan enkelt vokse eller krympe.

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

Definere en node

Node-strukturen inneholder dataene samt struct Node *next, som peker på den neste noden.

Pointertypen refererer til den samme strukturen, og slik kobles kjeden sammen.

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

Hodepekeren

En liste identifiseres av én enkelt peker til den første noden, kalt hodet.

En tom liste er ganske enkelt et hode som er lik 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;
}

Allokere en node

Noder opprettes vanligvis på heapen med malloc, slik at de lever lenger enn funksjonen som oppretter dem.

Kontroller alltid returverdien, og husk å frigjøre nodene senere.

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

Piloperatoren

Når De har en peker til en struct, bruker De -> for å få tilgang til medlemmene. n->value betyr det samme som (*n).value.

De kommer til å bruke piloperatoren hele tiden med lenkede lister.

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

Koble sammen to noder

For å koble sammen noder setter De next i den første til å peke på den andre. next i den siste noden forblir NULL for å markere slutten.

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

En hjelpefunksjon for å opprette noder

Gjentatt allokering er tungvint, så pakk den inn i en hjelpefunksjon som allokerer, initialiserer og returnerer en ny node.

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

Bygge en liten liste

Bruk hjelpefunksjonen til å bygge en liste med tre noder, 1 -> 2 -> 3, ved å lenke sammen next-pekerne.

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

Skrive ut listen

For å skrive ut alle verdiene starter De ved hodet og følger next-pekerne til De når NULL.

Dette traverseringsmønsteret danner grunnlaget for nesten alle listeoperasjoner.

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

Tabeller kontra lenkede lister

Tabeller gir rask tilgang via indeks, men har fast størrelse. Lenkede lister gjør innsetting og fjerning enkelt, men tilgangen er tregere fordi De må gå gjennom listen for å nå et element.

Velg ut fra hvilke operasjoner som dominerer i programmet Deres.

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

Frigjøre hele listen

Hver node som er allokert med malloc, må frigjøres. Gå gjennom listen, men lagre den neste pekeren før De frigjør hver node, ellers mister De resten av kjeden.

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

Kort sjekk

Test forståelsen Deres av lenkede listers struktur.

Besvar den i den interaktive leksjonen

Oppsummering

De har lært det grunnleggende om enkelt lenkede lister:

En node inneholder en verdi og en next-peker; head peker på den første noden.
Alloker noder med malloc, og få tilgang til medlemmer med ->.
Den siste nodens next er NULL; gå gjennom listen ved å følge pekerne.
Frigjør alltid alle noder, og lagre next før De frigjør noden.

Gratis å komme i gang

Lær deg C med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 39
Leksjoner: 144

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Enkelt lenkede lister» gratis?

Ja – hele teksten i «Enkelt lenkede lister» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av C Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i C Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Enkelt lenkede lister»?

Noder og pekere Du øver på C Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med C Academy?

Ingen tidligere erfaring er nødvendig. C Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.

Hvor lang tid tar leksjonen «Enkelt lenkede lister»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne C Academy-leksjonen?

Ja. Alle C Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til C Academy