C Language
Verknüpfte Listen

Bemerkungen

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);
}

Einfügen eines Knotens am Anfang einer einfach verknüpften Liste

Der nachstehende Code fordert Sie zur Eingabe von Nummern auf und fügt sie am Anfang einer verknüpften Liste hinzu.

/* 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;
}

Erläuterung zum Einfügen von Knoten

Um zu verstehen, wie wir am Anfang Knoten hinzufügen, werfen wir einen Blick auf mögliche Szenarien:

1. Die Liste ist leer, daher müssen wir einen neuen Knoten hinzufügen. In diesem Fall sieht unser Gedächtnis folgendermaßen aus, wobei HEAD ein Zeiger auf den ersten Knoten ist:

| HEAD | --> NULL

Die Zeile currentNode->next = *headNode; weist den Wert von currentNode->next zu NULL da headNode ursprünglich mit einem NULL Wert beginnt.

Jetzt möchten wir unseren Kopfknotenzeiger so einstellen, dass er auf unseren aktuellen Knoten zeigt.

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

Dies geschieht mit *headNode = currentNode;

2. Die Liste ist bereits ausgefüllt. Wir müssen am Anfang einen neuen Knoten hinzufügen. Der Einfachheit halber beginnen wir mit 1 Knoten:

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

Bei currentNode->next = *headNode sieht die Datenstruktur folgendermaßen aus:

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

Was natürlich geändert werden muss, da *headNode auf currentNode *headNode sollte.

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

Dies geschieht mit *headNode = currentNode;

Einfügen eines Knotens an der n-ten Position

Bisher haben wir uns mit dem Einfügen eines Knotens am Anfang einer einfach verknüpften Liste befasst . Meistens möchten Sie jedoch auch Knoten an anderer Stelle einfügen können. Der folgende Code zeigt, wie es möglich ist, eine insert() Funktion zu schreiben, um Knoten an beliebigen Stellen in die verknüpften Listen einzufügen.

#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;
  }
}

Umkehrung einer verknüpften Liste

Sie können diese Aufgabe auch rekursiv ausführen, aber ich habe mich in diesem Beispiel für einen iterativen Ansatz entschieden. Diese Aufgabe ist hilfreich, wenn Sie alle Knoten am Anfang einer verknüpften Liste einfügen . Hier ist ein Beispiel:

#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;
}

Erklärung für die Reverse List-Methode

Wir starten den previousNode als NULL , da wir bei der ersten Iteration der Schleife wissen, dass wir NULL suchen, wenn wir vor dem ersten Kopfknoten nach dem Knoten suchen. Der erste Knoten wird der letzte Knoten in der Liste, und die nächste Variable sollte natürlich NULL .

Grundsätzlich besteht das Konzept der Umkehrung der verknüpften Liste darin, dass wir die Verknüpfungen selbst umkehren. Das nächste Member jedes Knotens wird der Knoten davor, wie folgt:

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

Jede Zahl steht für einen Knoten. Diese Liste würde zu:

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

Schließlich sollte der Kopf stattdessen auf den fünften Knoten zeigen, und jeder Knoten sollte auf den vor ihm liegenden Knoten zeigen.

Knoten 1 sollte auf NULL da vorher nichts vorlag. Knoten 2 sollte auf Knoten 1 zeigen, Knoten 3 auf Knoten 2 und so weiter.

Es gibt jedoch ein kleines Problem mit dieser Methode. Wenn wir die Verbindung zum nächsten Knoten aufheben und zum vorherigen Knoten ändern, können wir nicht zum nächsten Knoten in der Liste wechseln, da die Verbindung zu diesem Knoten weg ist.

Die Lösung für dieses Problem besteht darin, das nächste Element in einer Variablen ( nextNode ) zu nextNode bevor Sie die Verknüpfung ändern.

Eine doppelt verknüpfte Liste

Ein Codebeispiel, das zeigt, wie Knoten in eine doppelt verknüpfte Liste eingefügt werden können, wie die Liste leicht umgekehrt werden kann und wie sie umgekehrt gedruckt werden kann.

#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;
  }
}

Beachten Sie, dass das Speichern eines Zeigers auf den letzten Knoten manchmal nützlich ist (es ist effizienter, einfach direkt zum Ende der Liste springen zu können, als bis zum Ende durchlaufen zu müssen):

struct Node *lastNode = NULL;

In diesem Fall ist eine Aktualisierung bei Änderungen der Liste erforderlich.

Manchmal wird ein Schlüssel auch zur Identifizierung von Elementen verwendet. Es ist einfach ein Mitglied der Node-Struktur:

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

Der Schlüssel wird dann verwendet, wenn Aufgaben für ein bestimmtes Element ausgeführt werden, z. B. das Löschen von Elementen.