U ovom vodiču naučit ćete različite vrste povezanih popisa. Također ćete pronaći implementaciju povezanog popisa u C.
Prije nego što saznate o vrsti povezanog popisa, provjerite znate li strukturu podataka LinkedList.
Postoje tri uobičajene vrste povezanog popisa.
- Popis pojedinačno povezanih
- Popis dvostruko povezanih
- Kružno povezani popis
Popis pojedinačno povezanih
Najčešći je. Svaki čvor ima podatke i pokazivač na sljedeći čvor.
Pojedinačno povezani popis
Čvor je predstavljen kao:
struct node ( int data; struct node *next; )
Tročlani pojedinačno povezani popis može se stvoriti kao:
/* 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;
Popis dvostruko povezanih
Dodamo pokazivač na prethodni čvor na dvostruko povezanom popisu. Dakle, možemo ići u bilo kojem smjeru: naprijed ili unatrag.
Popis dvostruko povezan
Čvor je predstavljen kao
struct node ( int data; struct node *next; struct node *prev; )
Tročlani dvostruko povezani popis može se stvoriti kao
/* 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;
Kružno povezani popis
Kružno povezani popis varijacija je povezanog popisa u kojem je zadnji element povezan s prvim elementom. Tako nastaje kružna petlja.
Kružno povezani popis
Kružno povezani popis može biti pojedinačno ili dvostruko povezan.
- za pojedinačno povezan popis, sljedeći pokazivač posljednje stavke pokazuje na prvu stavku
- Na dvostruko povezanom popisu, prethodni pokazivač prve stavke ukazuje i na posljednju stavku.
Tročlani kružno pojedinačno povezani popis može se stvoriti kao:
/* 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;
