V tejto príručke sa dozviete rôzne typy prepojeného zoznamu. Implementáciu prepojeného zoznamu nájdete aj v C.
Predtým, ako sa dozviete o type prepojeného zoznamu, uistite sa, že viete o dátovej štruktúre LinkedList.
Existujú tri bežné typy prepojeného zoznamu.
- Zoznam so samostatným odkazom
- Dvojnásobne prepojený zoznam
- Kruhový prepojený zoznam
Zoznam so samostatným odkazom
Je to najbežnejšie. Každý uzol má údaje a smerník na nasledujúci uzol.
Samostatne prepojený zoznam
Uzol je reprezentovaný ako:
struct node ( int data; struct node *next; )
Trojčlenný samostatne prepojený zoznam je možné vytvoriť ako:
/* 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;
Dvojnásobne prepojený zoznam
Pridáme ukazovateľ na predchádzajúci uzol v zozname, ktorý je dvojnásobne prepojený. Môžeme teda ísť ktorýmkoľvek smerom: dopredu alebo dozadu.
Dvojnásobne prepojený zoznam
Uzol je reprezentovaný ako
struct node ( int data; struct node *next; struct node *prev; )
Trojčlenný dvojnásobne prepojený zoznam je možné vytvoriť ako
/* 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;
Kruhový prepojený zoznam
Kruhový prepojený zoznam je variáciou prepojeného zoznamu, v ktorom je posledný prvok prepojený s prvým prvkom. Takto sa vytvorí kruhová slučka.
Kruhový prepojený zoznam
Kruhový prepojený zoznam môže byť prepojený jednotlivo alebo dvojnásobne.
- pre jednotlivo prepojený zoznam ukazuje ďalší ukazovateľ poslednej položky na prvú položku
- V zozname, ktorý je dvakrát prepojený, ukazuje ukazovateľ predchádzajúcej prvej položky tiež na poslednú položku.
Trojčlenný kruhový jednotlivo prepojený zoznam je možné vytvoriť ako:
/* 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;
