Listas enlazadas | Linked List

Repo: https://github.com/umarquez/100DaysOfC0D3/tree/master/8-linked-list

Una lista enlazada es una estructura de datos lineal en la que cada elemento de la lista es almacenado en un nodo, estos nodos no se encuentran necesariamente en orden, cada nodo podría esta conectado por lo menos a otro haciendo referencia a la ubicación de este último; esto forma una cadena de elementos (o cinta) que puede ser recorrida en por lo menos un sentido, obteniendo en elemento almacenado en el nodo actual, emulando a la cabeza lectora de una cinta magnética

Lista enlazada & cabeza lectora
Lista enlazada & cabeza lectora

Tipos de listas

Simple

Cada nodo apunta solo al siguiente, el primer nodo no es apuntado por nadie y el último nodo no apunta a ningún otro por lo que solo puede ser recorrido en un solo sentido.

Lista simple
Lista simple

Doble enlace

Cada nodo hace referencia al nodo previo, además del nodo siguiente, esto hace que la lista pueda ser recorrida en ambos sentidos.

El primer nodo no tiene antecesor y el último nodo no tiene predecesor.

Lista doblemente enlazada
Lista doblemente enlazada

Lista circular simple

Hacia un solo sentido, pero el último nodo apunta al inicio de la lista

Lista circular simple
Lista circular simple

Lista circular de enlace doble

En ambos sentidos, pero el primer nodo apunta al final como nodo previo y el último nodo apunta al inicio como nodo siguiente.

Lista circular de enlace doble
Lista circular de enlace doble

Ejemplo

Vamos a realizar un sistema automático de marcado telefónico, en este caso vamos a marcar 10 números aleatorio, aunque bien podrían ser leídos desde un archivo o una base de datos; vamos a almacenar cada dígito a marcar en un nodo de una lista enlazada de tal forma que, sin importar la longitud de esta, nos aseguremos de realizar la marcación.