Una lista es una estructura de datos secuencial. En una lista enlazada: la posición del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos la posición de memoria del primer elemento. Además es dinámica, es decir, su tamaño cambia durante la ejecución del programa.
Una lista enlazada se puede definir recursivamente de la siguiente manera:
Una lista enlazada es una estructura vacía o
Un elemento de información y un enlace hacia una lista (un nodo).
Gráficamente se suele representar así:
Clasificación de las Listas Enlazadas
Las listas se pueden dividir en 4 categorías:
Simplemente Enlazadas
Cada nodo (elemento) contiene un único enlace que conecta ese nodo al nodo siguiente o nodo sucesor. La lista es eficiente en recorridos directos (“adelante”)
Doblemente enlazadas
Cada nodo contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor. La lista es eficiente tanto como en recorrido directo (“adelante”) como en recorrido inverso (“atrás”).
Circular simplemente enlazada
El último elemento (cola) se enlaza al primer elemento (cabeza), de tal modo que la lista puede se recorrida de modo circular (“anillo”)
Circular doblemente enlazada
El último elemento se enlaza con el primer elemento y viceversa. Esta lista se puede recorrer en modo circular tanto en dirección directa como viceversa.
➡ MIRA: Cómo utilizar los escritorios virtuales de Windows 10 para mejorar la productividad
Definición de una Lista
Una lista es una colección lineal de elementos llamados nodos donde el orden de los mismos se establece mediante punteros o referencias y existe un puntero/referencia especial llamado inicio para localizar al primer elemento.
¿Qué es un Nodo?
Un nodo se divide en 2 partes:
- Dato o Información: Contiene la información del elemento.
- Enlace o Apuntador: Contiene la dirección del siguiente nodo de la lista.
El último nodo de la lista contiene una referencia siguiente «null».
// atributos
public String informacion;
public Nodo enlace;
// el constructor de nodos
Nodo (String n){
informacion = n;
enlace = null;
}
}Cómo Funciona una Lista
Una lista enlazada simple necesita una clase con varios campos, los campos que contienen los datos necesarios (por ejemplo nombre y teléfono) y otro campo que contiene un puntero a la propia a la misma clase. Este puntero se usa para saber dónde está el siguiente nodo de la lista, para saber la posición en memoria del siguiente elemento
public class Nodo{
// atributos
public String nombre;
public String telefono;
// puntero al siguiente nodo
public Nodo siguiente ;
// el constructor de nodos
Nodo (String nom, String tel)
{ nombre=nom;
telefono=tel;
siguiente = null;
}
}Gráficamente se vería algo así:
