В този урок ще научите различни видове свързан списък. Също така ще намерите изпълнение на свързания списък в C.
Преди да научите за вида на свързания списък, уверете се, че знаете за структурата на данните LinkedList.
Има три често срещани типа свързан списък.
- Единично свързан списък
- Двойно свързан списък
- Кръгово свързан списък
Единично свързан списък
Той е най-често срещаният. Всеки възел има данни и указател към следващия възел.
Единично свързан списък
Възелът е представен като:
struct node ( int data; struct node *next; )
Тричленен единично свързан списък може да бъде създаден като:
/* 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;
Двойно свързан списък
Добавяме указател към предишния възел в двойно свързан списък. По този начин можем да вървим във всяка посока: напред или назад.
Двойно свързан списък
Възел е представен като
struct node ( int data; struct node *next; struct node *prev; )
Тричленен двойно свързан списък може да бъде създаден като
/* 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;
Кръгово свързан списък
Кръговият свързан списък е вариант на свързан списък, в който последният елемент е свързан с първия елемент. Това образува кръгъл цикъл.
Кръгово свързан списък
Кръгово свързан списък може да бъде еднократно свързан или двойно свързан.
- за единично свързан списък, следващият указател на последния елемент сочи към първия елемент
- В двойно свързания списък, предният указател на първия елемент сочи и последния елемент.
Тричленен кръгов списък с единична връзка може да бъде създаден като:
/* 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;
