У овом упутству ћете научити различите типове повезане листе. Такође, у Ц. ћете наћи примену повезане листе.
Пре него што сазнате о врсти повезане листе, обавезно сазнајте о структури података ЛинкедЛист.
Постоје три уобичајена типа повезане листе.
- Списак појединачно повезаних
- Двоструко повезана листа
- Кружно повезана листа
Списак појединачно повезаних
Најчешћи је. Сваки чвор има податке и показивач на следећи чвор.
Појединачно повезана листа
Чвор је представљен као:
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;
