I denne vejledning lærer du forskellige typer af linket liste. Du finder også implementering af linket liste i C.
Før du lærer om typen af den linkede liste, skal du sørge for at kende til den LinkedList-datastruktur.
Der er tre almindelige typer af sammenkædet liste.
- Enkelt forbundet liste
- Dobbelt sammenkædet liste
- Cirkulær sammenkædet liste
Enkelt forbundet liste
Det er den mest almindelige. Hver node har data og en markør til den næste node.
Enkeltkædet liste
Node er repræsenteret som:
struct node ( int data; struct node *next; )
En enkeltliste med tre medlemmer kan oprettes 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;
Dobbelt sammenkædet liste
Vi tilføjer en markør til den forrige node i en dobbeltkoblet liste. Således kan vi gå i begge retninger: fremad eller bagud.
Dobbeltkoblet liste
En node er repræsenteret som
struct node ( int data; struct node *next; struct node *prev; )
En dobbeltkoblet liste med tre medlemmer kan oprettes 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 sammenkædet liste
En cirkulær sammenkædet liste er en variation af en sammenkædet liste, hvor det sidste element er knyttet til det første element. Dette danner en cirkulær løkke.
Cirkulær linket liste
En cirkulær sammenkædet liste kan enten være enkeltkædet eller dobbeltkædet.
- for en enkelt sammenkædet liste, peger den næste markør med det sidste element på det første element
- På den dobbeltkoblede liste peger forrige markør for det første element også på det sidste element.
En tre-medlem cirkulær enkeltstående liste kan oprettes 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;
