C Language
Gekoppelde lijsten

Opmerkingen

struct singly_node
{
  struct singly_node * next;
};

struct doubly_node
{
  struct doubly_node * prev;
  struct doubly_node * next;
};

void doubly_node_bind (struct doubly_node * prev, struct doubly_node * next)
{
  prev->next = next;
  next->prev = prev;
}

void doubly_node_make_empty_circularly_list (struct doubly_node * head)
{
  doubly_node_bind (head, head);
}

void doubly_node_make_empty_linear_list (struct doubly_node * head, struct doubly_node * tail)
{
  head->prev = NULL;
  tail->next = NULL;
  doubly_node_bind (head, tail);
}

void doubly_node_insert_between
(struct doubly_node * prev, struct doubly_node * next, struct doubly_node * insertion)
{
  doubly_node_bind (prev, insertion);
  doubly_node_bind (insertion, next);
}

void doubly_node_insert_before
(struct doubly_node * tail, struct doubly_node * insertion)
{
  doubly_node_insert_between (tail->prev, tail, insertion);
}

void doubly_node_insert_after
(struct doubly_node * head, struct doubly_node * insertion)
{
  doubly_node_insert_between (head, head->next, insertion);
}

Een knooppunt invoegen aan het begin van een afzonderlijk gekoppelde lijst

De onderstaande code vraagt om cijfers en blijft deze toevoegen aan het begin van een gekoppelde lijst.

/* This program will demonstrate inserting a node at the beginning of a linked list */

#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node* next;
};


void insert_node (struct Node **head, int nodeValue);
void print_list (struct Node *head);

int main(int argc, char *argv[]) {
  struct Node* headNode;
  headNode = NULL; /* Initialize our first node pointer to be NULL. */
  size_t listSize, i;
  do {
    printf("How many numbers would you like to input?\n");
  } while(1 != scanf("%zu", &listSize));

  for (i = 0; i < listSize; i++) {
    int numToAdd;
    do {
      printf("Enter a number:\n");
    } while (1 != scanf("%d", &numToAdd));

    insert_node (&headNode, numToAdd);
    printf("Current list after your inserted node: \n");
    print_list(headNode);
  }

  return 0;
}

void print_list (struct Node *head) {
  struct node* currentNode = head;

  /* Iterate through each link. */
  while (currentNode != NULL) {
      printf("Value: %d\n", currentNode->data);
      currentNode = currentNode -> next;
  }
}

void insert_node (struct Node **head, int nodeValue) {
  struct Node *currentNode = malloc(sizeof *currentNode);
  currentNode->data = nodeValue;
  currentNode->next = (*head);

  *head = currentNode;
}

Verklaring voor het invoegen van knooppunten

Laten we om te begrijpen hoe we in het begin knooppunten toevoegen, kijken naar mogelijke scenario's:

1. De lijst is leeg, dus we moeten een nieuw knooppunt toevoegen. In dat geval ziet ons geheugen er zo uit, waarbij HEAD een wijzer is naar het eerste knooppunt:

| HEAD | --> NULL

De regel currentNode->next = *headNode; zal de waarde van currentNode->next NULL headNode omdat headNode oorspronkelijk begint met een waarde van NULL .

Nu willen we onze hoofdknooppuntwijzer instellen op onze huidige knooppunt.

  -----      -------------
 |HEAD | --> |CURRENTNODE| --> NULL /* The head node points to the current node */
  -----      -------------

Dit wordt gedaan met *headNode = currentNode;

2. De lijst is al ingevuld; we moeten een nieuw knooppunt aan het begin toevoegen. Laten we voor de eenvoud beginnen met 1 knooppunt:

 -----    -----------
 HEAD --> FIRST NODE --> NULL
 -----    -----------

Met currentNode->next = *headNode ziet de gegevensstructuur er als volgt uit:

 ---------        -----    ---------------------
 currentNode -->  HEAD --> POINTER TO FIRST NODE --> NULL
 ---------        -----    ---------------------

Die uiteraard moet worden gewijzigd, omdat *headNode naar currentNode moet verwijzen.

 ----    -----------    ---------------
 HEAD -> currentNode -->     NODE       -> NULL
 ----    -----------    ---------------

Dit wordt gedaan met *headNode = currentNode;

Een knooppunt invoegen op de nde positie

Tot nu toe hebben we gekeken naar het invoegen van een knooppunt aan het begin van een afzonderlijk gekoppelde lijst . Meestal wilt u echter ook elders knooppunten kunnen invoegen. De onderstaande code laat zien hoe het mogelijk is om een functie insert() te schrijven om overal in de gekoppelde lijsten knooppunten in te voegen.

#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node* next;
};

struct Node* insert(struct Node* head, int value, size_t position);
void print_list (struct Node* head);

