V tomto kurzu se naučíte různé typy propojeného seznamu. Implementaci propojeného seznamu najdete také v C.
Než se dozvíte o typu propojeného seznamu, ujistěte se, že víte o datové struktuře LinkedList.
Existují tři běžné typy propojeného seznamu.
- Singly Linked List
- Dvojnásobně propojený seznam
- Kruhový propojený seznam
Singly Linked List
Je to nejběžnější. Každý uzel má data a ukazatel na další uzel.
Jednoduše spojený seznam
Uzel je reprezentován jako:
struct node ( int data; struct node *next; )
Tříčlenný jednotlivě propojený seznam lze vytvořit jako:
/* 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ásobně propojený seznam
Přidáme ukazatel na předchozí uzel v seznamu s dvojitým propojením. Můžeme tedy jít oběma směry: dopředu nebo dozadu.
Dvojnásobně propojený seznam
Uzel je reprezentován jako
struct node ( int data; struct node *next; struct node *prev; )
Tříčlenný dvojitě propojený seznam lze vytvořit jako
/* 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ý propojený seznam
Kruhový propojený seznam je variace propojeného seznamu, ve kterém je poslední prvek propojen s prvním prvkem. Tím se vytvoří kruhová smyčka.
Kruhový propojený seznam
Kruhový propojený seznam může být propojen jednotlivě nebo dvojnásobně.
- pro jednotlivě propojený seznam ukazuje další ukazatel poslední položky na první položku
- V seznamu s dvojnásobným propojením ukazuje předchozí ukazatel první položky také na poslední položku.
Tříčlenný kruhový jednotlivě propojený seznam lze vytvořit jako:
/* 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;
