Domina la construcción de una doubly linked list: una estructura con recorrido bidireccional que usa punteros next y preview para moverse de la head a la tail y viceversa. Verás cómo su nodo incluye tres campos y cómo adaptar el método append para enlazar en dos direcciones con una sola línea clave.
¿Qué es una doubly linked list y por qué usarla?
Una doubly linked list es una linked list con enlaces hacia adelante y hacia atrás. A diferencia de una singly, no necesitas “volver a empezar” desde la cabeza para regresar; puedes ir de la tail a la head directamente. Esto puede hacer ciertas búsquedas y recorridos más ágiles en casos particulares.
¿Qué ventajas ofrece frente a una singly linked list?
Recorrido en dos direcciones: head → tail y tail → head.
Evita rehacer bucles desde el inicio al retroceder.
Misma regla de acceso: no hay índice aleatorio, se recorre nodo a nodo.
¿Cómo se recorre sin volver al inicio?
Avanza con next hasta la tail.
Retrocede con preview hasta la head.
Mantiene la lógica de lista enlazada: pasos secuenciales, sin acceso por índice directo.
¿Cómo se define la estructura: nodo, instancia y memoria?
El corazón de la lista es el nodo. Aquí cambia respecto a una singly: además de value y next, se agrega un puntero preview (al previo), que inicia en null.
¿Qué contiene el nodo de una doubly linked list?
value: el dato que guarda el nodo.
next: referencia al siguiente nodo.
preview: referencia al nodo anterior; inicia en null.
¿Cómo se inicializa la primera instancia de la clase?
Crear el primer nodo con value y next = null.
Definir preview = null en ese primer nodo.
Asignar head = tail = primerNodo.
Iniciar length = 1 porque ya existe un elemento.
Representación mental en memoria:
Los nodos forman una cadena con dos direcciones.
Puedes “saltar” hacia atrás gracias a preview sin reiniciar desde la head.
¿Cómo programar append y qué reto sigue?
El método append añade un nodo al final y ahora debe enlazar en ambos sentidos. El ajuste clave es establecer el preview del nuevo nodo apuntando a la tail actual, luego encadenar el next y actualizar la tail.
¿Cómo cambia el método append?
Crear el nuevo nodo.
Apuntar su preview a la tail actual.
Conectar la tail actual hacia adelante con next.
Mover tail al nuevo nodo e incrementar length.
Fragmento esencial del enlace doble:
append(value){const newNode =newNode(value); newNode.preview=this.tail;// enlace hacia atrásthis.tail.next= newNode;// enlace hacia adelantethis.tail= newNode;// actualizar colathis.length++;returnthis;}
Resultados esperados tras varios append:
La head conserva preview = null.
La tail conserva next = null.
Los nodos intermedios tienen next y preview correctamente enlazados.
¿Qué métodos debes extender después?
Implementa la misma lógica de doble enlace en insert.
Ajusta referencias en remove para ambos lados.
Revisa métodos previos de la singly y añade preview donde corresponda.
Sigue la recomendación: antes de codear, toma papel y lápiz para planear los enlaces. ¿Ya adaptaste tus métodos con el nuevo puntero? Comparte tu solución y cuéntanos cómo lo resolviste.
Una doubly linked list tiene el mismo comportamiento que una simply linked list, pero con la particularidad de que esta SI puede regresar. Aún necesita ir moviéndose una por una, pero ahora si lo desea puede regresar porque ya conoce quién es su elemento anterior y también quién es el siguiente, es decir, ya no es necesario repetir el ciclo.
Gracias!
Muy buena manera gráfica de representarlo
Que emocionante recordar todos estos conceptos de la universidad :)
total es una materia complete que en mi caso se llamava estructuras de datos todo un semnestre luchando con c++ y java en mi caso
En mi universidad no nos enseñaron estructuras de datos :S
Doubly Linked List
Además de tener una referencia al nodo siguiente, también se tiene una referencia al nodo anterior.
↔️ Doubly Linked List
Ideas/conceptos claves
una lista doblemente enlazada es una estructura de datos que consiste en un conjunto de nodos enlazados secuencialmente. Cada nodo contiene tres campos, dos para los llamados enlaces, que son referencias al nodo siguiente y al anterior en la secuencia de nodos, y otro más para el almacenamiento de la información
Apuntes
La singly solo tiene un solo canal
La doubly se caracteriza por tener dos direcciones
Tiene tres valores, los que ya conocemos
Value
Next
El que caracteriza es el valor previo
Prev
Esto nos ayuda si es que deseamos buscar un valor en particular nos evita volver a recorrer la estructura
Es decir que para buscar cosas es más rápido
La forma en la que se guarda en memoria los objetos es similar a singly pero con dos direcciones
De un slot a otro, pero ahora puedo volver mediante el pointer prev
RESUMEN: Las doubly linked list son aquellas que tienen dos canales de punteros el anterior [prev] y el proximo [next]
Cómo se aplicaría esta estructura en un caso real?
El ejemplo del navegador es uno bueno, allí es probable que se implemente una double linked list:
Tenemos un usuario que puede ver páginas anteriores o páginas siguientes una por una.
La funcionalidad de volver atrás volver adelante también es un caso donde puede aplizar Ctrl + Z Ctrl + Shift Z, tenemos navegación en dos direcciones, que va nodo por nodo.
La posición de un ascensor en un conjunto de pisos también se podría modelar a través de una doubly linked list dado que va subiendo piso por piso y bajando piso por piso sin poder saltarse pasos, está atado a una sola posición.
Si seguimos analizando pudieramos encontrar otros casos probablemente.
Les comparto mi versión del método getNode.. Este se asegura de que el índice dado no se desborde. Además recorre la lista desde la cabeza o la cola dependiendo de si el nodo está mas cerca de la una o de la otra.
getNode(index){const middlePoint =Math.floor(this.length/2);if(index >this.length-1){//Makes sure the index don't overflow.returnnull;}elseif(index < middlePoint){//Checks whether the index given is closer to the head or the tail.let currentNode =this.head;let counter =0;while(counter != index){//Runs until it gets to the index given. currentNode = currentNode.next; counter++;}return currentNode;}elseif(index > middlePoint){let currentNode =this.tail; counter =this.length-1;//Last indexwhile(counter != index){ currentNode = currentNode.previous; counter--;}return currentNode;}}
¿Alguien cuando hizo ésta DobleList, también notaron que se hacía un Loop infinito? o ¿Fue impresión mía? 😋
Hola! Podrias pasar tu codigo si es posible? asi podremos ayudarte. PD: Los loops infinitos pueden suceder si no creamos correctamente la condicion de corte, y en muchos casos, la condicion de corte, falla porque quizas nos equivocamos a la hora plantearle al ordenador lo que estamos buscando.
Si te refieres a que si estamos a la hora de abir el objeto que hace referencia en la linked list con los previews podemos hacerlo de forma infinita, si jajaja, eso si es posible, ya que la linked list no tiene prinicio ni fin.
Easy.
Whole code of my solution:
/**
* Métodos de las linked list
* -- 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
*
* Tipos
* -Single linked list: linked list compuesto por el head, cuerpo y un tail,
* y el recorrido es en una sola dirección
* -Double linked list: linked list compuesto por el head, cuerpo, tail, y
* el recorrido en dos direcciones
*/functionprintNodes(nodes){let current = nodes.head;const array =[];while(current){ array.push(current.value); current = current.next;}console.log(array);console.log('\n')}classNode{constructor(value){this.value= value;this.next=null;this.prev=null;}}classDoublyLinkedList{constructor(value){this.head={ value,next:null,prev:null}this.tail=this.head;this.length=1;}append(value){const newNode =newNode(value); newNode.prev=this.tail;this.tail.next= newNode;this.tail= newNode;this.length++;returnthis;}prepend(value){const newNode =newNode(value);this.head.prev= newNode; newNode.next=this.head;this.head= newNode;this.length++;returnthis;}insert(index, value){const newNode =newNode(value);if(index >=this.length){returnthis.append(value);}if(index ===0){returnthis.prepend(value);}const targetIndex =this.getIndexNeighbors(index); newNode.prev= targetIndex.before; targetIndex.after.prev= newNode; targetIndex.before.next= newNode; newNode.next= targetIndex.after;this.length++;}remove(index){if(index >=this.length){thrownewError("Index out of bounds")}const targetIndex =this.getIndexNeighbors(index);if(index ===this.length-1){this.tail= targetIndex.before;this.tail.next=null;this.length--;returnthis;}if(index ===0){this.head=this.head.next;this.head.prev=null;this.length--;returnthis;} targetIndex.after.prev= targetIndex.before; targetIndex.before.next= targetIndex.after;this.length--;returnthis;}getIndexNeighbors(index){let i =0;let before =this.head;let after;while( i < index -1){ before = before.next; i++;} after = before.next.next;return{ after, before
}}}let myLinkedList =newDoublyLinkedList(3); myLinkedList.prepend(2); myLinkedList.prepend(1);printNodes(myLinkedList); myLinkedList.insert(3,4); myLinkedList.append(5); myLinkedList.append(6); myLinkedList.append(7);printNodes(myLinkedList); myLinkedList.append(8); myLinkedList.append(9);printNodes(myLinkedList); myLinkedList.remove(7);printNodes(myLinkedList); myLinkedList.remove(6);printNodes(myLinkedList); myLinkedList.remove(5);printNodes(myLinkedList);
Estaba usando algo similar al recibir el nodo per getIndexNeighbors es definitivamente gran idea.
MY NOTES FOR DUBLY LINKED LIST
classNode{constructor(value){this.value= value;this.next=null;//agregamos el tercer valor que traen los double linked listthis.prev=null;}}classMyDoublyLinkedList{constructor(value){this.head={value: value,next:null,//Agregamos tambien en el constructor prev para poder utilizar este dato//Cuando se instancie la claseprev:null,}this.tail=this.head;this.length=1;}append(value){const newNode =newNode(value);//le asignamos al prev el nodo que esta en la cola newNode.prev=this.tail;this.tail.next= newNode;this.tail= newNode;this.length++;returnthis;}prepend(){const newNode =newNode(value); newNode.next=this.head;this.head= newNode;this.length++;returnthis;}insert(index, value){if(index >=this.length){returnthis.append(value);}const newNode =newMySinglyLinkedList(1);const firstPointer =this.getTheIndex(index -1);const holdingPointer = firstPointer.next; firstPointer.next= newNode; newNode.next= holdingPointer;this.length++;returnthis;}getTheIndex(){let counter =0;let currentNode =this.head;while(counter !== index){ currentNode = currentNode.next; counter++;}return currentNode;}}//instanciamos de nuevo nuestras claseslet myDoublyLinkedList =newMyDoublyLinkedList(1);```
Compañeros a modo de aporte adicional , recordar que tambien existen las listas circulares , lo que cambia es que la cola de la lista apunta a la cabeza , de esta forma no es necesario devolverse por toda la lista , si deseamos ir a la cabeza de esta , en la listas circulares podemos usar listas simples , o doblemente enlazada dependiendo del caso.
//Agrega nodo al inicio de la listaprepend(value){const firstNode =newNode(value);this.head.prev= firstNode; firstNode.next=this.head;this.head= firstNode;this.length++;returnthis;}
Este es el metodo insert ajustado
// Agrega un nodo en cualquier parte de la listainsert(value, index){if(index >=this.length){returnthis.append(value);}if(index <=0){returnthis.prepend(value);}const node =newNode(value);const firstPointer =this.getTheIndex(index -1);const holdingPointer = firstPointer.next; firstPointer.next= node; node.next= holdingPointer; node.prev= firstPointer; holdingPointer.prev= node
this.length++;returnthis;}
El codigo del reto del video, adicionalmente agregue la funcionalidad de realizar la busqueda de un node de forma bidireccional head -> tail o tail -> head , de esta manera puedo obtener un node por su indice en cualquiera de las dos direcciones:
