Doubly Linked List con punteros bidireccionales

Clase 19 de 29 • Curso de Estructuras de Datos con JavaScript

Contenido del curso

Introducción a las estructuras de datos

Arrays y strings

Hash Table

Linked List

Stacks

Queues

Trees

24
Estructuras de Datos: Árboles Binarios y Búsqueda en JavaScript
06:15 min
25
Construcción y validación de un Árbol de Búsqueda Binaria en JavaScript
19:36 min

Graphs

Cierre

29
Estructuras de Datos con JavaScript: Práctica y Aplicación
03:14 min

Tomar examen

Resumen

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.

Ejemplo mínimo del nodo:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.preview = null; // previo
  }
}

¿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 = new Node(value);
  newNode.preview = this.tail;      // enlace hacia atrás
  this.tail.next = newNode;         // enlace hacia adelante
  this.tail = newNode;              // actualizar cola
  this.length++;
  return this;
}

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.

Comentarios

Carlos Eduardo Gomez García

teacher•

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.

Rodrigo Rodriguez

student•

Gracias!

Efraín Hernández García

student•

Muy buena manera gráfica de representarlo

Cesar Zegarra

student•

Que emocionante recordar todos estos conceptos de la universidad :)

class Node {
    constructor (value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class MyDoublyLinkedList {
    constructor(value) {
        this.head = new Node(value);
        this.tail = this.head;
        this.length = 1;
    }

    append(value) {
        const newNode = new Node(value);
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
        this.length++;
        return this;
    }

    prepend(value) {
        const newNode = new Node(value);
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        return this;
    }
    insert(index, value) {
        if (index >= this.length) {
            return this.append(value);
        } else if (index === 0) {
            return this.prepend(value);
        }

        let newNode = new Node(value);
        let prevPointer = this.getTheIndex(index - 1);
        let nextPointer = prevPointer.next;
        newNode.prev = prevPointer;
        newNode.next = nextPointer;
        prevPointer.next = newNode;
        nextPointer.prev = newNode;
        this.length++;
        return this;
    }

    remove(index) {
        if (index >= this.length) {
            console.log("index fuera de rango");
            return;
        }
        let indexToRemove = this.getTheIndex(index);
        let nextPointer = indexToRemove.next;
        let prevPointer = indexToRemove.prev;
        if (prevPointer && nextPointer) {
            prevPointer.next = nextPointer;
            nextPointer.prev = prevPointer;
        } else if (!prevPointer) {
            nextPointer.prev = null;
            this.head = nextPointer;
        } else if (!nextPointer) {
            prevPointer.next = null;
            this.tail = prevPointer;
        }
        this.length--;
        return this;
    }

    getTheIndex(index) {
        let counter = 0;
        let currentNode = this.head;
        while (counter !== index) {
            currentNode = currentNode.next;
            counter++;
        }
        return currentNode;
    }
}

Carlos Arturo Rueda Calier

student•

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

Jose Pablo Monge Fierro

student•

En mi universidad no nos enseñaron estructuras de datos :S

Jimmy Buriticá Londoño

student•

Doubly Linked List Además de tener una referencia al nodo siguiente, también se tiene una referencia al nodo anterior.

Fernando Quinteros Gutierrez

student•

↔️ 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]

Victor Gomez

student•

Implementación de los otros métodos:

class DoubleLinkedList {
  constructor(value){
    this.head = {
      value:value,
      next:null,
      prev:null
    }
    this.tail = this.head;

    this.length = 1;
  }
  
  prepend(value){
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head.prev = newNode;
    this.head = newNode;
    this.length++;
  }

  append(value){
    const newNode = new Node(value);
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;

    return this;
  }

  insert(index, value) {
    if(index >= this.length) {
      return this.append(value);
    }
    const newNode = new Node(value);
    const firstPointer = this.getTheIndex(index - 1);
    newNode.prev = firstPointer;
    const holdingPointer = firstPointer.next;
    holdingPointer.prev = newNode;
    firstPointer.next = newNode;
    newNode.next = holdingPointer;

    this.length++;

    return this;
 }

 getTheIndex(index) {
   let counter = 0;
   let currentNode = this.head;
   while(counter !== index){
     currentNode = currentNode.next;
     counter++;
   }

   return currentNode;
 }

