Iterar a través de una lista en C++

1. Lista en C++
2. Iterar a través de una lista en C++

Este breve tutorial de programación discutirá una estructura de datos ampliamente utilizada en C++, es decir, List. En la biblioteca de plantillas estándar (STL) de C++, tenemos una List de clases disponible para esta estructura de datos.

Hay un conjunto de funciones empaquetadas con él que se pueden usar para realizar múltiples operaciones en la lista. Más adelante en este artículo, discutiremos cómo podemos recorrer la lista y ver o editar una lista.

Lista en C++

List, o Linked List, es una estructura de datos lineal que puede servir como contenedor de datos y almacenar los datos en la memoria. A diferencia de los vectores y las matrices, los datos de la lista no se almacenan en ubicaciones de memoria contiguas.

En cambio, los datos se guardan en ubicaciones de memoria aleatorias. Cada elemento insertado en la lista se denomina nodo.

Cada nodo de una lista contiene un puntero que apunta al siguiente elemento de la lista. Esta es la razón por la que los elementos de la lista no se guardan en ubicaciones contiguas; por lo tanto, también se llama Lista enlazada.

Las listas se pueden clasificar en dos tipos:

1. Lista de enlaces individuales
2. Lista doblemente enlazada

Lista de enlaces individuales

En este tipo de lista de enlaces, todos los nodos tienen 2 partes, una es para datos y otra es para almacenar el puntero que apunta al siguiente nodo. La segunda parte almacena la dirección del siguiente nodo de la lista.

Lista doblemente enlazada

En este tipo de lista de enlaces, todos los nodos tienen 3 partes, la primera parte es para el puntero al nodo anterior, la segunda es para almacenar datos y la tercera contiene el puntero que hace referencia al siguiente elemento de la lista.

La clase list en STL contiene una lista doblemente enlazada. Al igual que los arreglos, la inserción y eliminación en este tipo de lista toma un tiempo lineal.

Sin embargo, las listas no requieren bloques de memoria contagiosos. Además, hacer crecer una lista adjuntando un solo nodo de lista a la vez es más fácil y más racional que reasignar toda la matriz dinámica (como lo hacen los vectores).

Por lo tanto, se considera una estructura de datos más flexible que otras estructuras de datos como matrices y vectores.

Otra estructura de datos, forward_list, puede iterar a través de una sola dirección y es una lista enlazada individualmente. En comparación con otras estructuras de datos, la principal desventaja de las listas y las listas de reenvío es que no podemos acceder directamente a ningún elemento de la lista dando su posición como en las matrices.

Por ejemplo, para acceder al quinto elemento de una lista, uno tiene que comenzar desde algún punto final, ya sea al principio o al final de esa posición, y toma una cantidad de tiempo lineal. Las listas también utilizan RAM adicional para almacenar la información de conexión de cada elemento.

Iterar a través de una lista en C++

Podemos usar la clase iterador de la biblioteca de plantillas estándar C++ para recorrer los elementos de la lista. La sintaxis para esto es la siguiente:

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

Hay diferentes métodos para la iteración en la lista:

Veamos el siguiente código que usa diferentes funciones de la clase de lista.

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

Producción :

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