Entonces, cuéntame acerca de las listas vinculadas
Habiéndome graduado recientemente de un bootcamp de codificación, he estudiado profundamente las estructuras de datos y los algoritmos para mejorar mis conocimientos fundamentales. Las listas enlazadas son una estructura de datos relativamente simple, pero son la base para estructuras de datos más complejas en el futuro. Este artículo discutirá las listas vinculadas: sus fortalezas, debilidades y cómo implementarlas.
Las estructuras de datos son, en pocas palabras, formas de organizar y almacenar datos de manera eficiente
¿Qué son las estructuras de datos?
Las estructuras de datos son, en pocas palabras, formas de organizar y almacenar datos de manera eficiente. Estos nos permiten almacenar información para que podamos acceder a ellos para más adelante, buscando un elemento específico, clasificándolos para tener un orden determinado o incluso administrando grandes conjuntos de datos. JavaScript tiene estructuras de datos con las que probablemente esté muy familiarizado: matrices y objetos. Se trata de estructuras de datos primitivas que son nativas del idioma. Las estructuras de datos no primitivas son estructuras de datos definidas por el programador. Los ejemplos incluyen pilas, colas, árboles, gráficos y tablas hash.
¿Qué son las listas enlazadas?
Una lista vinculada es una estructura de datos lineal que contiene elementos en orden secuencial. ¿Suena familiar? Son similares a las matrices, pero no son exactamente iguales. Las matrices tienen un índice cero , lo que significa que cada índice se asigna a un valor, y el primer elemento de la matriz comienza en un índice de 0. Puede extraer elementos fácilmente de la matriz, siempre que conozca el índice.
Por otro lado, una lista enlazada consta de nodos que apuntan a otros nodos. Cada nodo solo se conoce a sí mismo y al siguiente nodo. Como estructura de datos lineal, los elementos se organizan en orden. Podría pensar en ello como un tren: cada vagón está conectado al siguiente vagón, y así sucesivamente. Las listas vinculadas no están indexadas , por lo que no puede acceder al quinto elemento directamente. Tendrías que empezar por el principio, ir al siguiente y pasar al siguiente hasta encontrar el quinto elemento. El primer nodo se llama cabeza y el último nodo se llama cola. Hay varios tipos de listas enlazadas: lista enlazada individualmente, lista enlazada doble y lista enlazada circular. Por el bien de este artículo, me centraré en la lista de enlaces individuales.
Acceder a los elementos de toda la matriz es más fácil, pero tiene un costo.
¿Por qué utilizar listas vinculadas en lugar de matrices?
Quizás se esté preguntando, pero ¿por qué usar esto si puedo acceder a elementos directamente con matrices? ¡Esto es verdad! Acceder a los elementos en toda la matriz es más fácil, pero tiene un costo.
Las matrices están indexadas , por lo que siempre que necesite eliminar un elemento desde el principio o el medio, todos los índices siguientes deben cambiarse. Esto también es cierto si necesita insertar un elemento; todos los elementos siguientes deben volver a indexarse. Al insertar o eliminar elementos de una lista vinculada, no es necesario volver a indexar; todo lo que le importa es el nodo al que apunta .
Implementación de una lista enlazada individualmente
Hay varios tipos de listas enlazadas: individual, doble y circular. Las listas vinculadas individualmente son un tipo de lista vinculada donde cada nodo tiene un valor y un puntero al siguiente nodo (nulo si es el nodo de cola). Las listas doblemente enlazadas, por otro lado, tienen un puntero adicional al nodo anterior. Las listas enlazadas circulares son donde el nodo de cola apunta hacia el nodo principal.
Nota: Si eres un aprendiz visual, VisuAlgo es un gran lugar para jugar y ver cómo la estructura de datos sufre cambios.
Si desea omitir el código completo: consulte esta esencia de GitHub .
Creando un nodo
Comencemos por construir un nodo para usar. Tendrá un valor y un puntero siguiente, que indicará su vecino siguiente.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
Comenzaremos construyendo una clase llamada SinglyLinkedList y le daremos una base para el principio, el final y la longitud de la lista.
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
Para agregar un nodo al final, verificaremos si ya hay un encabezado declarado en la lista. De lo contrario, establezca la cabeza y la cola para que sean el nodo recién creado. Si ya existe una propiedad de cabecera, establezca la propiedad siguiente en la cola para el nuevo nodo y la propiedad de cola para que sea el nuevo nodo. Incrementaremos la longitud en 1.
push(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++;
return this;
}
Para eliminar un nodo al final, primero debemos verificar si hay nodos en la lista. Si hay nodos, tenemos que recorrer la lista hasta llegar a la cola. Estableceremos la siguiente propiedad del penúltimo nodo para que sea nula, estableceremos la propiedad de cola en ese nodo, disminuiremos la longitud en 1 y devolveremos el valor del nodo eliminado.
pop() {
if (!this.head) return undefined;
var current = this.head
var newTail = current
while (current.next) {
newTail = current
current = current.next;
}
this.tail = newTail;
this.tail.next = null;
this.length--;
if (this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}
Para eliminar el nodo desde el principio, comprobamos si hay nodos en la lista. Almacenaremos la propiedad del encabezado actual en una variable y configuraremos el encabezado para que sea el siguiente nodo del encabezado actual. Disminuya la longitud en 1 y devuelva el valor del nodo eliminado.
shift() {
if (!this.head) return undefined
var oldHead = this.head;
this.head = oldHead.next;
this.length--
if (this.length===0) {
this.head = null;
this.tail = null;
}
return oldHead
}
Para agregar un nodo al principio, primero creamos el nodo y verificamos si hay una propiedad principal en la lista. Si es así, establezca la siguiente propiedad del nodo recién creado en el encabezado actual, establezca el encabezado en el nuevo nodo e incremente la longitud.
unshift(val) {
var newNode = new Node(val)
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.length++
return this
}
Para acceder a un nodo según su posición en la lista, primero comprobaremos si el índice es válido. Después, recorreremos la lista, mientras mantenemos una variable de contador. Una vez que la variable del contador coincida con el índice, devolveremos el nodo encontrado
get(idx) {
if (idx < 0 || idx >= this.length) return null
var counter = 0;
var current = this.head
while (counter !== idx) {
current = current.next;
counter++;
}
return current;
}
Para cambiar un nodo en función de su posición, primero buscamos el nodo, utilizando el método get y establecemos el valor en el nuevo valor.
set(idx, val) {
var foundNode = this.get(idx)
if (foundNode) {
foundNode.val = val
return true;
}
return false;
}
Para insertar un nodo, primero verificamos el índice. Si es igual a 0, usamos nuestro método unshift. Si es igual a la longitud, la colocamos en la lista. De lo contrario, obtendremos el nodo anterior utilizando el método get en uno menos que el índice. Esencialmente, necesitamos realizar un seguimiento del nodo antes y después del índice seleccionado para asegurarnos de que nuestros punteros se dirijan hacia el nodo correcto.
insert(idx, val) {
if (idx < 0 || idx > this.length) return false;
if (idx === 0) {
this.unshift(val)
return true;
};
if (idx === this.length) {
this.push(val);
return true;
};
var newNode = new Node(val);
var beforeNode = this.get(idx-1);
var afterNode = beforeNode.next;
beforeNode.next = newNode;
newNode.next = afterNode;
this.length++;
return true;
}
Para eliminar un nodo según la posición, usaremos nuestro método get nuevamente y usaremos el mismo principio que usamos para insertar un nodo. Al realizar un seguimiento del nodo anterior al índice elegido, podemos maniobrar nuestros punteros.
remove(idx) {
if (idx < 0 || idx > this.length) return undefined;
if (idx === this.length-1) {
this.pop()
}
if (idx === 0) {
this.shift()
}
var prevNode = this.get(idx-1)
var removeNode = prevNode.next
prevNode.next = removeNode.next
this.length--;
return removeNode;
}
Fortalezas de las listas vinculadas
La ventaja de utilizar una lista vinculada es la capacidad de insertar y eliminar elementos rápidamente. Debido a que las listas vinculadas no están indexadas, insertar elementos es relativamente rápido y fácil.
Agregar al final de la lista vinculada simplemente requiere que la cola anterior apunte al nuevo nodo y que la propiedad de la cola se establezca en el nuevo nodo. Agregar al principio de la lista vinculada es la misma premisa, pero el nuevo nodo apunta al encabezado anterior y la propiedad del encabezado se establece en el nuevo nodo. Fundamentalmente las mismas acciones, por lo que la inserción es O (1).
Nota: Insertar en el medio de una lista vinculada, requiere buscar para encontrar su nodo (O (N)) y luego insertar el nodo (O (1)).
Eliminar un nodo de la lista vinculada puede ser fácil… pero tampoco. Depende de dónde. Eliminar un nodo del principio de la lista es simple: el segundo nodo se convierte en el nuevo encabezado y establecemos el siguiente puntero del anterior encabezado en nulo. Eliminar desde el final es más complicado porque requiere recorrer toda la lista y detenerse en el penúltimo nodo. En el peor de los casos O (N) y en el mejor de los casos O (1).
Debilidades de las listas enlazadas
Las debilidades de una lista vinculada se deben a su falta de reindexación. Debido a que no puede acceder a los elementos directamente, dificulta la búsqueda y el acceso a los elementos.
Buscar y acceder a un nodo en una lista vinculada requiere comenzar desde el principio de la lista y seguir el rastro de rutas de navegación hacia abajo en la lista. Si estamos buscando el nodo al final de la lista, tendremos que revisar toda la lista enlazada, haciendo que el tiempo sea complejo O (N). A medida que crece la lista, crece el número de operaciones. En comparación con una matriz que tiene acceso aleatorio, se necesita un tiempo constante para acceder a un elemento.
¡Eso es!
Las listas vinculadas son excelentes alternativas a las matrices cuando la inserción y eliminación al principio son acciones clave. Las matrices están indexadas, mientras que las listas enlazadas no. Las listas enlazadas también son la estructura de datos fundamental sobre la que se construyen las pilas y las colas, de lo que hablaré en un artículo posterior. Si llegaste hasta aquí, ¡felicitaciones y espero que hayas aprendido algo junto con tu viaje de programación!