 remove(index){
  if(index >= this.length) {
    console.error("index is out of limits of the array");
  } else if( index == 0) {
    this.head = this.head.next;
    this.head.prev = null;
    this.length--
  }
  
  else if(index  === this.length - 1){
    const firstPointer = this.getTheIndex(index - 1);
    firstPointer.next = null;
    
    this.tail = firstPointer;
    this.length--;
  } else {
    const firstPointer = this.getTheIndex(index - 1);
    const pointerToRemove = firstPointer.next;
    const nextToPointerToRemove = pointerToRemove.next;
    nextToPointerToRemove.prev = firstPointer;
    firstPointer.next = nextToPointerToRemove;
    this.length--;
  }
 }
}```

Erick Fernando Guzmán Valerio

student•

Cómo se aplicaría esta estructura en un caso real?

Daniel Páez

student•

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.

Santiago Hoyos

student•

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.
        return null;
    }
    else if (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;
    }else if(index > middlePoint){
        let currentNode = this.tail;
        counter = this.length - 1; //Last index
        while(counter != index){
            currentNode = currentNode.previous;
            counter--;
        }
        return currentNode;
    }
}

Daniel Páez

student•

Divide y vencerás !

Omar Flores Grimontt

student•

Les comparto mis notas sobre el módulo acá 😁

Jose Anibal Garcia Giraldo

student•

Les comparto mi código al reto de la clase :D

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor(value) {
    this.head = {
      value: value,
      prev: null,
      next: null,
    };
    this.tail = this.head;
    this.length = 1;
  }

  append(value) {
    const newNode = new Node(value);
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;

    this.length++;

    return this;
  }

  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head.prev = newNode;
    this.head = newNode;

    this.length++;

    return this;
  }

  searchNode(index) {
    let counter = 0;
    let currentNode = this.head;

    while (counter !== index) {
      currentNode = currentNode.next;
      counter++;
    }

    return currentNode;
  }

  insertByIndex(index, value) {
    if (index >= this.length) {
      return this.append(value);
    }
    if (index === 0) {
      return this.prepend(value);
    }

    const holeToInsert = this.searchNode(index);
    const newNode = new Node(value);
    newNode.next = holeToInsert.next;
    newNode.prev = holeToInsert;
    holeToInsert.next = newNode;

    return this;
  }

  deleteFirst() {
    const nodeToDelete = this.head;
    this.head = this.head.next;
    this.head.prev = null;

    this.length--;
    return nodeToDelete;
  }

  deleteLast() {
    const nodeToDelete = this.tail;
    this.tail = this.tail.prev;
    this.tail.next = null;

    this.length--;

    return nodeToDelete;
  }

  deleteByIndex(index) {
    if (index >= this.length - 1) {
      return this.deleteLast();
    }
    if (index === 0) {
      return this.deleteFirst();
    }

    const nodeToDelete = this.searchNode(index);
    const previousNode = nodeToDelete.prev;
    const laterNode = nodeToDelete.next;
    laterNode.prev = previousNode;
    previousNode.next = laterNode;

    this.length--;

    return nodeToDelete;
  }
}

Diego Alejandro Páez Porras

student•

¿Alguien cuando hizo ésta DobleList, también notaron que se hacía un Loop infinito? o ¿Fue impresión mía? 😋

Ariel Ezequiel Biazzo Genua

student•

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.

Ernán Alexander Velásquez Ramírez

student•

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
  */

 function printNodes(nodes) {
   let current = nodes.head;
   const array = [];
   while (current) {
    array.push(current.value);
    current = current.next;
   }
   console.log(array);
   console.log('\n')
 }

 class Node {
   constructor(value){
     this.value = value;
     this.next = null;
     this.prev = null;
   }
 }

 class DoublyLinkedList {
   constructor(value){
    this.head = {
      value,
      next: null,
      prev: null
    }
    this.tail = this.head;
    this.length = 1;
   }
   append(value){
    const newNode = new Node(value);
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    
    return this;
   }

   prepend(value){
     const newNode = new Node(value);
     this.head.prev = newNode;
     newNode.next = this.head;
     this.head = newNode;
     this.length++;

     return this;
   }

   insert(index, value) {
     const newNode = new Node(value);
     if (index >= this.length) {
      return this.append(value);
     }
     if (index === 0) {
       return this.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) {
      throw new Error("Index out of bounds")
     } 
    const targetIndex = this.getIndexNeighbors(index);
     if (index === this.length - 1) {
      this.tail = targetIndex.before;
      this.tail.next = null;
      this.length--;
      return this;
     }
     if (index === 0) {
       this.head = this.head.next;
       this.head.prev = null;
       this.length--;
       return this;
     }
     targetIndex.after.prev = targetIndex.before;
     targetIndex.before.next = targetIndex.after;
     this.length--;
     return this;
   }

   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 = new DoublyLinkedList(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);

Luis Bastidas

student•

Estaba usando algo similar al recibir el nodo per getIndexNeighbors es definitivamente gran idea.

Guido Modarelli

student•

Andres Felipe Pinchao Ramirez

student•

MY NOTES FOR DUBLY LINKED LIST

class Node{

  constructor(value){

    this.value = value;
    this.next  = null;
    //agregamos el tercer valor que traen los double linked list
    this.prev = null;
  }
}

class MyDoublyLinkedList{

  constructor(value){

    this.head = {
      value: value,
      next: null,
      //Agregamos tambien en el constructor prev para poder utilizar este dato
        //Cuando se instancie la clase
      prev: null,


    }
    this.tail = this.head;

    this.length = 1;
  }
  append(value){
  
    const newNode = new Node(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++;

    return this;



  }

  prepend(){

    const newNode = new Node(value);

    newNode.next = this.head;

    this.head = newNode;

    this.length++;

    return this;





  }


  insert(index, value){

      if(index >= this.length){

        return this.append(value);

      }

      const newNode = new MySinglyLinkedList(1);
      const firstPointer = this.getTheIndex(index - 1);

      const holdingPointer = firstPointer.next;

      firstPointer.next =  newNode;

      newNode.next = holdingPointer;

      this.length++;

      return this;
  }

  getTheIndex(){

    let counter = 0;
    let currentNode = this.head;

    while(counter !== index){

      currentNode = currentNode.next;
      counter++;

    }
    return currentNode;

  }

}

//instanciamos de nuevo nuestras clases

let myDoublyLinkedList = new MyDoublyLinkedList(1);```

Diego Andres Cabrera Rojas

student•

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.

Aura Melia Berdugo Naranjo

student•

Mi aporte!!

class  Node {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.prev = null;
        
    }
}

