Tässä opetusohjelmassa opit erityyppisiä linkitettyjä luetteloita. Linkitetyn luettelon toteutus löytyy myös C: stä.
Ennen kuin opit linkitetyn luettelon tyypistä, varmista, että tiedät LinkedList-tietorakenteen.
Linkitettyjä luetteloita on kolme yleistä tyyppiä.
- Yksin linkitetty luettelo
- Epäillysti linkitetty luettelo
- Pyöreä linkitetty luettelo
Yksin linkitetty luettelo
Se on yleisin. Jokaisella solmulla on tietoja ja osoitin seuraavaan solmuun.
Yksin linkitetty luettelo
Solmu on esitetty seuraavasti:
struct node ( int data; struct node *next; )
Kolmijäseninen linkitetty luettelo voidaan luoda seuraavasti:
/* 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;
Epäillysti linkitetty luettelo
Lisäämme osoittimen edelliseen solmuun kaksinkertaisesti linkitetyssä luettelossa. Siksi voimme mennä kumpaankin suuntaan: eteenpäin tai taaksepäin.
Kaksinkertaisesti linkitetty luettelo
Solmu on esitetty
struct node ( int data; struct node *next; struct node *prev; )
Kolmijäseninen kaksinkertaisesti linkitetty luettelo voidaan luoda nimellä
/* 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;
Pyöreä linkitetty luettelo
Pyöreä linkitetty luettelo on muunnelma linkitetystä luettelosta, jossa viimeinen elementti on linkitetty ensimmäiseen elementtiin. Tämä muodostaa pyöreän silmukan.
Pyöreä linkitetty luettelo
Pyöreä linkitetty luettelo voi olla joko yksin linkitetty tai kaksoissidottu.
- Yksin linkitetyn luettelon viimeisen kohteen seuraava osoitin osoittaa ensimmäisen kohteen
- Kaksinkertaisesti linkitetyn luettelon ensimmäisen kohteen edellinen osoitin osoittaa myös viimeisen kohteen.
Kolmijäseninen pyöreä, linkitetty luettelo voidaan luoda seuraavasti:
/* 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;