int main(int argc, char *argv[]) {
  struct Node *head = NULL; /* Initialize the list to be empty */

  /* Insert nodes at positions with values: */
  head = insert(head, 1, 0);
  head = insert(head, 100, 1);
  head = insert(head, 21, 2);
  head = insert(head, 2, 3);
  head = insert(head, 5, 4);
  head = insert(head, 42, 2);

  print_list(head);
  return 0;
}

struct Node* insert(struct Node* head, int value, size_t position) {
  size_t i = 0;
  struct Node *currentNode;

  /* Create our node */
  currentNode = malloc(sizeof *currentNode);
  /* Check for success of malloc() here! */

  /* Assign data */
  currentNode->data = value;

  /* Holds a pointer to the 'next' field that we have to link to the new node.
     By initializing it to &head we handle the case of insertion at the beginning. */
  struct Node **nextForPosition = &head;
  /* Iterate to get the 'next' field we are looking for.
     Note: Insert at the end if position is larger than current number of elements. */
  for (i = 0; i < position && *nextForPosition != NULL; i++) {
      /* nextForPosition is pointing to the 'next' field of the node.
         So *nextForPosition is a pointer to the next node.
         Update it with a pointer to the 'next' field of the next node. */
      nextForPosition = &(*nextForPosition)->next;
  }

  /* Here, we are taking the link to the next node (the one our newly inserted node should
  point to) by dereferencing nextForPosition, which points to the 'next' field of the node
  that is in the position we want to insert our node at.
  We assign this link to our next value. */
  currentNode->next = *nextForPosition;

  /* Now, we want to correct the link of the node before the position of our
  new node: it will be changed to be a pointer to our new node. */
  *nextForPosition = currentNode;

  return head;
}

void print_list (struct Node* head) {
  /* Go through the list of nodes and print out the data in each node */
  struct Node* i = head;
  while (i != NULL) {
    printf("%d\n", i->data);
    i = i->next;
  }
}

Een gekoppelde lijst omkeren

U kunt deze taak ook recursief uitvoeren, maar ik heb in dit voorbeeld gekozen voor een iteratieve aanpak. Deze taak is handig als u al uw knooppunten aan het begin van een gekoppelde lijst invoegt . Hier is een voorbeeld:

#include <stdio.h>
#include <stdlib.h>

#define NUM_ITEMS 10

struct Node {
  int data;
  struct Node *next;
};

void insert_node(struct Node **headNode, int nodeValue, int position);
void print_list(struct Node *headNode);
void reverse_list(struct Node **headNode);


int main(void) {
  int i;
  struct Node *head = NULL;

  for(i = 1; i <= NUM_ITEMS; i++) {
    insert_node(&head, i, i);
  }
  print_list(head);

  printf("I will now reverse the linked list\n");
  reverse_list(&head);
  print_list(head);
  return 0;
}

void print_list(struct Node *headNode) {
  struct Node *iterator;

  for(iterator = headNode; iterator != NULL; iterator = iterator->next) {
    printf("Value: %d\n", iterator->data);
  }
}

void insert_node(struct Node **headNode, int nodeValue, int position) {
  int i;
  struct Node *currentNode = (struct Node *)malloc(sizeof(struct Node));
  struct Node *nodeBeforePosition = *headNode;

  currentNode->data = nodeValue;

  if(position == 1) {
    currentNode->next = *headNode;
    *headNode = currentNode;
    return;
  }

  for (i = 0; i < position - 2; i++) {
    nodeBeforePosition = nodeBeforePosition->next;
  }

  currentNode->next = nodeBeforePosition->next;
  nodeBeforePosition->next = currentNode;
}

void reverse_list(struct Node **headNode) {
  struct Node *iterator = *headNode;
  struct Node *previousNode = NULL;
  struct Node *nextNode = NULL;

  while (iterator != NULL) {
    nextNode = iterator->next;
    iterator->next = previousNode;
    previousNode = iterator;
    iterator = nextNode;
  }

  /* Iterator will be NULL by the end, so the last node will be stored in
  previousNode.  We will set the last node to be the headNode */
  *headNode = previousNode;
}

Verklaring voor de Reverse List-methode

We beginnen de previousNode als NULL , omdat we weten op de eerste iteratie van de lus, als we op zoek bent naar het knooppunt voor de eerste hoofdnode, zal het NULL . Het eerste knooppunt wordt het laatste knooppunt in de lijst en de volgende variabele moet natuurlijk NULL .

Kortom, het concept van het omdraaien van de gekoppelde lijst is dat we de koppelingen zelf omdraaien. Het volgende lid van elk knooppunt wordt het knooppunt ervoor, als volgt:

Head -> 1 -> 2 -> 3 -> 4 -> 5

Waar elk nummer een knooppunt vertegenwoordigt. Deze lijst zou worden:

1 <- 2 <- 3 <- 4 <- 5 <- Head

Ten slotte moet de kop in plaats daarvan naar het 5e knooppunt wijzen en moet elk knooppunt naar het vorige knooppunt wijzen.