class MyDoublyLinkedList {
    constructor(value){
        this.head = {
            value: value,
            next: null,
            prev: null,
        };
        this.tail = this.head;
        this.length = 1;
    }

append (value){
    const newNode = new Node (value);
    newNode.prev = this.tail;
    this.tail.next = newNode; 
    this.tail = newNode;
    this.length++;
    return this;
    }

    prepend (value){
        if (this.length === 1){
        const newNode = new Node (value);
        newNode.prev = this.tail;
        this.tail.next = newNode; 
        this.tail = newNode;

        this.length++;        
        return this;
    }
        const newNode = new Node (value);
        newNode.prev =  null;
        newNode.next = this.head;
        this.head = newNode;

        this.length++;        
        return this;
    }

        insert (index, value){
            if(index >= this.length){
                return this.append(value);
            }

            const newNode = new Node (value);
            const firstPointer = this.getTheIndex(index - 1);
            const holdingPointer = firstPointer.next;  
            firstPointer.next = newNode;
            newNode.next = holdingPointer;
            newNode.prev = firstPointer;
            this.length++;
            return this;
        } 
        //counter
        getTheIndex(index){
            let counter = 0;
            let currentNode = this.head; 
            
            while (counter !== index){
                currentNode = currentNode.next;
                counter++;
            }
            return currentNode;
        }
        remove (index){
            if(index >= this.length){
                return 'this nodo does not exist';
            }
            else if (index === 0){
                const deleteNode = this.getTheIndex(index);
                deleteNode.prev = this.tail;

                this.tail = deleteNode;
                const afterDelete = this.getTheIndex(index + 1);     
                this.head = afterDelete;
                this.tail.next = null; 
                afterDelete.prev = null;

                return this;
            }
            else{
                const deleteNode = this.getTheIndex(index);
                deleteNode.prev = this.tail;
                this.tail = deleteNode;
                
                const afterDelete = this.getTheIndex(index + 1);     
                const beforeDelete = this.getTheIndex(index - 1);        
                beforeDelete.next=afterDelete;

                this.tail.next = null; 
                afterDelete.prev = beforeDelete;
                
            return this;
            } 
    }
    } 
    let myDoublyLinkedList = new MyDoublyLinkedList(1);

Juan Sebastián Agudelo

student•

Este es el metodo pretend ajustado

//Agrega nodo al inicio de la lista
prepend (value) {
    const firstNode = new Node(value);
    this.head.prev = firstNode;
    firstNode.next = this.head;
    this.head = firstNode;
    this.length++;
    return this;
}

Este es el metodo insert ajustado


// Agrega un nodo en cualquier parte de la lista
insert (value, index) {
    if (index >= this.length) {
        return this.append(value);
    }
    if (index <= 0) {
        return this.prepend(value);
    }
    const node = new Node(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++;
    return this;
}

Sebastián Saldarriaga Ramirez

student•

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:

class Node {
  constructor(value) {
    this.prev = null;
    this.value = value;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor(value) {
    this.head = {
      prev: null,
      value,
      next: null,
    };
    this.tail = this.head;
    this.length = 1;
  }
  
  append(value) {
    const node = new Node(value);

    node.prev = this.tail;
    this.tail.next = node;
    this.tail = node;
    this.length++;
    return this;
  }

  prepend(value) {
    const node = new Node(value);
    
    this.head.prev = node;
    node.next = this.head;
    this.head = node;
    this.length++;
    return this;
  }

  get(index, reverse = false) {
    let currentNode = reverse ? this.tail : this.head;
    const pointer = reverse ? 'prev' : 'next';

    for (let i = 1; i <= index; i++) {
      if (currentNode[pointer]) {
        currentNode = currentNode[pointer];
      } else {
       throw Error(`list index ${index} out of range error while iteratively popping elements`);
      }
    }

    return currentNode;
  }

  insert(index, value) {
    if (index === 0) return this.prepend(value);
    if (index >= this.length) return this.append(value);

    const node = this.get(index - 1)
    const newNode = new Node(value);

    newNode.prev = node;
    newNode.next = node.next;
    node.next.prev = newNode;
    node.next = newNode;

    this.length++;
    return this;
  }

  deleteHead() {
    this.length--;
    this.head = this.head.next;
    this.head.prev = null;
    return this;
  }

  delete(index) {
    if (index === 0) return this.deleteHead();

    const prevNode = this.get(index - 1)
    const nodeToDelete = prevNode.next;
    prevNode.next = nodeToDelete.next;
    nodeToDelete.next.prev = prevNode;
    
    if (this.length -1 ===index) {
      prevNode.next = null;
      this.tail = prevNode;
    }
    this.length--;
    return this;
  }
}

Joseph Manuel Salen Pantoja

student•

Así quedó mi actividad :D

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.previous = null;
  }
}

class DoubleLinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next: null,
      previous: null,
    };
    this.tail = this.head;
    this.length = 1;
  }

  append(value) {
    const newNode = new Node(value);

    newNode.previous = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;

    return this;
  }

  prepend(value) {
    const newNode = new Node(value);

    newNode.next = this.head;
    this.head.previous = newNode;
    this.head = newNode;
    this.length++;

    return this;
  }

  insert(index, value) {
    if (index >= this.length) {
      return this.append(value);
    } else if (index <= 0) {
      return this.prepend(value);
    }

    const newNode = new Node(value);
    const firstPointer = this.getIndex(index - 1);
    const holdingPointer = firstPointer.next;

    firstPointer.next = newNode;
    newNode.next = holdingPointer;
    newNode.previous = firstPointer;
    this.length++;
  }

  remove(index) {
    if (index >= this.length || index < 0) {
      return "Index error";
    } else if (index === 0) {
      const nextNode = this.getIndex(index + 1);

      nextNode.previous = null;
      this.head = nextNode;
      this.length--;

      return this;
    } else if (index === this.length - 1) {
      const previousPointer = this.getIndex(index - 1);

      previousPointer.next = null;
      this.tail = previousPointer;
      this.length--;

      return this;
    } else {
      const previousPointer = this.getIndex(index - 1);
      const nextPointer = this.getIndex(index + 1);

      previousPointer.next = nextPointer;
      nextPointer.previous = previousPointer;
      this.length--;

      return this;
    }
  }

  getIndex(index) {
    let count = 0;
    let currentNode = this.head;

    while (count !== index) {
      currentNode = currentNode.next;
      count++;
    }

    return currentNode;
  }
}

let dll = new DoubleLinkedList(1);
dll.append(2);
dll.append(3);
dll.append(4);

Mi cara cuando volteo a ver mi código que funciona:

Jose Luis Higuera Caraveo

student•

Esta es mi Doubly Linked List

class Node {
  constructor(value) {
    this.value = value,
    this.next = null
    this.prev = null
  }
}

class MyDoublyLinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next : null,
      prev : null
      
    }
    this.tail = this.head

    this.length = 1
  }
  append(value) {
    const node = new Node(value)
    node.prev = this.tail
    this.tail.next = node
    this.tail = node

    this.length ++

    return this
  }
  prepend(value) {
    const node = new Node(value)
    node.next = this.head
    this.head.prev = node
    this.head = node

    this.length ++

    return this
  }
  getIndex(index) {
    let counter = 0
    let currentNode = this.head

    while(counter !== index) {
      currentNode = currentNode.next
      counter ++
    }
    return currentNode
  }
  insert(value, index) {
    const node = new Node(value)
    if (index >= this.length) {
      return this.append(value)
    }
    const firstPointer = this.getIndex(index - 1)
    const holdingPointer = firstPointer.next
    firstPointer.next = node
    node.prev = firstPointer
    node.next = holdingPointer
    holdingPointer.prev = node

    this.length ++

    return this
  }
  remove(index) {
    if (index >= this.length || index < 0) {
      console.log("Incorrect Index")
    }
    if (index === 0) {
      this.head = this.head.next
      this.head.prev = null
    }
    if (index === this.length -1) {
      this.tail = this.tail.prev
      this.tail.next = null
    }
    
    const firstPointer = this.getIndex(index - 1)
    const nextPointer = this.getIndex(index + 1)
    firstPointer.next = nextPointer
    nextPointer.prev = firstPointer
    

    this.length -- 

    return this
  }
}

Johan Sebastian

student•

