In diesem Tutorial lernen Sie verschiedene Arten von verknüpften Listen kennen. Die Implementierung der verknüpften Liste finden Sie auch in C.
Bevor Sie sich mit dem Typ der verknüpften Liste vertraut machen, stellen Sie sicher, dass Sie mit der LinkedList-Datenstruktur vertraut sind.
Es gibt drei gängige Arten von verknüpften Listen.
- Einfach verknüpfte Liste
- Doppelt verknüpfte Liste
- Zirkuläre verknüpfte Liste
Einfach verknüpfte Liste
Es ist am häufigsten. Jeder Knoten hat Daten und einen Zeiger auf den nächsten Knoten.
Einfach verknüpfte Liste
Der Knoten wird dargestellt als:
struct node ( int data; struct node *next; )
Eine dreiköpfige, einfach verknüpfte Liste kann wie folgt erstellt werden:
/* 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;
Doppelt verknüpfte Liste
Wir fügen einen Zeiger auf den vorherigen Knoten in einer doppelt verknüpften Liste hinzu. Wir können also in beide Richtungen gehen: vorwärts oder rückwärts.
Doppelt verknüpfte Liste
Ein Knoten wird dargestellt als
struct node ( int data; struct node *next; struct node *prev; )
Eine dreiköpfige doppelt verknüpfte Liste kann als erstellt werden
/* 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;
Zirkuläre verknüpfte Liste
Eine zirkuläre verknüpfte Liste ist eine Variation einer verknüpften Liste, in der das letzte Element mit dem ersten Element verknüpft ist. Dies bildet eine kreisförmige Schleife.
Zirkuläre verknüpfte Liste
Eine zirkuläre verknüpfte Liste kann entweder einfach oder doppelt verknüpft sein.
- Bei einfach verknüpften Listen zeigt der nächste Zeiger des letzten Elements auf das erste Element
- In der doppelt verknüpften Liste zeigt der vorherige Zeiger des ersten Elements ebenfalls auf das letzte Element.
Eine dreiköpfige, einfach verknüpfte Rundschreiben-Liste kann wie folgt erstellt werden:
/* 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;
