Estructuras de Datos: Listas Enlazadas en JavaScript

🦁 Linked List

Ideas/conceptos claves

Linked List son simplemente un conjunto de nodos ordenados que contienen los valores que necesitemos (numbers, strings, boolean, etc). Cada uno tiene un valor y una referencia a un siguiente nodo.

Apuntes

Esta es la anatomía de un linked list
Tenemos el nodo principal o cabeza, luego tenemos diferentes nodos y un nodo final o cola
Cada flecha es su conexión
Existen dos tipos de Linked List en este caso usaremos solo la Singly Linked List

Métodos

Prepend ⇒ Agregar un nodo al inicio
Append ⇒ Agregar un nodo al final
Lookup / Search ⇒ Buscar un nodo
Insert ⇒ insertar un nodo en la lista
Delete ⇒ Borrar un nodo

Singly Linked List

Tenemos un nodo, Se compone de dos factores
- Valor
- Valor del Next

Si deseamos llegar a algún lugar, debemos empezar del Head hasta el lugar especificado
No podemos regresar una vez hemos avanzado en un lugar, sera necesario volver a hacer otro recorrido
Lo característico de esta lista es que sus valores están relacionados con su nodo actual y el siguiente

RESUMEN: Un singly linked list es aquella que en sus nodos están su valor actual y la relación con el siguiente, si deseamos acceder a un determinado valor debemos recorrer si o si todos los elementos anteriores para llegar al lugar deseado.

Jimmy Buriticá Londoño

Excelente resumen

Fabio Gomez

Gracias por tus apuntes amigo!

Carlos Eduardo Gomez García

Una linked listed suele tener la particularidad de "ser un poco lenta" en la búsqueda por el hecho de que tiene que recorrer absolutamente todos los elementos de izquierda a derecha en busca de ese valor. . Un elemento de una linked list (singly) solo conoce al siguiente elemento, pero no conoce al siguiente, es por eso que no te puedes regresar, por eso, si necesitas conocer el valor de un nodo anterior no te queda otra opción más que terminar tu búsqueda y volver a iniciarla. Por eso una linked list no sería la mejor opción para hacer búsqueda de elementos que dependen de otro elemento de la misma linked list:D

Jorge Cruz Perez

Creo que es asi: Un elemento de una linked list (singly) solo conoce al siguiente elemento, pero no conoce al anterior, cierto? Saludos :)

Carlos Eduardo Gomez García

Así es, pequeño typo, ojalá Platzi me dejara corregirlo xd

Fernando Quinteros Gutierrez

😉 Les recomiendo bastante este artículo si desean saber más de esta estructura de datos

Jimmy Buriticá Londoño

Me gusto mucho el articulo, les traigo una frase:

Pensemos en las Singly Linked List como un edificio con escaleras donde cada piso sería un Nodo. Si quisiera ir del piso 1 al piso 5, estoy obligado a pasar por los pisos 2, 3 y 4. Además siempre debo entrar por el primer piso.

Fernando Quinteros Gutierrez

🚀 Esa frase igual me gusto, no los describe de una manera ilustrativa esta estructura de datos

Juan Esteban Galvis

Recuerdo que vi las listas en la universidad con Java, como vimos son nodos (Cajas digamos con valores dentro) y un enlace o referencia al siguiente. Existen varios tipos, por ejemplo:

Simple (Contenido y Siguiente):

Doblemente ligada (Anterior, Contenido y Siguiente)

Circular (Además de doblemente ligada, también conecta el principio y fin de la lista):

Alexis Villalva

Gracias por el aporte :D

Tomás Eduardo González Quiñones

Recuerdo tener este ramo en la universidad, la diferencia era que me quería morir, me las enseñaron por 3 meses y no entendí nada en su momento... ahora llevo 2 días y estoy entendiendo todo, gracias diego, gracias platzi

Juan Sebastián Agudelo

Linked List (Listas enlazadas)