class Node {
    constructor (value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class MyDoublyLinkedList {
    constructor(value) {
        this.head = new Node(value);
        this.tail = this.head;
        this.length = 1;
    }

    append(value) {
        const newNode = new Node(value);
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
        this.length++;
        return this;
    }

    prepend(value) {
        const newNode = new Node(value);
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        return this;
    }
    insert(index, value) {
        if (index >= this.length) {
            return this.append(value);
        } else if (index === 0) {
            return this.prepend(value);
        }

        let newNode = new Node(value);
        let prevPointer = this.getTheIndex(index - 1);
        let nextPointer = prevPointer.next;
        newNode.prev = prevPointer;
        newNode.next = nextPointer;
        prevPointer.next = newNode;
        nextPointer.prev = newNode;
        this.length++;
        return this;
    }

    remove(index) {
        if (index >= this.length) {
            console.log("index fuera de rango");
            return;
        }
        let indexToRemove = this.getTheIndex(index);
        let nextPointer = indexToRemove.next;
        let prevPointer = indexToRemove.prev;
        if (prevPointer && nextPointer) {
            prevPointer.next = nextPointer;
            nextPointer.prev = prevPointer;
        } else if (!prevPointer) {
            nextPointer.prev = null;
            this.head = nextPointer;
        } else if (!nextPointer) {
            prevPointer.next = null;
            this.tail = prevPointer;
        }
        this.length--;
        return this;
    }

    getTheIndex(index) {
        let counter = 0;
        let currentNode = this.head;
        while (counter !== index) {
            currentNode = currentNode.next;
            counter++;
        }
        return currentNode;
    }
}

class DoubleLinkedList {
  constructor(value){
    this.head = {
      value:value,
      next:null,
      prev:null
    }
    this.tail = this.head;

    this.length = 1;
  }
  
  prepend(value){
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head.prev = newNode;
    this.head = newNode;
    this.length++;
  }

  append(value){
    const newNode = new Node(value);
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;

    return this;
  }

  insert(index, value) {
    if(index >= this.length) {
      return this.append(value);
    }
    const newNode = new Node(value);
    const firstPointer = this.getTheIndex(index - 1);
    newNode.prev = firstPointer;
    const holdingPointer = firstPointer.next;
    holdingPointer.prev = newNode;
    firstPointer.next = newNode;
    newNode.next = holdingPointer;

    this.length++;

    return this;
 }

 getTheIndex(index) {
   let counter = 0;
   let currentNode = this.head;
   while(counter !== index){
     currentNode = currentNode.next;
     counter++;
   }

   return currentNode;
 }

 remove(index){
  if(index >= this.length) {
    console.error("index is out of limits of the array");
  } else if( index == 0) {
    this.head = this.head.next;
    this.head.prev = null;
    this.length--
  }
  
  else if(index  === this.length - 1){
    const firstPointer = this.getTheIndex(index - 1);
    firstPointer.next = null;
    
    this.tail = firstPointer;
    this.length--;
  } else {
    const firstPointer = this.getTheIndex(index - 1);
    const pointerToRemove = firstPointer.next;
    const nextToPointerToRemove = pointerToRemove.next;
    nextToPointerToRemove.prev = firstPointer;
    firstPointer.next = nextToPointerToRemove;
    this.length--;
  }
 }
}```

getNode(index){
    const middlePoint = Math.floor(this.length / 2);

    if(index > this.length - 1){//Makes sure the index don't overflow.
        return null;
    }
    else if (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;
    }else if(index > middlePoint){
        let currentNode = this.tail;
        counter = this.length - 1; //Last index
        while(counter != index){
            currentNode = currentNode.previous;
            counter--;
        }
        return currentNode;
    }
}

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor(value) {
    this.head = {
      value: value,
      prev: null,
      next: null,
    };
    this.tail = this.head;
    this.length = 1;
  }

  append(value) {
    const newNode = new Node(value);
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;

    this.length++;

    return this;
  }

  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head.prev = newNode;
    this.head = newNode;

    this.length++;

    return this;
  }

  searchNode(index) {
    let counter = 0;
    let currentNode = this.head;

    while (counter !== index) {
      currentNode = currentNode.next;
      counter++;
    }

    return currentNode;
  }

  insertByIndex(index, value) {
    if (index >= this.length) {
      return this.append(value);
    }
    if (index === 0) {
      return this.prepend(value);
    }

    const holeToInsert = this.searchNode(index);
    const newNode = new Node(value);
    newNode.next = holeToInsert.next;
    newNode.prev = holeToInsert;
    holeToInsert.next = newNode;

    return this;
  }

  deleteFirst() {
    const nodeToDelete = this.head;
    this.head = this.head.next;
    this.head.prev = null;

    this.length--;
    return nodeToDelete;
  }

  deleteLast() {
    const nodeToDelete = this.tail;
    this.tail = this.tail.prev;
    this.tail.next = null;

    this.length--;

    return nodeToDelete;
  }

  deleteByIndex(index) {
    if (index >= this.length - 1) {
      return this.deleteLast();
    }
    if (index === 0) {
      return this.deleteFirst();
    }

    const nodeToDelete = this.searchNode(index);
    const previousNode = nodeToDelete.prev;
    const laterNode = nodeToDelete.next;
    laterNode.prev = previousNode;
    previousNode.next = laterNode;

    this.length--;

    return nodeToDelete;
  }
}

 /**
  * 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
  */

 function printNodes(nodes) {
   let current = nodes.head;
   const array = [];
   while (current) {
    array.push(current.value);
    current = current.next;
   }
   console.log(array);
   console.log('\n')
 }

 class Node {
   constructor(value){
     this.value = value;
     this.next = null;
     this.prev = null;
   }
 }

 class DoublyLinkedList {
   constructor(value){
    this.head = {
      value,
      next: null,
      prev: null
    }
    this.tail = this.head;
    this.length = 1;
   }
   append(value){
    const newNode = new Node(value);
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    
    return this;
   }

   prepend(value){
     const newNode = new Node(value);
     this.head.prev = newNode;
     newNode.next = this.head;
     this.head = newNode;
     this.length++;

     return this;
   }

   insert(index, value) {
     const newNode = new Node(value);
     if (index >= this.length) {
      return this.append(value);
     }
     if (index === 0) {
       return this.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) {
      throw new Error("Index out of bounds")
     } 
    const targetIndex = this.getIndexNeighbors(index);
     if (index === this.length - 1) {
      this.tail = targetIndex.before;
      this.tail.next = null;
      this.length--;
      return this;
     }
     if (index === 0) {
       this.head = this.head.next;
       this.head.prev = null;
       this.length--;
       return this;
     }
     targetIndex.after.prev = targetIndex.before;
     targetIndex.before.next = targetIndex.after;
     this.length--;
     return this;
   }

   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 = new DoublyLinkedList(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);

class Node{

  constructor(value){

    this.value = value;
    this.next  = null;
    //agregamos el tercer valor que traen los double linked list
    this.prev = null;
  }
}

class MyDoublyLinkedList{

  constructor(value){

    this.head = {
      value: value,
      next: null,
      //Agregamos tambien en el constructor prev para poder utilizar este dato
        //Cuando se instancie la clase
      prev: null,

    }
    this.tail = this.head;

    this.length = 1;
  }
  append(value){
  
    const newNode = new Node(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++;

    return this;

  }

  prepend(){

    const newNode = new Node(value);

    newNode.next = this.head;

    this.head = newNode;

    this.length++;

    return this;

  }

  insert(index, value){

      if(index >= this.length){

        return this.append(value);

      }

      const newNode = new MySinglyLinkedList(1);
      const firstPointer = this.getTheIndex(index - 1);

      const holdingPointer = firstPointer.next;

      firstPointer.next =  newNode;

      newNode.next = holdingPointer;

      this.length++;

      return this;
  }

  getTheIndex(){

    let counter = 0;
    let currentNode = this.head;

    while(counter !== index){

      currentNode = currentNode.next;
      counter++;

    }
    return currentNode;

  }

}

//instanciamos de nuevo nuestras clases

let myDoublyLinkedList = new MyDoublyLinkedList(1);```

class  Node {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.prev = null;
        
    }
}

class MyDoublyLinkedList {
    constructor(value){
        this.head = {
            value: value,
            next: null,
            prev: null,
        };
        this.tail = this.head;
        this.length = 1;
    }

append (value){
    const newNode = new Node (value);
    newNode.prev = this.tail;
    this.tail.next = newNode; 
    this.tail = newNode;
    this.length++;
    return this;
    }

