Ebben az oktatóanyagban különféle típusú összekapcsolt listákat tanulhat meg. Ezenkívül megtalálja a csatolt lista megvalósítását a C-ben.
Mielőtt megtudná a csatolt lista típusát, győződjön meg arról, hogy tud a LinkedList adatstruktúráról.
A csatolt listáknak három általános típusa van.
- Egyszerűen összekapcsolt lista
- Kétségkívül összekapcsolt lista
- Kör alakú összekapcsolt lista
Egyszerűen összekapcsolt lista
Ez a leggyakoribb. Minden csomópont rendelkezik adatokkal és egy mutatóval a következő csomópontra.
Egyedül linkelt lista
A csomópont a következőképpen jelenik meg:
struct node ( int data; struct node *next; )
Háromtagú, egyenként összekapcsolt lista a következőképpen hozható létre:
/* 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;
Kétségkívül összekapcsolt lista
Hozzáadunk egy mutatót az előző csomóponthoz egy kétszeresen linkelt listában. Így bármelyik irányba haladhatunk: előre vagy hátra.
Kétszer linkelt lista
Egy csomópont a következőképpen jelenik meg:
struct node ( int data; struct node *next; struct node *prev; )
Háromtagú, kétszeresen összekapcsolt lista létrehozható
/* 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;
Kör alakú összekapcsolt lista
A kör alakú linkelt lista egy olyan összekapcsolt lista változata, amelyben az utolsó elem az első elemhez kapcsolódik. Ez egy kör alakú hurkot képez.
Körkörös linkelt lista
A kör alakú linkelt lista lehet egyszeresen vagy kétszeresen összekapcsolva.
- Egyszerűen összekapcsolt lista esetén az utolsó elem következő mutatója az első elemre mutat
- A kétszeresen összekapcsolt listában az első elem előző mutatója az utolsó elemre is mutat.
Háromtagú kör alakú, egyenként összekapcsolt lista hozható létre a következőképpen:
/* 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;
