Las listas son una de las estructuras básicas para resolver problemas implementando algoritmos.
A continuación un ejemplo del uso basico de una lista.
#include <iostream>
#include <list>
int main () {
int arrayInts[] = { 75, 23, 65, 42, 13 };
// crea una lista a partir del array
std::list<int> milista (arrayInts, arrayInts + 5);
milista.push_back(10); // aumenta el numero 10 a la milista.
std::cout << "milista contiene:";
// crea un iterador para recorrer milista.
std::list<int>::iterator it;
// milista.begin() retorna un iterador apuntando al inicio de milista.
// milista.end() retorna un iterador apuntando al final de milista.
for (it = milista.begin(); it != milista.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
}
El anterior código imprime como resultado en consola:
milista contiene: 75 23 65 42 13 10
Por el momento no vimos ninguna diferencia entre una lista y un vector o array, pero las listas tienen una gran ventaja a la hora de insertar nuevos números en medio de la lista y también a hora de eliminar números en la lista.
La complejidad para insertar un número es de $O(1)$ pero es necesario tener un iterador en el lugar donde necesitas insertar el número entonces si necesitas llegar desde el inicio de la lista buscando un numero en especial necesitarás $O(p)$ pasos utilizando un it++ para ir avanzando.
Al igual que insertar para eliminar un valor es necesario un iterador ya que una lista no tiene índices al igual que un array pero si ya estas apuntando al nodo que necesitas eliminar entonces la complejidad será $O(1)$
#include <iostream>
#include <list>
#include <vector>
int main () {
std::list<int> mylist;
std::list<int>::iterator it;
// aca añadimos los valores iniciales
for (int i=1; i<=5; ++i) mylist.push_back(i); // 1 2 3 4 5
// begin() retorna un puntero al primer valor ^
it = mylist.begin();
++it; // "it" apunta al numero 2 ^
mylist.insert (it, 10); // 1 10 2 3 4 5
// "it" aun apunta al numero 2 ^
mylist.insert (it, 2, 20); // 1 10 20 20 2 3 4 5
--it; // "it" ahora apunta al segundo 20 ^
std::vector<int> myvector (2, 30);
mylist.insert (it,myvector.begin(), myvector.end());
// 1 10 20 30 30 20 2 3 4 5
// ^
std::cout << "mylist contiene:";
for (it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
El anterior código imprime lo siguiente en la consola:
mylist contiene: 1 10 20 30 30 20 2 3 4 5
Cuando utilizo C++ y no recuerdo o necesito buscar algunas estructuras o funciones utilizó cplusplus.com y en este caso los ejemplos fueron una traducción de esta página.
referencias:
cplusplus list