Son un conjutno de nodos, donde en cada nodo esta el valor que guardamos y tambien una referencia en memoria de donde esta el nodo siguiente. . Te dejo este articulo para que profundizes mas sobre las linked list en JS Mas sobre las linked list en JS . Hay dos tipos de linked list, las que solo apuntan a su nodo siguiente, (singly linked list) y las que tienen dos referencias en memoria (Doubly Linked List), los cuales corresponden al nodo anterior y al nodo siguiente. .

Pero pensemos en las Singly Linked List como un edificio con escaleras donde cada piso sería un Nodo. Si quisiera ir del piso 1 al piso 5, estoy obligado a pasar por los pisos 2, 3 y 4. Además siempre debo entrar por el primer piso. . Para recorrer una linked list tenemos que pasar por todos y cada uno de los nodos, y siempre desde la cabeza, entonces ya podemos ver que es un poco ineficiente para algunos casos ya que no podemos acceder al valor de un nodo de manera rapida solo como su indice o su key como si seria el caso en los arrays y las tablas de hash. . Sino que por el contrario debemos de recorrer cada uno de los nodos si o si hasta llegar al que nos interesa.

Usuario anónimo

User

🤔 Un Linked List consume un poco más de memoria que un Array.

Diego Fernando Velesaca Orellana

En que casos prácticos (de la vida real) se debería o podria utilizar linkde lists ?

Rubén Cuello

Pregunta: Parece que javascript tiene ya todo resuelto con array y objetos. Cual sería la funcionalidad extra que me haría considerar usar una "singly linked list" o algún otro tipo de estructuras?

Rony Porraz Vargas

Las Linked list o en español listas enlazadas son otra estructura de datos y un pequeño ejemplo visual seria algo asi

las listas enlazadas tienen nodos donde guardan la información donde tenemos una cabeza que serial el primer nodo y el ultimo que seria la cola.

Las listas enlazadas tienen métodos para acceder o manipular la información

Prepend: permite agregar un nodo al inicio de nuestra lista
Append: Agrega un nodo al final de la lista
Search / Lookup: Busca un nodo en la lista
Insert: Inserta un nodo en la lista
Delete: Borra un nodo Y dirias, ¿Por qué usar una lista enlazada en vez de un array? pues te muestro ventajas
Las listas no guardan de forma secuencial en memoria los datos, como lo hace un array, pueden estar "regados en memoria", siempre y cuando los nodos apunten al siguiente
Tienen longitud variable A su vez también las listas tiene algunas desventajas contra los arrays
Como los datos no están de manera secuencial y no pueden tener un índice no podríamos hacer accesos aleatorios a la lista
Si queremos un elemento tendríamos que recorrer toda nuestra lista desde el principio

Si quieres saber más de las listas te dejo este video que me pareció muy descriptivo que encontré https://www.youtube.com/watch?v=0NzAFk1CwaQ

Ana Rotela Cabrera

Hace 2 años

Tipos de Linked List

Singly Linked List: Cada nodo apunta solo al siguiente nodo (como una cadena de eslabones).
Doubly Linked List: Cada nodo apunta tanto al nodo anterior como al siguiente, permitiendo moverse en ambas direcciones.
Circular Linked List: El último nodo apunta de nuevo al primero, formando un ciclo.

Ejemplos prácticos en la vida real

Cadena de Eventos en una App de Tareas
- Imagina una aplicación de lista de tareas pendientes, donde puedes agregar y eliminar tareas de forma dinámica. Una Linked List sería útil porque permite insertar o eliminar tareas fácilmente. Cada tarea (nodo) tiene un nombre (el valor) y un enlace (puntero) que te lleva a la siguiente tarea.
Historial de Navegación en un Navegador
- Cuando navegas en Internet, los sitios que visitas podrían ser almacenados en una Doubly Linked List. Esto permite ir hacia adelante y atrás (punteros hacia el siguiente y el anterior sitio) en el historial de forma eficiente, sin recargar todos los sitios desde el principio.
Gestión de Procesos en un Sistema Operativo
- En los sistemas operativos, los procesos (programas en ejecución) a menudo se gestionan usando Linked Lists. Cada proceso es un nodo que contiene información sobre el proceso (valor) y una referencia al siguiente proceso (puntero).
Trenes con Vagones
- Un tren es como una Linked List. Cada vagón es un nodo que contiene pasajeros (valor) y está conectado al siguiente vagón (puntero). Si necesitas agregar o quitar vagones (nodos) en medio del tren, puedes hacerlo fácilmente sin tener que mover todo el tren.
Música en una Playlist
- En una app de música, cuando tienes una playlist, podrías implementar esto con una Linked List. Cada canción sería un nodo, y el puntero te llevaría a la siguiente canción en la lista. Si decides cambiar el orden o eliminar una canción, lo puedes hacer sin reorganizar toda la playlist.