    prepend (value){
        if (this.length === 1){
        const newNode = new Node (value);
        newNode.prev = this.tail;
        this.tail.next = newNode; 
        this.tail = newNode;

        this.length++;        
        return this;
    }
        const newNode = new Node (value);
        newNode.prev =  null;
        newNode.next = this.head;
        this.head = newNode;

        this.length++;        
        return this;
    }

        insert (index, value){
            if(index >= this.length){
                return this.append(value);
            }

            const newNode = new Node (value);
            const firstPointer = this.getTheIndex(index - 1);
            const holdingPointer = firstPointer.next;  
            firstPointer.next = newNode;
            newNode.next = holdingPointer;
            newNode.prev = firstPointer;
            this.length++;
            return this;
        } 
        //counter
        getTheIndex(index){
            let counter = 0;
            let currentNode = this.head; 
            
            while (counter !== index){
                currentNode = currentNode.next;
                counter++;
            }
            return currentNode;
        }
        remove (index){
            if(index >= this.length){
                return 'this nodo does not exist';
            }
            else if (index === 0){
                const deleteNode = this.getTheIndex(index);
                deleteNode.prev = this.tail;

                this.tail = deleteNode;
                const afterDelete = this.getTheIndex(index + 1);     
                this.head = afterDelete;
                this.tail.next = null; 
                afterDelete.prev = null;

                return this;
            }
            else{
                const deleteNode = this.getTheIndex(index);
                deleteNode.prev = this.tail;
                this.tail = deleteNode;
                
                const afterDelete = this.getTheIndex(index + 1);     
                const beforeDelete = this.getTheIndex(index - 1);        
                beforeDelete.next=afterDelete;

                this.tail.next = null; 
                afterDelete.prev = beforeDelete;
                
            return this;
            } 
    }
    } 
    let myDoublyLinkedList = new MyDoublyLinkedList(1);

//Agrega nodo al inicio de la lista
prepend (value) {
    const firstNode = new Node(value);
    this.head.prev = firstNode;
    firstNode.next = this.head;
    this.head = firstNode;
    this.length++;
    return this;
}

// Agrega un nodo en cualquier parte de la lista
insert (value, index) {
    if (index >= this.length) {
        return this.append(value);
    }
    if (index <= 0) {
        return this.prepend(value);
    }
    const node = new Node(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++;
    return this;
}

class Node {
  constructor(value) {
    this.prev = null;
    this.value = value;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor(value) {
    this.head = {
      prev: null,
      value,
      next: null,
    };
    this.tail = this.head;
    this.length = 1;
  }
  
  append(value) {
    const node = new Node(value);

    node.prev = this.tail;
    this.tail.next = node;
    this.tail = node;
    this.length++;
    return this;
  }

  prepend(value) {
    const node = new Node(value);
    
    this.head.prev = node;
    node.next = this.head;
    this.head = node;
    this.length++;
    return this;
  }

  get(index, reverse = false) {
    let currentNode = reverse ? this.tail : this.head;
    const pointer = reverse ? 'prev' : 'next';

    for (let i = 1; i <= index; i++) {
      if (currentNode[pointer]) {
        currentNode = currentNode[pointer];
      } else {
       throw Error(`list index ${index} out of range error while iteratively popping elements`);
      }
    }

    return currentNode;
  }

  insert(index, value) {
    if (index === 0) return this.prepend(value);
    if (index >= this.length) return this.append(value);

    const node = this.get(index - 1)
    const newNode = new Node(value);

    newNode.prev = node;
    newNode.next = node.next;
    node.next.prev = newNode;
    node.next = newNode;

    this.length++;
    return this;
  }

  deleteHead() {
    this.length--;
    this.head = this.head.next;
    this.head.prev = null;
    return this;
  }

  delete(index) {
    if (index === 0) return this.deleteHead();

    const prevNode = this.get(index - 1)
    const nodeToDelete = prevNode.next;
    prevNode.next = nodeToDelete.next;
    nodeToDelete.next.prev = prevNode;
    
    if (this.length -1 ===index) {
      prevNode.next = null;
      this.tail = prevNode;
    }
    this.length--;
    return this;
  }
}

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.previous = null;
  }
}

class DoubleLinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next: null,
      previous: null,
    };
    this.tail = this.head;
    this.length = 1;
  }

  append(value) {
    const newNode = new Node(value);

    newNode.previous = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;

    return this;
  }

  prepend(value) {
    const newNode = new Node(value);

    newNode.next = this.head;
    this.head.previous = newNode;
    this.head = newNode;
    this.length++;

    return this;
  }

  insert(index, value) {
    if (index >= this.length) {
      return this.append(value);
    } else if (index <= 0) {
      return this.prepend(value);
    }

    const newNode = new Node(value);
    const firstPointer = this.getIndex(index - 1);
    const holdingPointer = firstPointer.next;

    firstPointer.next = newNode;
    newNode.next = holdingPointer;
    newNode.previous = firstPointer;
    this.length++;
  }

  remove(index) {
    if (index >= this.length || index < 0) {
      return "Index error";
    } else if (index === 0) {
      const nextNode = this.getIndex(index + 1);

      nextNode.previous = null;
      this.head = nextNode;
      this.length--;

      return this;
    } else if (index === this.length - 1) {
      const previousPointer = this.getIndex(index - 1);

      previousPointer.next = null;
      this.tail = previousPointer;
      this.length--;

      return this;
    } else {
      const previousPointer = this.getIndex(index - 1);
      const nextPointer = this.getIndex(index + 1);

      previousPointer.next = nextPointer;
      nextPointer.previous = previousPointer;
      this.length--;

      return this;
    }
  }

  getIndex(index) {
    let count = 0;
    let currentNode = this.head;

    while (count !== index) {
      currentNode = currentNode.next;
      count++;
    }

    return currentNode;
  }
}

