Itérer dans une liste en C++

1. Liste en C++
2. Itérer dans une liste en C++

Ce bref tutoriel de programmation traitera d’une structure de données largement utilisée en C++, c’est-à-dire List. Dans la bibliothèque de modèles standard C++ (STL), nous avons une classe List disponible pour cette structure de données.

Il contient un ensemble de fonctions qui peuvent être utilisées pour effectuer plusieurs opérations sur la liste. Plus loin dans cet article, nous verrons comment nous pouvons parcourir la liste et afficher ou modifier une liste.

Liste en C++

La liste, ou 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 et aux tableaux, les données de la liste ne sont pas stockées dans des emplacements de mémoire contigus.

Au lieu de cela, les données sont enregistrées dans des emplacements de mémoire aléatoires. Chaque élément inséré dans la liste est appelé un node.

Chaque node d’une liste contient un pointeur pointant sur l’élément suivant de la liste. C’est pourquoi les éléments de la liste ne sont pas enregistrés dans des emplacements contigus ; par conséquent, il est également appelé liste liée.

Les listes peuvent être classées en deux types :

1. Liste liée individuellement
2. Liste doublement liée

Liste liée individuellement

Dans ce type de liste de liens, tous les nœuds ont 2 parties, une pour les données et une pour stocker le pointeur pointant vers le nœud suivant. La deuxième partie stocke l’adresse du nœud suivant de la liste.

Liste doublement chaînée

Dans ce type de liste de liens, tous les nœuds ont 3 parties, la première partie est pour le pointeur vers le nœud précédent, la seconde pour stocker des données et la troisième contient le pointeur référençant l’élément suivant de la liste.

La classe list en STL contient une liste doublement chaînée. Comme les tableaux, l’insertion et la suppression dans ce type de liste prennent un temps linéaire.

Cependant, les listes ne nécessitent pas de blocs de mémoire contagieux. De plus, développer une liste en attachant un seul nœud de liste à la fois est plus facile et plus rationnel que de réallouer l’ensemble du tableau dynamique (comme le font les vecteurs).

Par conséquent, il est considéré comme une structure de données plus flexible que d’autres structures de données telles que les tableaux et les vecteurs.

Une autre structure de données, forward_list, ne peut itérer que dans une seule direction et est une liste à liaison unique. Par rapport aux autres structures de données, l’inconvénient majeur des listes et des listes directes est qu’on ne peut accéder directement à aucun élément de la liste en donnant sa position comme dans les tableaux.

Par exemple, pour accéder au 5ème élément d’une liste, il faut commencer à partir d’un point final, soit le début ou la fin de cette position, et cela prend un temps linéaire. Les listes utilisent également de la RAM supplémentaire pour stocker les informations de connexion pour chaque élément.

Itérer dans une liste en C++

On peut utiliser la classe iterator de Standard Template Library C++ pour parcourir les éléments de la liste. La syntaxe pour cela est la suivante :

std::list<int>::iterator itr;

Il existe différentes méthodes d’itération dans la liste :

Regardons le code ci-dessous qui utilise différentes fonctions de la classe list.

#include <cstdlib>
#include <iostream>
#include <iterator>
#include <list>
using namespace std;

void displaylist(list<int> l)  // print function to show list
{
  list<int>::iterator myitr;
  for (myitr = l.begin(); myitr != l.end(); ++myitr) cout << "  " << *myitr;
  cout << endl;
}
int main() {
  list<int> mylist1;
  for (int a = 0; a < 10; ++a) {
    int r = 1 + (rand() % 50);
    mylist1.push_back(r);
  }
  cout << "\nData of List 1 : ";
  displaylist(mylist1);
  cout << "\nList first element : " << mylist1.front();
  cout << "\nAfter we pop first element: ";
  mylist1.pop_front();
  displaylist(mylist1);

  cout << "\nWhen we sort the list: ";
  mylist1.sort();
  displaylist(mylist1);

  return 0;
}

Production:

Data of List 1 :   34  37  28  16  44  36  37  43  50  22

List first element : 34
After we pop first element:   37  28  16  44  36  37  43  50  22

When we sort the list:   16  22  28  36  37  37  43  44  50