In deze tutorial leer je verschillende soorten gelinkte lijsten. Ook vindt u implementatie van gekoppelde lijst in C.
Voordat u het type van de gekoppelde lijst leert kennen, moet u de LinkedList-gegevensstructuur kennen.
Er zijn drie veelvoorkomende typen gekoppelde lijsten.
- Afzonderlijk gekoppelde lijst
- Dubbel gekoppelde lijst
- Circulaire gekoppelde lijst
Afzonderlijk gekoppelde lijst
Het komt het meest voor. Elk knooppunt heeft gegevens en een pointer naar het volgende knooppunt.
Enkel gelinkte lijst
Knooppunt wordt weergegeven als:
struct node ( int data; struct node *next; )
Een enkelvoudig gelinkte lijst met drie leden kan worden aangemaakt als:
/* 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;
Dubbel gekoppelde lijst
We voegen een pointer toe aan het vorige knooppunt in een dubbel gekoppelde lijst. We kunnen dus in beide richtingen gaan: vooruit of achteruit.
Dubbel gelinkte lijst
Een knooppunt wordt weergegeven als
struct node ( int data; struct node *next; struct node *prev; )
Een dubbel gekoppelde lijst met drie leden kan worden gemaakt als
/* 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;
Circulaire gekoppelde lijst
Een circulaire gekoppelde lijst is een variatie op een gekoppelde lijst waarin het laatste element is gekoppeld aan het eerste element. Dit vormt een cirkelvormige lus.
Circulaire gekoppelde lijst
Een circulaire gekoppelde lijst kan afzonderlijk of dubbel gekoppeld zijn.
- voor een enkelvoudig gelinkte lijst wijst de volgende wijzer van het laatste item naar het eerste item
- In de dubbel gelinkte lijst wijst de vorige pointer van het eerste item ook naar het laatste item.
Een circulaire enkelvoudig gelinkte lijst met drie leden kan worden aangemaakt als:
/* 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;
