C Academy · Lektion

Enkellänkade listor

Noder och pekare.

Lektion 1 av 413 steg

Enkellänkade listor är en gratis lektion i C Academy på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för C Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i C Academy innehåller totalt 4 lektioner.

Vad är en länkad lista?

En länkad lista är en kedja av små strukturer som kallas noder. Varje nod innehåller ett värde och en pekare till nästa nod.

Till skillnad från arrayer behöver elementen inte ligga sammanhängande i minnet, och listan kan enkelt växa eller krympa.

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

Definiera en nod

Node-strukturen innehåller data samt struct Node *next, som pekar på nästa nod.

Pekartypen refererar till samma struct, vilket är det som kopplar samman kedjan.

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

Huvudpekaren

En lista identifieras av en enda pekare till dess första nod, som kallas head.

En tom lista är helt enkelt en head som är lika med 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;
}

Allokera en nod

Noder skapas vanligtvis på heapen med malloc så att de överlever funktionen som skapar dem.

Kontrollera alltid returvärdet och kom ihåg att frigöra noderna senare.

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

Piloperatorn

När Ni har en pekare till en struct använder Ni -> för att komma åt medlemmar. n->value betyder samma sak som (*n).value.

Ni kommer att använda piloperatorn hela tiden med länkade listor.

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

Länka två noder

För att koppla ihop noder ställer Ni in den första nodens next så att den pekar på den andra. Den sista nodens next förblir NULL för att markera slutet.

#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 hjälpfunktion för att skapa noder

Upprepad allokering är omständlig, så kapsla in den i en hjälpfunktion som allokerar, initierar och returnerar en ny nod.

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

Bygga en liten lista

Använd hjälpfunktionen för att bygga en lista med tre noder, 1 -> 2 -> 3, genom att kedja ihop next-pekarna.

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

Skriva ut listan

För att skriva ut varje värde börjar Ni vid head och följer next-pekarna tills Ni når NULL.

Detta genomgångsmönster utgör grunden för nästan alla listoperationer.

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

Arrayer jämfört med länkade listor

Arrayer ger snabb åtkomst via index men har fast storlek. Länkade listor gör det enkelt att infoga och ta bort element, men åtkomsten är långsammare eftersom Ni måste gå igenom listan för att nå ett element.

Välj utifrån vilka operationer som dominerar i Ert program.

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

Frigöra hela listan

Varje nod som har allokerats med malloc måste frigöras. Gå igenom listan, men spara nästa pekare innan du frigör varje nod, annars förlorar du resten av kedjan.

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

Snabbtest

Testa din förståelse av länkade listors struktur.

Besvara frågan i den interaktiva lektionen

Sammanfattning

Du har lärt dig grunderna i enkellänkade listor:

En nod innehåller ett värde och en next-pekare; head pekar på den första noden.
Allokera noder med malloc och åtkom medlemmar med ->.
Den sista nodens next är NULL; gå igenom listan genom att följa pekarna.
Frigör alltid varje nod och spara next innan du frigör noden.

Gratis att börja

Lär dig C med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 39
Lektioner: 144

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Enkellänkade listor” gratis?

Ja – hela texten till ”Enkellänkade listor” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i C Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i C Academy innehåller totalt 4 lektioner.

Vad lär jag mig i ”Enkellänkade listor”?

Noder och pekare. Ni övar på C Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig C Academy?

Du behöver inga förkunskaper. Utbildningen i C Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.

Hur lång tid tar lektionen ”Enkellänkade listor”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här C Academy-lektionen?

Ja. Varje C Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

← Tillbaka till C Academy