Foto de Karine Avetisyan en Unsplash
Las listas enlazadas son estructuras básicas utilizadas en desarrollo. Tienen diversas aplicaciones y forman el cimiento de estructuras más complejas.
Las listas enlazadas están compuestas de Nodos. Si no sabes que son los nodos, te recomiendo vayas a este post. > Estructura de datos en Python (teoría)
Aparentemente la lista enlazada es una simplemente una serie de nodos. En esencia es eso, sin embargo, la lista contiene otros atributos como “cabecera” y “cola”.
“La cabecera” es el primer nodo contenido en la lista, es el punto de entrada a la lista y “la cola” es el último nodo de la lista, el que su link hace referencia a Null. (En el gráfico de arriba, la cabecera es el nodo_a y la cola es el nodo_c).
La imagen anterior de una lista enlazada contiene tres nodos (nodo_a, nodo_b y nodo_c). Cada nodo contiene un valor de dato asignado y según la secuencia definida el orden es “Perro“, 22 y 3.52.
La lista termina en el nodo_c ya que podemos notar que su link hace referencia a Null.
A diferencia de, por ejemplo, los arreglos en Python, las listas enlazadas poseen links o referencias al siguiente nodo (o anterior), no existe la necesidad de almacenarlos secuencialmente en memoria.
Operaciones comunes en listas enlazadas incluyen:
- Agregar nodos
- Eliminar nodos
- Encontrar un nodo
- Atravesar (o viajar a través de) la lista enlazada.
Agregar y eliminar nodos de una lista enlazada
Como los nodos dentro de una lista enlazada, tienen referencias y enlaces consistentes no podemos simplemente agregar o eliminar nodos sin realizar algunas tareas de mantenimiento a la lista de manera a asegurar su integridad y también evitar tener nodos huérfanos en el proceso.
1. Agregar nodos
1.1 Agregar nodo al inicio de la lista.
Para agregar un nodo al inicio de la lista, debemos primero crear el nodo nuevo. Después, definimos el link de su siguiente nodo el que actualmente está en la cabecera y por último, seteamos el nuevo nodo como cabecera de la lista.
1.2 Agregar nodo al final de la lista.
Para agregar un nodo al final de la lista, hacemos algo similar el nuestro primer caso. Primero, instanciamos nuestro nodo. Después, linkeamos el nodo que se encuentra en la cola de la lista al nuevo nodo, y como paso final, cambiamos el puntero de cola de nuestra lista, al nuevo nodo añadido.
1.3 Agregar nodo en medio de la lista.
Para agregar un nodo al medio de una lista enlazada debemos tomar los siguientes pasos. Primero instanciamos nuestro nuevo nodo, después seteamos el link entre el nodo nuevo y el nodo de la cola de nuestra lista. Luego, cambiamos el link del nodo que anteriormente apuntaba al nodo de la cola, a nuestro nuevo nodo y listo. Abajo una animación para entender mejor.
