C Language
Listes liées

Remarques

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

Insertion d'un nœud au début d'une liste liée séparément

Le code ci-dessous demandera des chiffres et continuera à les ajouter au début d'une liste chaînée.

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

Explication pour l'insertion de nœuds

Afin de comprendre comment nous ajoutons des nœuds au début, examinons les scénarios possibles:

1. La liste est vide, nous devons donc ajouter un nouveau nœud. Dans ce cas, notre mémoire ressemble à ceci: HEAD est un pointeur sur le premier nœud:

| HEAD | --> NULL

La ligne currentNode->next = *headNode; assignera la valeur de currentNode->next pour être NULL puisque headNode commence à l'origine à la valeur NULL .

Maintenant, nous voulons définir notre pointeur de nœud principal pour qu'il pointe vers notre nœud actuel.

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

Ceci est fait avec *headNode = currentNode;

2. La liste est déjà remplie. nous devons ajouter un nouveau nœud au début. Par souci de simplicité, commençons par 1 nœud:

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

Avec currentNode->next = *headNode , la structure de données ressemble à ceci:

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

Ce qui doit évidemment être modifié depuis que *headNode doit pointer sur currentNode .

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

Ceci est fait avec *headNode = currentNode;

Insérer un noeud à la nième position

Jusqu'à présent, nous avons envisagé d' insérer un nœud au début d'une liste liée séparément . Cependant, la plupart du temps, vous souhaiterez également pouvoir insérer des nœuds ailleurs. Le code écrit ci-dessous montre comment il est possible d'écrire une fonction insert() pour insérer des noeuds n'importe où dans les listes liées.

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

Inverser une liste chaînée

Vous pouvez également effectuer cette tâche de manière récursive, mais j'ai choisi dans cet exemple d'utiliser une approche itérative. Cette tâche est utile si vous insérez tous vos nœuds au début d'une liste chaînée . Voici un exemple:

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

Explication de la méthode de la liste inversée

Nous commençons le previousNode par NULL , puisque nous savons à la première itération de la boucle, si nous cherchons le noeud avant le premier noeud principal, ce sera NULL . Le premier nœud deviendra le dernier nœud de la liste et la variable suivante sera naturellement NULL .

Fondamentalement, l'idée d'inverser la liste des liens ici est que nous inversons les liens eux-mêmes. Le membre suivant de chaque nœud deviendra le nœud avant, comme ceci:

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

Où chaque nombre représente un nœud. Cette liste deviendrait:

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

Enfin, la tête devrait plutôt pointer vers le 5ème nœud et chaque nœud devrait pointer vers le nœud précédent.

Le nœud 1 devrait pointer sur NULL car il n'y avait rien avant lui. Le nœud 2 doit pointer sur le nœud 1, le nœud 3 doit pointer sur le nœud 2, et cetera.

Cependant, il y a un petit problème avec cette méthode. Si nous rompons le lien vers le nœud suivant et le changeons pour le nœud précédent, nous ne pourrons pas traverser le nœud suivant dans la liste, car le lien vers celui-ci a disparu.

La solution à ce problème consiste simplement à stocker l'élément suivant dans une variable ( nextNode ) avant de modifier le lien.

Une liste doublement liée

Un exemple de code montrant comment les nœuds peuvent être insérés dans une liste à double lien, comment la liste peut facilement être inversée et comment elle peut être imprimée en sens inverse.

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

Notez que parfois, stocker un pointeur sur le dernier nœud est utile (il est plus efficace de simplement pouvoir sauter directement à la fin de la liste que de devoir parcourir la fin):

struct Node *lastNode = NULL;

Dans ce cas, il est nécessaire de le mettre à jour en cas de modification de la liste.

Parfois, une clé est également utilisée pour identifier des éléments. C'est simplement un membre de la structure Node:

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

La clé est ensuite utilisée lorsque des tâches sont effectuées sur un élément spécifique, comme la suppression d'éléments.