Liste à chaînage unique dans les structures de données

Qu'est-ce qu'une liste à lien unique ?

Une liste simplement chaînée est une structure de données linéaire et unidirectionnelle où les données sont stockées sur les nœuds, et chaque nœud est relié au nœud suivant par un lien. Chaque nœud contient un champ de données et un lien vers le nœud suivant. Les listes simplement chaînées ne peuvent être parcourues que dans un seul sens, contrairement aux listes multilingues. Liste doublement liée peut être parcouru dans les deux sens.

Voici la structure des nœuds d'une liste simplement chaînée :

Structure d'un nœud dans une liste chaînée

Pourquoi utiliser une liste chaînée plutôt qu'un tableau ?

Dans plusieurs cas, une liste chaînée est préférable à une liste chaînée. tableau:

• Nombre d'éléments inconnu : Lorsque le nombre d'éléments requis n'est pas connu au moment de la compilation, une liste chaînée alloue de la mémoire dynamiquement au fur et à mesure que des éléments sont ajoutés.
• Accès aléatoire: Lorsqu'un accès indexé aléatoire n'est pas nécessaire, une liste chaînée est un choix approprié.
• Insertion au milieu : L'insertion au milieu d'un tableau nécessite le décalage des éléments. Une liste chaînée permet l'insertion à n'importe quelle position en modifiant seulement quelques pointeurs.

Operation de liste à chaînage unique

Une liste simplement chaînée est idéale pour l'allocation dynamique de mémoire. Elle prend en charge les opérations standard des listes chaînées : insertion, suppression, recherche, mise à jour, fusion de deux listes et parcours.

Les opérations suivantes sont abordées dans cet article :

• Insertion en tête
• Insertion à la queue
• Insérer après un nœud
• Insérer avant un nœud
• Supprimer le nœud principal
• Supprimer le nœud de queue
• Rechercher et supprimer un nœud
• Parcourir la liste chaînée

Voici un exemple de liste chaînée à quatre nœuds.

Exemple de liste à lien unique

Insertion en tête d'une liste simplement chaînée

Il s'agit d'une opération simple, généralement appelée « ajout d'un élément à une liste simplement chaînée ». Un nouveau nœud est créé et placé en tête de liste.

Pour réaliser cette opération, deux conditions importantes doivent être respectées :

1. Si la liste est vide, le nœud nouvellement créé devient le nœud principal, et son next Le pointeur est NULL.
2. Si la liste n'est pas vide, le nouveau nœud devient le nœud principal, et son next Le pointeur pointe vers le nœud de tête précédent.

Voici le pseudo-code pour insérer un nœud en tête d'une liste chaînée :

function insertAtHead(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  else:
    newNode.next = head
    return newNode

Insertion en tête

Insertion à la fin d'une liste chaînée simple

Insérer un nœud à la fin d'une liste chaînée est similaire à l'insertion en tête. Parcourez la liste jusqu'au nœud de queue, puis indiquez son emplacement. next Pointeur vers le nouveau nœud. Si la tête est NULL, le nouveau nœud devient la tête.

Étape 1) Traversez jusqu'au next Le pointeur du nœud actuel devient NULL.

Étape 2) Créez un nouveau nœud avec la valeur spécifiée.

Étape 3) Attribuez le nouveau nœud comme nœud suivant du nœud de queue.

Le pseudo-code pour insérer un élément à la fin d'une liste unique :

function insertAtEnd(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  while head.next is not NULL:
    head = head.next
  head.next = newNode
  newNode.next = NULL

Insertion à la queue

Insertion après un nœud dans une liste simplement chaînée

L'insertion après un nœud comporte deux étapes : la recherche du nœud cible et l'insertion d'un nouveau nœud à la suite. Il faut parcourir la liste jusqu'à trouver une correspondance, puis insérer le nouveau nœud.

Étape 1) Parcourez le réseau jusqu'à ce que la valeur du nœud actuel soit égale à l'élément recherché.

Étape 2) Définir le nouveau nœud next pointeur vers le nœud actuel next aiguille.

Étape 3) Indiquez le nœud actuel next pointeur vers le nouveau nœud.

Pseudo-code :

function insertAfter(head, value, searchItem):
  newNode = Node(value)
  while head.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Insertion d'un nœud après un nœud dans une liste à lien unique

Insertion avant un nœud dans une liste chaînée simple

Cela s'apparente à une insertion après un nœud. On parcourt l'arbre jusqu'au prochain nœud correspondant à la valeur recherchée, puis on insère le nouveau nœud avant celui-ci.

