V tej vadnici boste izvedeli različne vrste povezanih seznamov. Prav tako boste v C. našli izvedbo povezanega seznama.
Preden se naučite o vrsti povezanega seznama, se prepričajte, da poznate strukturo podatkov LinkedList.
Obstajajo tri pogoste vrste povezanega seznama.
- Enotno povezan seznam
- Dvojno povezan seznam
- Krožno povezan seznam
Enotno povezan seznam
Je najpogostejša. Vsako vozlišče ima podatke in kazalec na naslednje vozlišče.
Enotno povezan seznam
Vozlišče je predstavljeno kot:
struct node ( int data; struct node *next; )
Tričlanski posamično povezan seznam lahko ustvarite kot:
/* 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;
Dvojno povezan seznam
Kazalec dodamo na prejšnje vozlišče na dvojno povezanem seznamu. Tako lahko gremo v katero koli smer: naprej ali nazaj.
Dvojno povezan seznam
Vozlišče je predstavljeno kot
struct node ( int data; struct node *next; struct node *prev; )
Tričlanski dvojno povezan seznam lahko ustvarite kot
/* 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;
Krožno povezan seznam
Krožno povezan seznam je različica povezanega seznama, v katerem je zadnji element povezan s prvim elementom. To tvori krožno zanko.
Krožno povezan seznam
Krožno povezan seznam je lahko bodisi posamično povezan ali dvojno povezan.
- za posamezno povezan seznam naslednji kazalec zadnjega elementa kaže na prvi element
- Na dvojno povezanem seznamu prejšnji kazalec prvega elementa kaže tudi na zadnji element.
Tričlanski krožno posamično povezan seznam lahko ustvarite kot:
/* 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;
