Trier la liste chaînée en C++

1. Liste en C++
2. Implémenter une liste chaînée en C++
3. Trier une liste chaînée en C++

Ce didacticiel de programmation trivial illustre l’implémentation de l’opération de tri sur une structure de données de liste liée en C++.

Liste en C++

La liste ou la liste liée est une structure de données linéaire qui peut servir de conteneur de données et stocker les données dans la mémoire. Contrairement aux vecteurs ou aux tableaux, les données de la liste ne nécessitent pas d’emplacements de mémoire consécutifs ; au lieu de cela, les données peuvent être développées dynamiquement et allouées à des emplacements de mémoire de tas arbitraires.

Chaque élément de la liste est appelé un nœud. Chaque nœud d’une liste contient un pointeur pointant vers le nœud suivant de la liste.

Inclure le pointeur vers l’élément suivant dans chaque nœud peut faciliter le chaînage linéaire où chaque élément suivant est accessible via le nœud précédent. Ce chaînage linéaire entre les nœuds est la principale raison de donner à cette structure le nom de liste chaînée.

Plusieurs opérations ADT (Abstract Data Type) peuvent être effectuées sur la liste chaînée comme l’insertion, la suppression, la recherche et même le tri. Nous allons commencer par l’implémentation structurelle de base de la liste chaînée, puis implémenter l’algorithme de tri dans cette classe.

Implémenter une liste chaînée en C++

Maintenant, nous allons commencer la mise en œuvre de la liste liée. Pour cela, nous devons d’abord créer une classe pour Node comme ceci :

template <class T>
class Node {
 public:
  T data;
  Node<T>* next;
  Node() { next = 0; }
};

Dans cette classe, il y a deux membres, l’un pour stocker des données, c’est-à-dire info, et l’autre est le pointeur de la classe pour stocker l’adresse du nœud suivant. La classe est modélisée afin qu’une liste de n’importe quel type de données puisse être créée.

Maintenant, nous allons créer une classe Linked List comme celle-ci :

template <class T>
class LSLL {
 private:
  Node<T>* head;

 public:
  LSLL() { head = 0; }
  void insertAtHead(T val) {
    Node<T>* x = new Node<T>(val);
    x->next = head;
    head = x;
  }
  void displayAll() {
    Node<T>* x = head;
    {
      while (x != 0) {
        cout << x->info << endl;
        x = x->next;
      }
    }
  }
};

Dans cette classe, il y a un constructeur et deux autres fonctions membres pour insérer et afficher les nœuds de la liste.

Trier une liste chaînée en C++

Nous allons implémenter l’algorithme de tri le plus simple, Bubble Sort, pour trier la liste chaînée par ordre croissant. Cet algorithme de tri permute à plusieurs reprises les éléments adjacents s’ils sont placés dans un ordre non trié.

Cette opération est effectuée à plusieurs reprises jusqu’à ce que tous les éléments soient à leur position de tri correcte. Celle-ci sera mise en œuvre comme suit :

void sortLinkedList() {
  Node<T> *curr = head, *temp = NULL;
  int t;
  if (head == NULL) {
    return;
  } else {
    while (curr != NULL) {
      temp = curr->next;
      while (temp != NULL) {
        if (curr->info > temp->info) {
          t = curr->info;
          curr->info = temp->info;
          temp->info = t;
        }
        temp = temp->next;
      }
      curr = curr->next;
    }
  }
}

Le programme pilote sera :

int main() {
  LSLL<int> list;
  list.insertAtHead(50);
  list.insertAtHead(45);
  list.insertAtHead(16);
  cout << "Before sorting" << endl;
  list.displayAll();
  cout << "After Sorting: " << endl;
  list.sortLinkedList();
  list.displayAll();
  return 0;
}

Production:

Before sorting
43
65
13
After Sorting:
13
43
65