I denne opplæringen lærer du forskjellige typer koblede lister. Du vil også finne implementering av koblet liste i C.
Før du lærer om typen koblet liste, må du sørge for at du vet om LinkedList-datastrukturen.
Det er tre vanlige typer koblede lister.
- Enkelt koblet liste
- Dobbeltkoblet liste
- Sirkulær koblet liste
Enkelt koblet liste
Det er det vanligste. Hver node har data og en peker til neste node.
Enkelt koblet liste
Node er representert som:
struct node ( int data; struct node *next; )
En liste med tre medlemmer, enkeltkoblet, kan opprettes 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;
Dobbeltkoblet liste
Vi legger til en peker til forrige node i en dobbeltkoblet liste. Dermed kan vi gå i begge retninger: fremover eller bakover.
Dobbeltkoblet liste
En node er representert som
struct node ( int data; struct node *next; struct node *prev; )
En dobbelt medlemsliste med tre medlemmer kan opprettes 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;
Sirkulær koblet liste
En sirkulær koblet liste er en variant av en koblet liste der det siste elementet er knyttet til det første elementet. Dette danner en sirkulær sløyfe.
Rundkoblet liste
En sirkulær koblet liste kan være koblet enkeltvis eller dobbelt.
- for enkeltkoblet liste, peker neste peker med siste element til første element
- I den dobbeltkoblede listen peker forrige peker for det første elementet også til det siste elementet.
En sirkulær liste med tre medlemmer kan enkelt opprettes 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;