Knooppunt 1 moet naar NULL wijzen, omdat er niets vóór was. Knooppunt 2 moet wijzen naar knooppunt 1, knooppunt 3 moet wijzen naar knooppunt 2, enzovoort.

Er is echter een klein probleem met deze methode. Als we de koppeling naar het volgende knooppunt verbreken en wijzigen in het vorige knooppunt, kunnen we niet doorgaan naar het volgende knooppunt in de lijst, omdat de koppeling er naartoe is verdwenen.

De oplossing voor dit probleem is om het volgende element eenvoudig op te slaan in een variabele ( nextNode ) voordat u de link wijzigt.

Een dubbel gekoppelde lijst

Een voorbeeld van code die laat zien hoe knooppunten kunnen worden ingevoegd in een dubbel gekoppelde lijst, hoe de lijst gemakkelijk kan worden omgekeerd en hoe deze omgekeerd kan worden afgedrukt.

#include <stdio.h>
#include <stdlib.h>

/* This data is not always stored in a structure, but it is sometimes for ease of use */
struct Node {
  /* Sometimes a key is also stored and used in the functions */
  int data;
  struct Node* next;
  struct Node* previous;
};

void insert_at_beginning(struct Node **pheadNode, int value);
void insert_at_end(struct Node **pheadNode, int value);

void print_list(struct Node *headNode);
void print_list_backwards(struct Node *headNode);

void free_list(struct Node *headNode);

int main(void) {
  /* Sometimes in a doubly linked list the last node is also stored */
  struct Node *head = NULL;

  printf("Insert a node at the beginning of the list.\n");
  insert_at_beginning(&head, 5);
  print_list(head);

  printf("Insert a node at the beginning, and then print the list backwards\n");
  insert_at_beginning(&head, 10);
  print_list_backwards(head);

  printf("Insert a node at the end, and then print the list forwards.\n");

  insert_at_end(&head, 15);
  print_list(head);

  free_list(head);

  return 0;
}

void print_list_backwards(struct Node *headNode) {
  if (NULL == headNode)
  {
    return;
  }
  /*
  Iterate through the list, and once we get to the end, iterate backwards to print 
  out the items in reverse order (this is done with the pointer to the previous node).
  This can be done even more easily if a pointer to the last node is stored.
  */
  struct Node *i = headNode;
  while (i->next != NULL) {
    i = i->next; /* Move to the end of the list */
  }

  while (i != NULL) {
    printf("Value: %d\n", i->data);
    i = i->previous;
  }
}

void print_list(struct Node *headNode) {
  /* Iterate through the list and print out the data member of each node */
  struct Node *i;
  for (i = headNode; i != NULL; i = i->next) {
    printf("Value: %d\n", i->data);
  }
}

void insert_at_beginning(struct Node **pheadNode, int value) {
  struct Node *currentNode;

  if (NULL == pheadNode)
  {
    return;
  }
  /* 
  This is done similarly to how we insert a node at the beginning of a singly linked
  list, instead we set the previous member of the structure as well
  */
  currentNode = malloc(sizeof *currentNode);

  currentNode->next = NULL;
  currentNode->previous = NULL;
  currentNode->data = value;

  if (*pheadNode == NULL) { /* The list is empty */
    *pheadNode = currentNode;
    return;
  }

  currentNode->next = *pheadNode;
  (*pheadNode)->previous = currentNode;
  *pheadNode = currentNode;
}

void insert_at_end(struct Node **pheadNode, int value) {
  struct Node *currentNode;

  if (NULL == pheadNode)
  {
    return;
  }

  /*
  This can, again be done easily by being able to have the previous element.  It 
  would also be even more useful to have a pointer to the last node, which is commonly
  used.
  */
  
  currentNode = malloc(sizeof *currentNode);
  struct Node *i = *pheadNode;

  currentNode->data = value;
  currentNode->next = NULL;
  currentNode->previous = NULL;

  if (*pheadNode == NULL) {
    *pheadNode = currentNode;
    return;
  }

  while (i->next != NULL) { /* Go to the end of the list */
    i = i->next;
  }

  i->next = currentNode;
  currentNode->previous = i;
}

void free_list(struct Node *node) {
  while (node != NULL) {
    struct Node *next = node->next;
    free(node);
    node = next;
  }
}

Merk op dat het soms handig is om een aanwijzer naar het laatste knooppunt op te slaan (het is efficiënter om eenvoudig rechtstreeks naar het einde van de lijst te kunnen springen dan om door te gaan naar het einde):

struct Node *lastNode = NULL;

In dat geval is het nodig deze bij te werken bij wijzigingen in de lijst.

Soms wordt een sleutel ook gebruikt om elementen te identificeren. Het is gewoon een lid van de knooppuntstructuur:

struct Node {
  int data;
  int key;
  struct Node* next;
  struct Node* previous;
};

De sleutel wordt vervolgens gebruikt wanneer taken worden uitgevoerd op een specifiek element, zoals het verwijderen van elementen.