PricingLoginStart free
C Academy · Lektion

Dobbeltkædede lister

Tovejskædning

Lektion 4 af 413 trin

Dobbeltkædede lister er en gratis C Academy-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i C Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. C Academy-kurset indeholder 4 lektioner i alt.

Tovejskædning

En dobbelt sammenkædet liste giver hver knude to pointere: én til next-knuden og én til prev-knuden (den forrige knude).

Det gør det muligt at gå gennem listen i begge retninger og forenkler sletning.

#include <stdio.h>

struct Node {
    int value;
    struct Node *prev;
    struct Node *next;
};

int main(void) {
    printf("Each node links forward and backward\n");
    return 0;
}

Definér knuden

Strukturen tilføjer en prev-pointer ved siden af next. Begge er NULL i listens ender.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 1; n->prev = NULL; n->next = NULL;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

En hjælpefunktion til oprettelse

Som før samler en hjælpefunktion allokeringen ét sted. Den sætter både prev og next til NULL.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };

struct Node *make(int v) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = v; n->prev = NULL; n->next = NULL;
    return n;
}

int main(void) {
    struct Node *n = make(42);
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Forbind knuder i begge retninger

Når du forbinder to knuder, skal du opdatere begge retninger: den første knudes next og den anden knudes prev.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b;
    b->prev = a;
    printf("forward %d, back %d\n", a->next->value, b->prev->value);
    free(a); free(b);
    return 0;
}

Indsæt forrest

Når du indsætter forrest, er den nye knudes next lig med det gamle hoved, det gamle hoveds prev er den nye knude, og derefter flyttes hovedet til den nye knude.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

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

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

Gennemløb fremad

At gå fremad er identisk med en enkelt sammenkædet liste: Følg next, indtil du når NULL.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b; b->prev = a;
    for (struct Node *p = a; p; p = p->next) printf("%d ", p->value);
    printf("\n");
    free(a); free(b);
    return 0;
}

Gennemløb bagud

Den store fordel er, at du fra enhver knude kan gå baglæns ved at følge prev-pointerne, indtil du når hovedet.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2), *c = make(3);
    a->next = b; b->prev = a; b->next = c; c->prev = b;
    for (struct Node *p = c; p; p = p->prev) printf("%d ", p->value);
    printf("\n");
    free(a); free(b); free(c);
    return 0;
}

Sletning er lettere

Fordi hver knude kender sin forgænger, kan du slette den uden at søge efter den forrige knude.

Forbind blot node->prev med node->next i begge retninger.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

void del(struct Node **head, struct Node *n) {
    if (n->prev) n->prev->next = n->next; else *head = n->next;
    if (n->next) n->next->prev = n->prev;
    free(n);
}

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

Opdatér begge naboer

Når du fjerner en knude, skal du altid rette next for den forrige knude og prev for den følgende knude.

Kontrollér for NULL ved hver ende, så du ikke derefererer en manglende nabo.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b; b->prev = a;
    a->next = NULL;
    free(b);
    printf("now only %d remains\n", a->value);
    free(a);
    return 0;
}

Gem en tail-pointer

Mange dobbelt sammenkædede lister gemmer også en tail-pointer til den sidste knude, hvilket muliggør tilføjelse sidst på O(1) og gennemløb bagud fra slutningen.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

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

Afvejninger

Dobbelt sammenkædede lister bruger ekstra hukommelse (én ekstra pointer pr. knude) og kræver, at to forbindelser opdateres ved hver ændring.

Til gengæld får du gennemløb i begge retninger og sletning af en kendt knude på O(1). Vælg ud fra dine behov.

#include <stdio.h>

int main(void) {
    printf("Singly: less memory, one-way\n");
    printf("Doubly: more memory, two-way + easy delete\n");
    return 0;
}

Hurtigt tjek

Test din forståelse af dobbelt sammenkædede lister.

Besvar den i den interaktive lektion

Opsummering

Du har lært om dobbelt sammenkædede lister:

  • Hver knude har både prev- og next-pointere.
  • Forbindelse kræver, at begge retninger opdateres.
  • Du kan gennemløbe listen fremad og bagud og slette en kendt knude på O(1).
  • Omkostningen er ekstra hukommelse og flere opdateringer af pointere; en tail-pointer muliggør tilføjelse sidst på O(1).
Gratis at komme i gang

Lær C med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser
39
Lektioner
144
Start gratisSe hele kurset

Ofte stillede spørgsmål

Er lektionen “Dobbeltkædede lister” gratis?

Ja — hele teksten til “Dobbeltkædede lister” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af C Academy-kurset, skal du opgradere til CoddyKit PRO. C Academy-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Dobbeltkædede lister”?

Tovejskædning Du øver dig i C Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på C Academy?

Der kræves ingen tidligere erfaring. C Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.

Hvor lang tid tager lektionen “Dobbeltkædede lister”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne C Academy-lektion?

Ja. Alle C Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

  1. Enkeltkædede lister
  2. Indsættelse og sletning
  3. Gennemløb og søgning
  4. Dobbeltkædede lister
← Tilbage til C Academy