Es gibt drei gängige Arten von verknüpften Listen.
- Einzelne verknüpfte Liste
- Doppelt verkettete Liste
- Zirkulär verkettete Liste
Einfach verknüpfte Liste
Dies ist am häufigsten. Jeder Knoten hat Daten und einen Zeiger auf den nächsten Knoten.
Wobei die Adresse des ersten Knotens ein spezieller Name namens HEAD ist.
Auf den letzten Knoten in der verknüpften Liste wird durch NULL gezeigt.
Der Knoten wird dargestellt als:
struct node { int data; struct node *next; }
Eine einfach verknüpfte Liste mit drei Elementen kann wie folgt erstellt werden:
/* Инициализируем узлы */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Выделяем память */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Назначаем значения данных */ one->data = 1; two->data = 2; three->data = 3; /* Соединяем узлы */ one->next = two; two->next = three; three->next = NULL; /* Сохраняем адрес первого узла в голове */ head = one;
Doppelt verknüpfte Liste
Wir fügen einen Zeiger auf den vorherigen Knoten in der doppelt verknüpften Liste hinzu. Somit können wir in jede Richtung gehen: vorwärts (next) oder rückwärts (prev).
Der Knoten wird dargestellt als:
struct node { int data; struct node *next; struct node *prev; }
Eine doppelt verknüpfte Liste mit drei Mitgliedern kann wie folgt erstellt werden:
/* Инициализируем узлы */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Выделяем память */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Назначаем значения данных */ one->data = 1; two->data = 2; three->data = 3; /* Соединяем узлы */ one->next = two; one->prev = NULL; two->next = three; two->prev = one; three->next = NULL; three->prev = two; /* Сохраняем адрес первого узла в голове */ head = one;
Kreisverknüpfte Liste
Eine kreisförmige verkettete Liste ist eine Variante einer verketteten Liste, bei der das letzte Element mit dem ersten Element verknüpft ist. Dies bildet eine kreisförmige Schleife.
Eine zirkulär verkettete Liste kann entweder einfach verkettet oder doppelt verkettet sein.
- Bei einer einfach verketteten Liste zeigt der next-Zeiger des letzten Elements auf das erste Element;
- In einer doppelt verketteten Liste zeigt der prev-Zeiger des ersten Elements auch auf das letzte Element.
Eine kreisförmige einfach verknüpfte Liste mit drei Mitgliedern kann wie folgt erstellt werden:
/* Инициализируем узлы */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Выделяем память */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Назначаем значения данных */ one->data = 1; two->data = 2; three->data = 3; /* Соединяем узлы */ one->next = two; two->next = three; three->next = one; /* Сохраняем адрес первого узла в голове */ head = one;