Stelin Larios

Las singly linked list para entenderse mejor pueden verse como una escalera entre pisos. Cada piso representa un nodo Si quiero ir al ultimo piso debo pasar antes por todos los pisos previos

Mas información

Tomas Di Mauro

Resumen Linked lists: (img 1)Conjunto de nodos ordenados que poseen una refencia al nodo siguiente Singly Linked List: (img 2) Tipo de linked list hacen referencia al valor actual y al nodo siguiente, si se quiere llegar a un nodo en específico, se deben recorrer todos los nodos anteriores

Juan Camilo Lentino Villalba

según Wikipedia:

el principal beneficio de las listas enlazadas respecto a los vectores convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.

fuente https://es.wikipedia.org/wiki/Lista_enlazada

Woldev S.A.S

Un hash table, básicamente, es esto:

Woldev S.A.S

Ingresamos una llave a una caja negra o candado (hasher function), si es la llave indicada, pasará el filtro y accederá al "value" que puede ser un cofre con lo que buscábamos o una puerta para continuar nuestro camino. Ahora, en vez de una sola cerradura, sería una hilera de cerraduras (siendo cada cerradura un bucket y la hilera la totalidad de nuestro hash map o hash table).

Julian Parra

La clave para los linked list es No perder la cabeza

Ruben Vigil

Es una estructura lineal que almacena una colección de elementos generalmente llamados nodos, donde cada nodo puede almacenar datos y enlaces a otros nodos. De esta manera los nodos pueden localizarse en cualquier parte de la memoria, utilizando la referencia que lo relaciona con otro nodo dentro de la estructura.

Se requiere un espacio de memoria adicional para un puntero por cada elemento de la lista. Al primer nodo se le llama "++head++" o cabeza, El ultimo nodo se llama "++tail++" o cola. El tamaño de la lista enlazada no necesita ser especificada en el momento de su inicialización. Permite una reestructuración en el tiempo de ejecución, a diferencia de los arreglos. No se necesita que los elementos sean almacenadas de manera contigua en la memoria ya que los punteros se utilizan para enlazar los datos entre sí.

Métodos: • Prepend: Agregar un nodo al inicio • Append: Agregar un nodo al final • Lookup/search: Buscar un nodo • Insert: Insertar un nodo en la lista • Delete: Borrar un nodo

Caracteristicas: • Acceso: El acceso aleatorio no esta permitido. Los elementos deben de ser accesados secuencialmente y empezando desde el primer nodo.

• Insercion: Podria ser implementado eficientemente si el elemento se inserta en la cabeza (primer nodo) porque no habria un reenlace de nodos a ejecutarse, ya que el primer nodo no tiene ningun nodo predecesor. Insertar un nodo en el medio de la lista requiere que el nodo predecesor se enlace al nuevo nodo agregado. Insertar un nodo al final (en la cola) requiere que el nodo predecesor apunte al nuevo nodo que está al final de la lista.

• Eliminación: Podría implementarse de manera eficiente si el elemento se elimina desde la cabeza (primer nodo) porque no habría que reenlazar los nodos. Eliminar un nodo del medio o del final, requiere que se vuelvan a enlazar los nodos para actualizar las referencias de los nodos contiguos.

Busqueda: Las listas enlazadas se deben revisar secuencialmente, hasta que un match aparezca.

Edgar David Jiménez Jijón

No hay una clase de listas pero de java?

Omar Daniel Centeno