Estructura de datos y algoritmos: lista vinculada
Una lista enlazada es una secuencia de estructuras de datos, que están conectadas entre sí mediante enlaces.
La lista vinculada es una secuencia de vínculos que contiene elementos. Cada enlace contiene una conexión a otro enlace. La lista vinculada es la segunda estructura de datos más utilizada después de la matriz. A continuación se muestran los términos importantes para comprender el concepto de lista vinculada.
Link - Cada enlace de una lista enlazada puede almacenar un dato llamado elemento.
Next - Cada enlace de una lista enlazada contiene un enlace al siguiente enlace llamado Siguiente.
LinkedList - Una lista vinculada contiene el enlace de conexión al primer enlace llamado Primero.
Representación de lista vinculada
La lista enlazada se puede visualizar como una cadena de nodos, donde cada nodo apunta al siguiente nodo.
Según la ilustración anterior, los siguientes son los puntos importantes que deben considerarse.
La lista vinculada contiene un elemento de enlace llamado primero.
Cada enlace lleva un campo de datos y un campo de enlace llamado siguiente.
Cada enlace está vinculado con su siguiente enlace utilizando su siguiente enlace.
El último enlace lleva un enlace como nulo para marcar el final de la lista.
Tipos de lista vinculada
A continuación se muestran los distintos tipos de listas vinculadas.
Simple Linked List - La navegación de elementos es solo hacia adelante.
Doubly Linked List - Los elementos se pueden navegar hacia adelante y hacia atrás.
Circular Linked List - El último elemento contiene el enlace del primer elemento como siguiente y el primer elemento tiene un enlace al último elemento como el anterior.
Operaciones básicas
A continuación se muestran las operaciones básicas respaldadas por una lista.
Insertion - Agrega un elemento al principio de la lista.
Deletion - Elimina un elemento al principio de la lista.
Display - Muestra la lista completa.
Search - Busca un elemento usando la clave dada.
Delete - Elimina un elemento usando la clave dada.
Operación de inserción
Agregar un nuevo nodo en la lista vinculada es una actividad de más de un paso. Aprenderemos esto con los diagramas aquí. Primero, cree un nodo con la misma estructura y busque la ubicación donde debe insertarse.
Imagina que estamos insertando un nodo B (NewNode), entre A (LeftNode) y C(RightNode). Luego apunte B. junto a C -
NewNode.next −> RightNode;Debería verse así:
Ahora, el siguiente nodo a la izquierda debería apuntar al nuevo nodo.
LeftNode.next −> NewNode;
Esto colocará el nuevo nodo en el medio de los dos. La nueva lista debería verse así:
Se deben tomar pasos similares si el nodo se inserta al principio de la lista. Al insertarlo al final, el segundo último nodo de la lista debe apuntar al nuevo nodo y el nuevo nodo apuntará a NULL.
Operación de eliminación
La eliminación también es un proceso de más de un paso. Aprenderemos con la representación pictórica. Primero, localice el nodo de destino que se va a eliminar, utilizando algoritmos de búsqueda.
El nodo izquierdo (anterior) del nodo objetivo ahora debería apuntar al siguiente nodo del nodo objetivo -
LeftNode.next −> TargetNode.next;
Esto eliminará el enlace que apuntaba al nodo de destino. Ahora, usando el siguiente código, eliminaremos a lo que apunta el nodo de destino.
TargetNode.next −> NULL;
Necesitamos usar el nodo eliminado. Podemos mantener eso en la memoria, de lo contrario, simplemente podemos desasignar la memoria y borrar el nodo de destino por completo.
Operación inversa
Esta operación es minuciosa. Necesitamos hacer que el último nodo sea señalado por el nodo principal e invertir toda la lista vinculada.
Primero, recorremos hasta el final de la lista. Debería apuntar a NULL. Ahora, haremos que apunte a su nodo anterior:
Tenemos que asegurarnos de que el último nodo no sea el último nodo. Así que tendremos un nodo temporal, que parece el nodo principal apuntando al último nodo. Ahora, haremos que todos los nodos del lado izquierdo apunten a sus nodos anteriores uno por uno.
Excepto el nodo (primer nodo) señalado por el nodo principal, todos los nodos deben apuntar a su predecesor, convirtiéndolos en su nuevo sucesor. El primer nodo apuntará a NULL.
Haremos que el nodo principal apunte al nuevo primer nodo utilizando el nodo temporal.
La lista vinculada ahora está invertida. Para ver la implementación de la lista vinculada en el lenguaje de programación C, haga clic aquí .