Singly Linked List en JavaScript
Clase 86 de 99 • 30 días de JavaScript
Contenido del curso
¿Qué es una singly linked list?
Una Singly Linked List es una estructura de datos lineal en la que cada elemento (nodo) contiene un valor y un puntero al siguiente nodo en la lista. La lista enlazada comienza con un nodo llamado cabeza (head) que apunta al primer elemento de la lista, y termina con un nodo llamado cola (tail) que apunta a null.
Una Singly Linked List puede ser utilizada para almacenar y organizar datos de manera eficiente, ya que se puede agregar y eliminar elementos de la lista sin tener que mover elementos adicionales.
Complejidad algorítmica
La complejidad de los métodos de las singly linked list con Big o notation, podremos notar que a diferencia de las hash tables puede llegar a tener áreas en las cuales no son la mejor solución.
| Algoritmo | Big o notation |
|---|---|
| Acceder a elementos | O(n) |
| Insertar o remover del INICIO | O(1) |
| Insertar o remover del FINAL | O(n) |
| Insertar o remover del MEDIO | O(n) |
Oportunidades donde puedes usar una singly linked list
Situaciones en las que NO es muy conveniente usarlas
Construyamos una singly linked list
En JavaScript, una single linked list se puede implementar usando clases. Cada nodo de la lista es un objeto que tiene dos propiedades: value, que almacena el valor del nodo, y next, que apunta al siguiente nodo en la lista.
Veamos un ejemplo de cómo se puede construir una single linked list en JavaScript.
class Node { // Esta clase Node representa un nodo en la lista constructor(value) { // tiene un valor y un enlace al siguiente nodo. this.value = value; this.next = null; } } // La clase LinkedList es la lista en sí misma class LinkedList { constructor() { // Tiene una referencia al primer nodo (head) this.head = null; // también tiene una referencia al último nodo (tail) this.tail = null; // y un contador de longitud (length). this.length = 0; } // El método append agrega un nuevo nodo al final de la lista append(value) { const newNode = new Node(value); if (!this.head) { // Si la lista está vacía, head y tail apuntan al nuevo nodo this.head = newNode; this.tail = newNode; // Si la lista no está vacía, } else { // El enlace next del último nodo en la lista apunta al nuevo nodo this.tail.next = newNode; // y tail se actualiza para que apunte al nuevo nodo this.tail = newNode; } this.length++; } // El método prepend agrega un nuevo nodo al inicio de la lista prepend(value) { const newNode = new Node(value); if (!this.head) { // Si la lista está vacía, head y tail apuntan al nuevo nodo this.head = newNode; this.tail = newNode; } else { // Si la lista no está vacía, // el enlace next del nuevo nodo apunta al primer nodo en la lista newNode.next = this.head; // y head se actualiza para que apunte al nuevo nodo. this.head = newNode; } this.length++; } // Elimina un nodo por su valor delete(value) { // Si la lista está vacía, no se hace nada if (!this.head) { return null; } // Si el nodo a eliminar es el primer nodo en la lista if (this.head.value === value) { // El puntero head se actualiza para apuntar al siguiente nodo this.head = this.head.next; this.length--; return; } // En caso contrario // se recorre la lista buscando el nodo anterior al que se quiere eliminar let currentNode = this.head; while (currentNode.next) { // Una vez encontrado, se actualiza el puntero next del nodo anterior // para que apunte al siguiente nodo después del que se quiere eliminar. if (currentNode.next.value === value) { currentNode.next = currentNode.next.next; this.length--; return; } currentNode = currentNode.next; } } }
Todo esto y más lo puedes aprender en el Curso de Estructuras de Datos con JavaScript
