Врсте повезане листе

У овом упутству ћете научити различите типове повезане листе. Такође, у Ц. ћете наћи примену повезане листе.

Пре него што сазнате о врсти повезане листе, обавезно сазнајте о структури података ЛинкедЛист.

Постоје три уобичајена типа повезане листе.

  1. Списак појединачно повезаних
  2. Двоструко повезана листа
  3. Кружно повезана листа

Списак појединачно повезаних

Најчешћи је. Сваки чвор има податке и показивач на следећи чвор.

Појединачно повезана листа

Чвор је представљен као:

 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;

Занимљиви Чланци...