let dll = new DoubleLinkedList(1);
dll.append(2);
dll.append(3);
dll.append(4);

class Node {
  constructor(value) {
    this.value = value,
    this.next = null
    this.prev = null
  }
}

class MyDoublyLinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next : null,
      prev : null
      
    }
    this.tail = this.head

    this.length = 1
  }
  append(value) {
    const node = new Node(value)
    node.prev = this.tail
    this.tail.next = node
    this.tail = node

    this.length ++

    return this
  }
  prepend(value) {
    const node = new Node(value)
    node.next = this.head
    this.head.prev = node
    this.head = node

    this.length ++

    return this
  }
  getIndex(index) {
    let counter = 0
    let currentNode = this.head

    while(counter !== index) {
      currentNode = currentNode.next
      counter ++
    }
    return currentNode
  }
  insert(value, index) {
    const node = new Node(value)
    if (index >= this.length) {
      return this.append(value)
    }
    const firstPointer = this.getIndex(index - 1)
    const holdingPointer = firstPointer.next
    firstPointer.next = node
    node.prev = firstPointer
    node.next = holdingPointer
    holdingPointer.prev = node

    this.length ++

    return this
  }
  remove(index) {
    if (index >= this.length || index < 0) {
      console.log("Incorrect Index")
    }
    if (index === 0) {
      this.head = this.head.next
      this.head.prev = null
    }
    if (index === this.length -1) {
      this.tail = this.tail.prev
      this.tail.next = null
    }
    
    const firstPointer = this.getIndex(index - 1)
    const nextPointer = this.getIndex(index + 1)
    firstPointer.next = nextPointer
    nextPointer.prev = firstPointer
    

    this.length -- 

    return this
  }
}

Doubly Linked List con punteros bidireccionales

Introducción a las estructuras de datos

Estructuras de Datos en JavaScript para Desarrolladores

Estructuras de Datos: Conceptos Básicos y Aplicaciones Prácticas

Almacenamiento de Datos en Memoria con JavaScript

Arrays y strings

Cómo funcionan arrays en memoria de JavaScript

Construcción de Arrays con Clases en JavaScript

Métodos pop y delete en arrays

Playground: crea tu propia implementación de unshift

Playground: crea tu propia implementación de shift

Inmutabilidad de Strings y Almacenamiento en Memoria

Hash Table

Conceptos y Construcción de Hash Tables en JavaScript

Implementación de Hash Table en JavaScript: Método Set

Implementación del método get en hash table JavaScript

Playground: implementa el metodo Delete

Playground: implementa el método getAllKeys

Linked List

Estructuras de Datos: Listas Enlazadas en JavaScript

Estructura y Creación de una Lista Enlazada Simple en JavaScript

Métodos para Manipular Nodos en Listas Enlazadas

Inserta nodos intermedios sin romper enlaces en JavaScript