Étape 1) Parcourez jusqu'à ce que la valeur du nœud suivant soit égale à l'élément de recherche.

Étape 2) Créez un nouveau nœud et définissez ses next pointeur vers le nœud actuel next.

Étape 3) Indiquez le nœud actuel next vers le nouveau nœud.

function insertBefore(head, value, searchItem):
  newNode = Node(value)
  while head.next.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Insertion d'un nœud avant un nœud dans une liste à lien unique

Supprimer la tête de la liste chaînée simple

Le pointeur vers la tête est fourni en paramètre. Le nœud de tête est supprimé et le nœud suivant devient la nouvelle tête. La mémoire du nœud supprimé doit être libérée afin d'éviter les fuites de mémoire.

Étape 1) Attribuez le nœud suivant de la tête comme nouvelle tête.

Étape 2) Libérez la mémoire allouée par le nœud principal précédent.

Étape 3) Renvoie le nouveau nœud principal.

function deleteHead(head):
  temp = head
  head = head.next
  free(temp)
  return head

Supprimer l'en-tête d'une liste chaînée

Supprimer la queue de la liste simplement chaînée

Supprimer le nœud de queue est similaire à la suppression du nœud de tête. La différence réside dans le fait qu'il est nécessaire de parcourir la liste jusqu'à la fin. Dans une liste simplement chaînée, le nœud dont next Le pointeur est NULL, il s'agit du nœud de queue.

Étape 1) Parcourez le réseau jusqu'à juste avant le nœud terminal. Sauvegardez le nœud courant.

Étape 2) Libérez la mémoire du nœud suivant (la queue).

Étape 3) Définir le nœud suivant du nœud actuel sur NULL.

function deleteTail(head):
  while head.next.next is not NULL:
    head = head.next
  free(head.next)
  head.next = NULL

Suppression de la queue d'une liste à lien unique

Rechercher et supprimer un nœud d'une liste chaînée simple

Cette fonction effectue deux tâches : la recherche et la suppression. Elle parcourt la liste jusqu'à sa fin. Si un nœud correspondant est trouvé, elle le supprime et rétablit le lien vers le nœud précédent. next aiguille.

Étape 1) Parcourez la liste jusqu'à sa fin. Vérifiez si le nœud courant correspond au nœud recherché.

Étape 2) Si une correspondance est trouvée, stockez un pointeur vers le nœud actuel.

Étape 3) Le next Le nœud précédent devient le nœud suivant du nœud actuel.

Étape 4) Supprimez le nœud actuel et libérez sa mémoire.

function searchAndDelete(head, searchItem):
  while head.next.next is not NULL and head.next.value != searchItem:
    head = head.next
  temp = head.next
  head.next = head.next.next
  free(temp)

Rechercher et supprimer un nœud de la liste à lien unique

Parcourir une liste simplement chaînée

Une liste simplement chaînée ne permet de la parcourir que de la tête à la queue. Il n'existe aucun pointeur vers le nœud précédent ; le parcours inverse est donc impossible. Chaque nœud est visité successivement, et sa valeur est affichée jusqu'à ce que la valeur NULL soit rencontrée.

Étape 1) Parcourir chaque nœud jusqu'à atteindre NULL.

Étape 2) Imprime la valeur du nœud actuel.

function traverse(head):
  while head is not NULL:
    print head.value
    head = head.next

Exemple de liste à lien unique dans C++

#include<iostream>
using namespace std;
struct Node{
  int data;
  struct Node *next;
};
void insertAtHead(Node* &head, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  if(head != NULL){
    newNode->next = head;
  }
  head = newNode;
  cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
  if(head == NULL){
    insertAtHead(head, value);
    return;
  }
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *temp = head;
  while(temp->next != NULL){
    temp = temp->next;
  }
  temp->next = newNode;
  cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
  Node *temp = NULL;
  if((*headPtr)->data == searchItem){
    temp = *headPtr;
    *headPtr = (*headPtr)->next;
    free(temp);
  } else {
    Node *currentNode = *headPtr;
    while(currentNode->next != NULL){
      if(currentNode->next->data == searchItem){
        temp = currentNode->next;
        currentNode->next = currentNode->next->next;
        free(temp);
        break;
      } else {
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
void insertAfter(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->next->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){
  Node* tempNode = headPointer;
  cout<<"Traversal from head:\t";
  while(tempNode != NULL){
    cout<<tempNode->data;
    if(tempNode->next)
      cout<<" --> ";
    tempNode = tempNode->next;
  }
  cout<<endl;
}
int main(){
  Node *head = NULL;
  insertAtHead(head, 5);
  insertAtHead(head, 6);
  insertAtHead(head, 7);
  insertEnd(head, 9);
  traverse(head);
  searchAndDelete(&head, 6);
  traverse(head);
  insertAfter(head, 7, 10);
  insertBefore(head, 9, 11);
  traverse(head);
}

Sortie

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Traversal from head:    7 --> 6 --> 5 --> 9
Deleted Node    6
Traversal from head:    7 --> 5 --> 9
Inserted 10 after node  7
Inserted 11 before node 9
Traversal from head:    7 --> 10 --> 5 --> 11 --> 9

Exemple de liste à lien unique dans Python

class Node:
  def __init__(self, data=None, next=None):
    self.data = data
    self.next = next
class SinglyLinkedList:
  def __init__(self):
    self.head = None
  def insertAtHead(self, value):
    newNode = Node(data=value)
    if self.head is not None:
      newNode.next = self.head
    self.head = newNode
    print(f'Added {newNode.data} at the front.')
  def insertAtEnd(self, value):
    if self.head is None:
      self.insertAtHead(value)
      return
    newNode = Node(value)
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    print(f'Added {newNode.data} at the end.')
  def searchAndDelete(self, searchItem):
    if self.head is None:
      return
    if self.head.data == searchItem:
      self.head = self.head.next
      print(f'Deleted node\t{searchItem}')
      return
    currentNode = self.head
    while currentNode.next is not None:
      if currentNode.next.data == searchItem:
        currentNode.next = currentNode.next.next
        print(f'Deleted node\t{searchItem}')
        return
      currentNode = currentNode.next
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
  def traverse(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
singlyLinkedList = SinglyLinkedList()
singlyLinkedList.insertAtHead(5)
singlyLinkedList.insertAtHead(6)
singlyLinkedList.insertAtHead(7)
singlyLinkedList.insertAtEnd(9)
singlyLinkedList.traverse()
singlyLinkedList.searchAndDelete(6)
singlyLinkedList.traverse()
singlyLinkedList.insertAfter(7, 10)
singlyLinkedList.insertBefore(9, 11)
singlyLinkedList.traverse()

Sortie

Added 5 at the front.
Added 6 at the front.
Added 7 at the front.
Added 9 at the end.
Traversing from head:   7       6       5       9
Deleted node    6
Traversing from head:   7       5       9
Inserted 10 after node  7
Inserted 11 before node 9
Traversing from head:   7       10      5       11      9

Complexité de la liste à chaînage unique

Il existe deux types de complexité : la complexité temporelle et la complexité spatiale. La complexité temporelle dans le pire des cas et dans le cas moyen est identique pour une liste simplement chaînée.

Complexité temporelle du meilleur cas :

• L'insertion en tête de liste peut être effectuée en O(1). Aucun parcours à l'intérieur de la liste n'est nécessaire.
• La recherche et la suppression peuvent être effectuées en O(1) si l'élément cible se trouve au niveau du nœud principal.

Complexité temporelle moyenne :

• L'insertion dans une liste chaînée prend un temps O(n), où n est le nombre total d'éléments.
• La recherche et la suppression peuvent également prendre O(n), car l'élément cible peut se trouver n'importe où jusqu'au nœud de queue.

Complexité spatiale d'une liste simplement chaînée

Une liste simplement chaînée alloue dynamiquement de la mémoire. Pour stocker n éléments, il alloue n unités de mémoire. La complexité spatiale est donc O(n).

Applications des listes simplement chaînées

Les listes simplement chaînées apparaissent dans de nombreux cas où le parcours en avant uniquement et la mémoire dynamique sont utiles :

• Piles et files d'attente : Stockage sous-jacent pour les piles LIFO et les files d'attente FIFO construites à partir de nœuds.
• Chaînage de tables de hachage : Les collisions sont résolues en enchaînant les entrées dans une liste chaînée simple par compartiment.
• Listes d'adjacence : Les graphes clairsemés utilisent une liste chaînée simple de voisins pour chaque sommet.
• Tableaux de symboles : Les compilateurs et les interpréteurs enchaînent les identifiants dans une liste chaînée simple par portée.
• Allocateurs de mémoire : allocateurs de listes libres track blocs libres sous forme de liste simplement chaînée.

FAQ