I den här handledningen lär du dig olika typer av länkad lista. Du hittar också implementering av länkad lista i C.
Innan du lär dig om typen av länkad lista, se till att du känner till LinkedList-datastrukturen.
Det finns tre vanliga typer av länkad lista.
- Singly Linked List
- Dubbel länkad lista
- Cirkulär länkad lista
Singly Linked List
Det är det vanligaste. Varje nod har data och en pekare till nästa nod.
Enskilt länkad lista
Noden representeras som:
struct node ( int data; struct node *next; )
En lista med tre medlemmar som är länkade kan skapas som:
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;
Dubbel länkad lista
Vi lägger till en pekare till den föregående noden i en dubbelt länkad lista. Således kan vi gå i båda riktningarna: framåt eller bakåt.
Dubbel länkad lista
En nod representeras som
struct node ( int data; struct node *next; struct node *prev; )
En dubbelt länkad lista med tre medlemmar kan skapas som
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; one->prev = NULL; two->next = three; two->prev = one; three->next = NULL; three->prev = two; /* Save address of first node in head */ head = one;
Cirkulär länkad lista
En cirkulär länkad lista är en variant av en länkad lista där det sista elementet är länkat till det första elementet. Detta bildar en cirkulär slinga.
Cirkulär länkad lista
En cirkulär länkad lista kan antingen vara länkad eller dubbelt länkad.
- för enstaka länkad lista, pekar nästa pekare med det sista objektet på det första objektet
- I den dubbelt länkade listan pekar föregående pekare för det första objektet också på det sista objektet.
En cirkulär tre-medlemss cirkulär länkad lista kan skapas som:
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = one; /* Save address of first node in head */ head = one;
