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.
Introducción a las estructuras de datos
Todo lo que aprenderás sobre estructuras de datos con JavaScript
¿Qué son las estructuras de datos?
Memoria y cómo se guardan los datos
Arrays y strings
Arrays
Construyendo nuestro Array
Eliminando elementos del Array
Strings
Hash Table
Hash Tables
Construyendo una Hash Table
Implementando el método Get
Linked List
Linked List
Construyendo una Singly Linked List
Agregar nodos a la lista
Agregar nodos intermedios
Doubly Linked List
Stacks
Stacks
Construyendo un Stack
Queues
Queues
Construyendo un Queue
Trees
Trees
Construyendo un Binary Search Tree
Graphs
Graphs
Representando grafos en código
Construyendo un grafo
Cierre
Conclusiones
Aún no tienes acceso a esta clase
Crea una cuenta y continúa viendo este curso
Crear cuenta
Si ya tienes una cuenta,
Iniciar sesión
Doubly Linked List
15/25Recursos
Aportes 86
Preguntas 8
Ordenar por:
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;
}
}
Alguien noto que los funko pop cambiaron?
Ahora se que el porfe es otaku.
https://www.youtube.com/watch?v=H2oWviWV9r4&t=63s
Doubly Linked List
Además de tener una referencia al nodo siguiente, también se tiene una referencia al nodo anterior.
↔️ Doubly Linked List
<h4>Ideas/conceptos claves</h4>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
<h4>Apuntes</h4>- 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]
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--;
}
}
}```
Les comparto mi código al reto de la clase 😄
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;
}
}
Les comparto mis notas sobre el módulo acá 😁
Mi codigo, lo hice un poco diferente…
Linked List Example in JS
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);```
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);
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;
}
}
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.
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;
}
}
Así quedó mi actividad 😄
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:
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
}
}
Mi solucion al reto
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;
}
getAll() {
return this;
}
/**
* Add a new node at the end
* @param {*} value
* @returns this
*/
append(value) {
const newNode = new Node(value);
newNode.prev = this.tail;
//Aqui hago la referencia al sig. nodo
this.tail.next = newNode;
//Aqui agrego el valor!!
this.tail = newNode;
this.length++;
return this;
}
/**
* Add the new node at the start
* @param {*} value
* @returns
*/
prepend(value) {
const newNode = new Node(value);
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
this.length++;
return this;
}
/**
* Add a new node in the list
* @param {number} index
* @param {*} value
* @returns {object}
*/
insert(index, value) {
//Hay que asegurar que niguno de los nodos se quede
// sin pointer, que no caiga en el garbage collector
if (index >= this.length) {
return this.append(value);
} else if (index === 0) {
return this.prepend(value);
} else {
const newNode = new Node(value);
const firstPointer = this.getTheIndex(index - 1);
const holdingPointer = firstPointer.next;
newNode.prev = firstPointer;
newNode.next = holdingPointer;
firstPointer.next = newNode;
holdingPointer.prev = newNode;
this.length++;
}
return this;
}
/**
* Remove a node in the list
* @param {number} index - position on the list, from 1
* @returns {null|object} this - List
*
*/
remove(index) {
if (index > this.length) {
return null;
} else if (index === 1) {
this.head = this.head.next;
this.head.prev = null;
} else if (index === this.length) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
const prevDeletedNode = this.getTheIndex(index - 1);
const holdingPointer = prevDeletedNode.next;
const nextDeletedNode = holdingPointer.next;
prevDeletedNode.next = holdingPointer.next;
nextDeletedNode.prev = holdingPointer.prev;
}
this.length--;
return this;
}
/**
* Get the especific node
* @param {number} index
* @returns {object} - currentNode
*/
getTheIndex(index) {
let counter = 0;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
}
let myDoublyLinkedList = new MyDoublyLinkedList(1);
myDoublyLinkedList.append(2);
myDoublyLinkedList.append(4);
myDoublyLinkedList.insert(2, 3);
myDoublyLinkedList.remove(1);
//Es mas facil si lo hago en consola (Chrome)
console.log(myDoublyLinkedList.getAll());
append(value) {
const newNode = new Node(value);
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
preAppend(value) {
const newNode = new Node(value);
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
this.length++;
return this;
}
insert(index, value) {
if (index >= this.length) {
return this.append(value);
}
const newNode = new Node(value);
const leader = this.traverseToIndex(index - 1);
const holdingPointer = leader.next;
leader.next = newNode;
newNode.prev = leader;
newNode.next = holdingPointer;
holdingPointer.prev = newNode;
this.length++;
return this;
}
remove(index) {
if (index >= this.length) {
return undefined;
}
const leader = this.traverseToIndex(index - 1);
const unwantedNode = leader.next;
leader.next = unwantedNode.next;
unwantedNode.next.prev = leader;
this.length--;
return this;
}
Cuando son listas grandes, si el nodo que buscamos está después de la mitad de la lista, resulta más eficiente iniciar la búsqueda desde el final.
Aquí una optimización de la búsqueda usando recursividad:
getByIndex(index) {
const isBeyondHalf = index > (this.length / 2)
const startingIndex = isBeyondHalf ? this.length - 1 : 0
return this.nodeLookUp(index, startingIndex, isBeyondHalf)
}
nodeLookUp(desiredIndex, currentIndex, isBeyondHalf, currentNode = this.head) {
return desiredIndex === currentIndex
? currentNode
: this.nodeLookUp(
desiredIndex,
currentNode.next,
isBeyondHalf
? currentIndex - 1
: currentIndex + 1
)
}
Este es un “Inception” El nodo 3 tiene en su elemento prev a el Nodo 2 que a su vez tienen en su elemento next al Node 3 que a su vez tiene en su elmento pre al nodo 2… Se autoreferencian.
cuando lo hice en la consola no encontré fin a esto. ¿Por qué esto es eficiente para el computador?
insert(value, index){
const newNode = new Node(value);
if(index <= this.length - 1 && index >= 0){
const first = this.get(index- 1);
let tail = first.next;
tail.prev = newNode;
newNode.next = tail;
newNode.prev= first;
first.next = newNode;
this.length++;
return this;
}else{
if(pos <= this.length){
return this.prepend(newNode);
}else{
return this.append(newNode);
}
}
}
Desarrolle un pequeña idea, si me equivoco, por favor, respondan este comentario.
Al pensar en la doublue LINKED LIST, pienso en como uno de sus mayores benefecios es la busqueda de un elemento. Pero, de que manera? Bien, imaginemos que deseamos buscar el numero 6 en esta linked list PAR(contando el null).: [1][3][4][6][8][null]. Imaginemos que tenemos 2 punteros para encontrar ese 6, un puntero ira desde head(1) hasta el 6 de izquiera a derecha, y el otro, desde head(1) hasta 6, pero en sentido contrario, empezando desde el 1, luego a null, y luego a 6. Entonces si contamos los moviemientos, de 1 a 6, con el primer puntero son 3 MOV 1 -> 3, 3->4, 4 -> 6. Y con el 2do puntero(el que pasa por los preview) TAMBIEN son 3 movimientos. 1-> null, null -> 8, 8->6. 3 movimientos. CONCLUSION: Si estamos buscando con una double linked list un elemento en una linked list PAR, y sabemos en que posicion esta este, la unica manera en que la doble linked list nos de un beneficio es que el elemento a busacar se encuentra en ((linkedList.length) / 2 + 2). Es decir, tomamos nuestra linked list par, encontramos su elemento que esta en la mitad(no el elemento buscado), de ahi, vamos 2 lugares mas hacia adelante, desde ese lugarm hasta el final de la lista, podemos usar una funcion de busqueda con oreviw, y nuestro tiempo sera menor a la hora de buscar algo!
🌟🌟 Solución para las Estructuras de Datos Linked List 🌟🌟
Comparto la solución de esta estructuras de datos, por si alguien se atascó o no entiende alguna parte. :DD
.
Traté de resolver la mayoría de errores que sucedían 😛 y comenté las líneas de diferencia entre Singly y Doubly Linked List.
.
¡Nunca pares de aprender! 💚
.
Singly Linked List
Doubly Linked List
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);
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
this.length++;
return this;
}
getTheIndex(index) {
let counter = 0;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
insert(value, index) {
if (index >= this.length) {
return this.append(value);
}
const newNode = new Node(value);
const previousNode = this.getTheIndex(index - 1);
const nextNode = previousNode.next;
newNode.prev = previousNode;
previousNode.next = newNode;
nextNode.prev = newNode;
newNode.next = nextNode;
this.length++;
return this;
}
remove(index) {
if (index === 0) {
this.head = this.head.next;
this.length--;
return this;
}
if (index === this.length - 1) {
const previousNode = this.getTheIndex(index - 1);
previousNode.next == null;
this.tail = previousNode;
this.length--;
return this;
}
if (index >= this.length || index < 0) {
return undefined;
}
const previousNode = this.getTheIndex(index - 1);
const nextNode = this.getTheIndex(index).next;
nextNode.prev = previousNode;
previousNode.next = nextNode;
this.length--;
return this;
}
}
let myLinkedList = new MyDoublyLinkedList(0);
Aca van los retos de la clase!
Saludos!!!
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) {
const newNode = new Node(value);
newNode.next = this.head;
this.head.prev = newNode
this.head = newNode;
this.length++
return this
}
insert(index, value) {
if(index === 0) {
return this.prepend(value)
}
if (index >= this.length) {
console.warn('out of limit index, it will be appended as the last element')
return this.append(value)
}
const newNode = new Node(value);
const firstPointer = this.getTheIndex(index - 1);
const holdingPointer = firstPointer.next;
firstPointer.next = newNode;
newNode.prev = firstPointer;
newNode.next = holdingPointer;
holdingPointer.prev = newNode;
this.length++;
return this;
}
delete(index) {
if (index === 0) {
this.head = this.head.next
this.head.prev = null
this.length--
return this
}
if (index >= this.length) {
console.error('out of limits, insert an existent index')
return this
}
if (index === this.length - 1) {
this.tail = this.tail.prev
this.tail.next = null
this.length--
return this
}
const prevNode = this.getTheIndex(index - 1);
const nextNode = this.getTheIndex(index + 1);
prevNode.next = nextNode;
nextNode.prev = prevNode;
this.length--
return this
}
getTheIndex(index) {
let counter = 0;
let current = this.head;
while (index !== counter) {
current = current.next
counter++
}
return current
}
}
let myDoublyLinkedList = new MyDoublyLinkedList(1)
myDoublyLinkedList.append(2)
myDoublyLinkedList.append(3)
myDoublyLinkedList.append(4)
Listo el reto. Casi que es solo agregar un par de lineas y algunos condicionales a la lógica del “singly”.
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 /** doubly */
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 /** doubly */
this.head = newNode
this.length++
return this
}
searchIndex(index) {
if (index >= this.length) {
return null
}
let currentNode = this.head
for (let i=0; i<=index; i++ ) {
if (i == index) {
return currentNode
}
currentNode = currentNode.next
}
return false
}
insert(index, value) {
if (index == 0) {
return this.prepend(value)
}
if (index >= this.length) {
return this.append(value)
}
const nodePrevious = this.searchIndex(index-1)
const newNode = new Node(value)
newNode.next = nodePrevious.next
newNode.prev = nodePrevious /** doubly */
nodePrevious.next.prev = newNode /** doubly */
nodePrevious.next = newNode
this.length++
return this
}
deleteIndex(index) {
const nodeToDelete = this.searchIndex(index)
if (nodeToDelete) {
if (nodeToDelete === this.head) {
this.head = this.head.next
this.head.prev = null /** doubly */
} else {
const nodePrevious = this.searchIndex(index-1)
if (nodeToDelete === this.tail) {
this.tail = nodePrevious
} else { /** doubly */
nodeToDelete.next.prev = nodeToDelete.prev /** doubly */
} /** doubly */
nodePrevious.next = nodeToDelete.next
}
this.length--
}
return this
}
}
Llamados para las pruebas:
let myDoublyLinkedList = new MyDoublyLinkedList(2)
myDoublyLinkedList.append(3)
myDoublyLinkedList.append(4)
myDoublyLinkedList.append(5)
myDoublyLinkedList.append(6)
myDoublyLinkedList.prepend(0)
myDoublyLinkedList.searchIndex(9)
myDoublyLinkedList.searchIndex(5)
myDoublyLinkedList.insert(9, 7)
myDoublyLinkedList.insert(1,1)
myDoublyLinkedList.insert(0, -1)
myDoublyLinkedList.deleteIndex(1)
myDoublyLinkedList.deleteIndex(0)
myDoublyLinkedList.deleteIndex(6)
El codigo de Bobionwa
class MyDoublyLinkedList {
constructor(value) {
this.head = {
value: value,
next: null,
prev: null,
};
this.tail = this.head;
this.length = 1;
}
append(value) { // Agregar nodo al final
const newNode = new Node(value);
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
prepend(value) { // Agregar nodo al inicio
const newNode = new Node(value);
newNode.next = this.head;
this.head.prev = newNode;
newNode.prev = null;
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;
holdingPointer.prev = newNode;
this.length++;
return this;
}
remove(index){
if(index <= this.length){
return null;
}
if(index == 0){
this.head = this.head.next;
this.prev = null;
this.lenght--;
}
if(index >= this.length){
prevPointer = this.getTheIndex[-1];
firstPointer.next = null;
this.head.prev = null;
this.tall = prevPointer;
this.lenght--;
} else{
const prevPointer = this.getTheIndex[-1];
const nextPointer = prevPointer.next
prevPointer.next = newNode;
newNode.prev = firstPointer;
newNode.next = nextPointer;
nextPointer.prev = newNode;
}
}
getTheIndex(index) {
let counter = 0;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
}
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
let myDoublyLinkedList = new MyDoublyLinkedList(1);
Listo, ya quedó! ;D
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;
}
push(value) {
const node = new Node(value);
this.tail.next = node
node.prev = this.tail
this.tail = this.tail.next
this.length++
return this;
}
prepend(value) {
const add = new Node(value);
add.next = this.head
this.head = add;
this.length++
return this
}
get(position) {
let getter = this.head
if (getter <= 1) {
return getter
} else {
// 1 < 3
for(let i = 1; i < position; i++) {
getter = getter.next
};
return getter;
};
}
insert(value, afterOf) {
if(afterOf < 0 || afterOf > this.length) {
return "Las posiciones de datos van de 0 a length"
} else if (afterOf == 0){
return this.prepend(value);
} else if(afterOf == this.length) {
return this.push(value)
} else {
let insert = new Node(value);
insert.next = this.get(afterOf + 1);
insert.prev = this.get(afterOf);
this.get(afterOf).next = insert
this.length++
}
return this;
}
deletehead() {
const item = this.head
item.next = null
this.head = this.get(2);
this.length--;
return item;
}
deletetail() {
const item = this.tail
item.prev = null
this.get(this.length - 1).next = null;
this.tail = this.get(this.length - 1)
this.length--
return item
}
delete(position) {
if(position < 1 || position > this.length) {
return "Las posiciones existentes de datos van de 1 a length"
} else if (position < 2) {
return this.deletehead();
} else if (position == this.length) {
return this.deletetail();
} else {
const item = this.get(position);
this.get(position - 1).next = this.get(position + 1);
this.get(position + 1).prev = this.get(position - 1);
this.length--
item.next = null;
item.prev = null;
return item
}
}
createACircuit(){
this.head.prev = this.tail;
this.tail.next = this.head;
return this;
}
};
const myLinkedList = new myDoublyLinkedList(1);
myLinkedList.push(2);
myLinkedList.push(5);
myLinkedList.push(4);
myLinkedList.push(5);
myLinkedList.push(3);
myLinkedList.push(8);
myLinkedList.push(1);
myLinkedList.push(30);
myLinkedList.push(132);
myLinkedList.push(22);
myLinkedList.push(4);
myLinkedList.push(2);
myLinkedList.push(56);
// DE AQUI PARA ARRIBA COPIA TODO Y PEGA EN EL NAVEGADOR,
// PARA QUE YA TENGAS LA LISTA HECHA Y PRUEBAS LAS FUNCIONES
// DE ABAJO SI GUSTAS DE FORMA MÁS CÓMODA
myLinkedList.prepend(10);
myLinkedList.length;
myLinkedList.get(3);
myLinkedList.insert(20, 4)
myLinkedList.insert(20, 0)
myLinkedList.deletehead();
myLinkedList.deletetail();
myLinkedList.delete(2);
myLinkedList.delete(3);
myLinkedList.delete(4);
myLinkedList.delete(1);
myLinkedList.delete(7);
myLinkedList.delete(2);
myLinkedList.createACircuit();
Hola, les muestro mi solución a ésta clase 😅
class NodeLinked
{
constructor({ value , next = null , prev = null })
{
this.value = value
this.next = next,
this.prev = prev
}
}
class DoubleLinkedList
{
constructor(value)
{
this.head =
{
value : value,
next : null,
prev : null,
}
this.tail = this.head
this.length = 1
}
// Append an item
append(value)
{
// * <=> *
// * <=> * <=> *
const newNode = new NodeLinked({ value : value })
newNode.prev = this.tail
this.tail.next = newNode
this.tail = newNode
this.length++
return this
}
// Insert at the shift of the List
prepend(value)
{
const newNode = new NodeLinked({value : value , next : this.head})
this.head.prev = newNode
this.head = newNode
this.length++
// * <=> *
// - <=> * <=> *
return this
}
// Insert an item from the list
insert({ value , index })
{
// * <=> * <=> * <=> * <=> *
// * <=> * <=> * <=> - <=> * <=> *
const firstPointer = this.getByIndex(index - 1)
const holdingPonter = firstPointer.next
const newNode = new NodeLinked(
{ value : value , prev : firstPointer , next : holdingPonter }
)
firstPointer.next = newNode
this.length++
return this
}
// Get item by index
getByIndex(index)
{
let counter = 0
let currentCounter = this.head
while( counter !== index )
{
currentCounter = currentCounter.next
counter++
}
return currentCounter
}
// Remove an item from the list
remove(index)
{
if( index >= this.length - 1 )
{
throw Error("The index is out the range of the List")
}
if( index === 0 )
{
// //*// <=> * <=> * <=> * <=> * <=> * <=> *
// <=> * <=> * <=> * <=> * <=> *
const newHead = this.head.next
newHead.prev = null
this.head = newHead
this.length--
return this
}
// The Item is at the middle of the bottom
// * <=> * <=> * <=> //*// <=> * <=> *
// * <=> * <=> * <=> deleted <=> * <=> *
const firstPointer = this.getByIndex(index - 1)
const holdingPonter = this.getByIndex(index + 1)
firstPointer.next = holdingPonter
holdingPonter.prev = firstPointer
this.length--
return this
}
}
Dejo mi código
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);
}
if (index === 1) {
return this.prepend(value);
}
const newNode = Node(value);
const prevPointer = this.getTheIndex(index - 1);
const nextPointer = this.getTheIndex(index + 1);
newNode.prev = prevPointer;
newNode.next = nextPointer;
nextPointer.prev = newNode;
prevPointer.next = newNode;
this.length++;
return this;
}
remove(index) {
if (index >= this.length) {
console.log("El indice no existe")
return
}
if (index === 0) {
this.head = this.head.next;
this.head.prev = null;
this.length--;
return this;
}
const prevNode = this.getTheIndex(index - 1);
const nextNode = this.getTheIndex(index + 1);
prevNode.next = nextNode;
nextNode.prev = prevNode;
this.length--;
return this;
}
Que tal campeon, buen dia. comparto mi solucion Doubly Linked List…
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
append(value) {
const newNode = new Node(value);
if(!this.length) {
this.head = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
}
this.tail = newNode;
this.length++;
return this;
}
prepend(value) {
const newNode = new Node(value);
if(!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.length++;
return this;
}
insert(index, value) {
if (index < 0 || index > this.length || value === undefined) {
return null;
} else if (index === 0) {
return this.prepend(value);
} else if (index === this.length) {
return this.append(value);
} else {
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;
}
}
getTheIndex(index) {
let counter = 0;
let currentNode = this.head;
while(counter < index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
//the functionality to remove a node at specific index in our list
remove(index) {
const removeNode = this.getTheIndex(index);
let currentNode = this.head,
count = 0,
message = {Error: 'Error: non-existing node in this list.'},
beforeNodeToDelete = null,
nodeToDelete = null,
deletedNode = null;
if (this.length === 0 || index < 0) {
throw new Error(message.Error);
}
if(index === 0) {
this.head = currentNode.next;
if (this.length === 1) {
this.tail = null;
} else {
this.head.prev = null;
}
} else if(index === this.length - 1){
currentNode = this.tail;
this.tail = currentNode.prev;
this.tail.next = null;
} else {
while( count < index) {
currentNode = currentNode.next;
count++;
}
beforeNodeToDelete = currentNode.prev;
nodeToDelete = currentNode;
let afterNodeToDelete = currentNode.next;
beforeNodeToDelete.next = afterNodeToDelete;
afterNodeToDelete.prev = beforeNodeToDelete;
deletedNode = nodeToDelete;
nodeToDelete = null;
}
this.length--;
return removeNode;
}
}
const myDoubleLinkedList = new DoublyLinkedList();
Mi solucion al reto
aplicando la misma logica de la clase anterios
prepend(value){
const newNode = new Node(value);
newNode.next = this.head;
this.head.prev = newNode;
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.prev = firstPointer;
newNode.next = holdingPointer;
holdingPointer.prev = newNode;
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(this.length === 0){
alert('solo hay un elemento en la lista');
}
const firstNode = this.getTheIndex(index - 1);
const deleteNode = firstNode.next;
const holdingPointer = deleteNode.next;
firstNode.next = holdingPointer;
holdingPointer.prev = firstNode;
this.length--;
return this;
}
Aporte a la comunidad
Implementación de DLL y le agregue un catchErrorIndex para botar un error cuando se pasa un índice fuera del limite. Espero les sirva de algo.
class Node{
constructor(value){ //Creamos un nodo
this.value = value; //Guardamos el valor por parametro
this.next = null; //Como no esta en una estructura, por ahora apunta a null
this.prev = null;
}
}
class DoubleLinkedList {
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);
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
this.length++;
return this;
}
insert(index,value){
if (index >= this.length) return this.append(value);
if (index < -1) return this.prepend(value);
const newNode = new Node(value);
const previousNode = this.getNodeIndex(index - 1);
const holderNode = previousNode.next;
previousNode.next = newNode;
newNode.next = holderNode;
newNode.prev = previousNode;
holderNode.prev = newNode;
this.length++;
return this;
}
getNodeIndex(index) {
this.catchErrorIndex(index);
let counter = 0;
let currentNode = this.head;
while(counter !== index){
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
remove(index){
if(index == 0) return this.shift();
if(index == this.length -1) return this.pop();
const previousNode = this.getNodeIndex(index - 1);
const nextNode = previousNode.next.next;
previousNode.next = nextNode;
nextNode.prev = previousNode;
this.length--;
return this;
}
shift(){
const secondNode = this.head.next;
secondNode.prev = null;
this.head = secondNode;
this.length--;
return this;
}
pop(){
const secondLastNode = this.getNodeIndex(this.length - 2);
secondLastNode.next = null;
this.tail = secondLastNode;
this.length--;
return this;
}
catchErrorIndex(index) {
if (0 > index || index >= this.length) {
throw new Error(`${index} is off limits`);
}
}
}
Recuerdo que en la Universidad parecía mas difícil Hehe
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.lenght = 1;
}
append(value){
const newNode = new Node(value);
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
this.lenght++;
return this;
}
prepend(value){
const newNode = new Node(value);
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
this.lenght++;
return this;
}
insert(afterValue, value){
let pointer = this.head;
while(pointer.value != afterValue && pointer.next != null){
pointer = pointer.next;
}
if(pointer.value === afterValue){
const newNode = new Node(value);
newNode.next = pointer.next
pointer.next.prev = newNode;
newNode.prev = pointer;
pointer.next = newNode;
this.lenght++;
if(newNode.next === null){
this.tail = newNode;
}
}
}
}
Comparto mi implementación de DoublyLinkedList
class DoubleNode {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor(value) {
this.head = new DoubleNode(value);
this.tail = this.head;
this.length = 1;
}
prepend(value) {
const node = new DoubleNode(value);
this.head.prev = node;
node.next = this.head;
this.head = node;
this.length++;
return this;
}
append(value) {
const node = new DoubleNode(value);
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
this.length++;
return this;
}
lookup(depth) {
if (depth >= this.length) return console.log("ERROR: depth exceeded");
// Use the short way to find the node
let node;
if (depth <= this.length / 2) {
node = this.head;
for (let i = 0; i < depth; i++) {
node = node.next;
}
} else {
node = this.tail;
for (let i = this.length - 1; i > depth; i--) {
node = node.prev;
}
}
return node;
}
insert(value, depth) {
const node = new DoubleNode(value);
if (depth === 0) return this.prepend(value);
if (depth === this.length) return this.append(value);
const prevNode = this.lookup(depth - 1);
const nextNode = this.lookup(depth);
prevNode.next = node;
node.prev = prevNode;
nextNode.prev = node;
node.next = nextNode;
this.length++;
return this;
}
delete(depth) {
if (depth >= this.length) return console.log("ERROR: depth exceeded");
if (depth === 0) {
this.head = this.head.next;
this.head.prev = null;
} else if (depth === this.length - 1) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
const nextNode = this.lookup(depth + 1);
const prevNode = this.lookup(depth - 1);
nextNode.prev = prevNode;
prevNode.next = nextNode;
}
this.length--;
return this;
}
}
Mi solución al agregar el nuevo pointer prev, para convertir la singly linked list en doubly linked list:
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class MySinglyLinkedList {
constructor(value) {
this.head = {
value: value,
next: null,
prev: null,
};
this.tail = this.head;
this.length = 1;
}
append(value) {
const nodo = new Node(value);
nodo.prev = this.tail;
this.tail.next = nodo;
this.tail = nodo;
this.length++;
return this;
}
/* appendHead */
prepend(value) {
const nodo = new Node(value);
nodo.next = this.head;
nodo.prev = null;
this.head.prev = nodo;
this.head = nodo;
this.length++;
return this;
}
insert(index, value) {
if (index >= this.length) {
return this.append(value);
}
if (index <= 0) {
return this.prepend(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;
holdingPointer.prev = newNode;
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.lenght) || (index < 0)) {
console.log('Index out of range');
return;
} else if (index === 0) {
this.head = this.head.next;
this.head.prev = null;
this.length--;
} else if (index === this.length) {
const firstPointer = this.getTheIndex(index - 1);
firstPointer.next = null;
this.tail = firstPointer;
this.length--;
} else {
const firstPointer = this.getTheIndex(index - 1);
const holdingPointer = firstPointer.next.next;
firstPointer.next = holdingPointer;
holdingPointer.prev = firstPointer; //
this.length--;
}
return this;
}
}
Les comparto mi implementeación de la DoubleLinkedList:
class Node {
constructor(value) {
this.value = value
this.next = null
this.prev = null
}
}
class DoubleLinkedList {
constructor(value) {
this.head = new Node(value)
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++
}
prepend(value) {
const node = new Node(value)
this.head.prev = node
node.next = this.head
this.head = node
this.length++
}
insert(value, index) {
if (index < 0 || index > this.length) throw new Error('Index out of bounds')
if (index === 0) return this.prepend(value)
if (!index || index === this.length) return this.append(value)
const node = new Node(value)
const nodeAtIndex = this._getByIndex(index)
node.next = nodeAtIndex
const nodeAtPreIndex = this._getByIndex(index - 1)
nodeAtPreIndex.next = node
nodeAtIndex.prev = node
node.prev = nodeAtPreIndex
this.length++
}
remove(index) {
if (index < 0 || index > this.length) throw new Error('Index out of bounds')
if (index === 0) return this.head = this.head.next
if (index === this.length) {
const newTail = this._getByIndex(index - 1)
newTail.next = null
this.tail = newTail
return
}
const node = this._getByIndex(index - 1)
node.next = node.next.next
node.next.prev = node.prev
}
_getByIndex(index) {
let current = this.head
for (let i = 0; i < index; i++)
current = current.next
return current
}
toString() {
let current = this.head
let linkedList = `${[current.value]} <-> `
while(current.next) {
current = current.next
linkedList += `${[current.value]} <-> `
}
linkedList += 'null'
return linkedList
}
}
Métodos: prepend, insert y moveNodeToTail
Vengo a pasarles la tarea!!
- na, echenle muchas ganas, para hacer el ejercicio use la consola y una app para desktop llamada RunJS
- y recuerden que los objetos funcionan por referencia
class Node {
constructor(value){
this.value = value
this.next = null
this.prev = null
}
}
class DoublyList {
constructor(value){
this.head = {
value: value,
next: null,
prev: null
}
this.tail = this.head
this.length = 1
}
append(value){
this.length++
const node = new Node(value)
node.prev = this.tail
this.tail.next = node
this.tail = node
}
prepend(value){
this.length++
const node = new Node(value)
node.next = this.head
this.head.prev = node
this.head = node
}
insert(value, index){
if (index <= 0) this.prepend(value)
else if (index >= this.length) this.append(value)
else {
const node = new Node(value)
const indexReference = this.getIndex(index--)
// next: -1, 'x', 0, 1, 2
node.next = indexReference.next
indexReference.next = node
// prev: 2, 1, 0, 'x', -1
node.prev = indexReference.prev
indexReference.prev = node
this.length++
}
}
getIndex(index){
if (index < 0 || index > this.length)
throw new Error('Numero no valido')
let curr = this.head
for(let i = 1; i <= this.length; i++){
if(i == index) return curr
curr = curr.next
}
return curr
}
delete(index){
if (index == 1) {
const ref = this.head.next
ref.prev = null
this.head = ref
}
else if(index == this.length) {
const ref = this.tail.prev
ref.next = null
this.tail = ref
}
else {
const refPrev = this.getIndex(--index)
const refNext = refPrev.next.next
refPrev.next = refNext
refNext.prev = refPrev
}
this.length--
}
}
const list = new DoublyList(1)
// list.insert('in',2)
list.append(2)
list.prepend(0)
list.prepend(-1)
// list.append(3)
list.delete(2)
// list.prepend(0)
// list.prepend('q')
// list.insert('x',2)
// list.insert('otro',2)
// list.prepend('primero')
// list.append('ultimo')
console.log(list.tail)
Mi código u.u
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);
// agregando un nuevo nodo a la cola
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)
}
const newNode = new Node(value)
const firstPointer = this.getIndex(index -1);
const holdingPointer = firstPointer.next;
firstPointer.next = newNode;
newNode.prev = firstPointer;
newNode.next = holdingPointer;
holdingPointer.prev = newNode;
this.length++;
return this;
}
getIndex(index) {
let counter = 0;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
remove (index) {
let firstPointer = this.getIndex(index -1);
const secondPointer = firstPointer.next;
const third = this.getIndex(index +1);
firstPointer.next = third;
third.prev = firstPointer;
const previo = this.tail.value
this.tail = secondPointer;
this.tail.next = null;
secondPointer.prev = previo;
return this;
}
}
let myDoublyLinkedList = new MyDoublyLinkedList(1)
Mi código
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) {
const newNode = new Node(value);
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
this.length++;
return this;
}
insert(index, value){
if(index >= this.length){
return this.append(value);
}
if(index === 0){
return this.prepend(value);
}
const newNode = new Node(value);
const firstPointer = this.getTheIndex(index - 1);
const holdingPointer = firstPointer.next;
firstPointer.next = newNode;
newNode.next = holdingPointer;
holdingPointer.prev = newNode;
newNode.prev = firstPointer;
this.length++;
return this;
}
getTheIndex(index){
let counter = 0;
let currentNode = this.head;
while(counter !== index){
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
listFromTail(){
let currentNode = this.tail;
let data = [];
while(currentNode){
data.push(currentNode.value);
currentNode = currentNode.prev;
}
return data;
}
listFromHead(){
let currentNode = this.head;
let data = [];
while(currentNode){
data.push(currentNode.value)
currentNode = currentNode.next;
}
return data;
}
}
let myDouList = new MyDoublyLinkedList(1);
Realmente se vuelve más sencillo cuando entiendes que esta pasando con cada nodo y asignas variables para no perderte con los next y prev. Les comparto mi clase de Double Linked List con algunas modificaciones y métodos extra.
class MyDoublyLinkedList {
constructor(value) {
this.head = new Node(value);
this.tail = this.head;
this.length = 1;
}
append(value) {
const newNode = new Node(value)
if (this.length === 0) {
this.head = newNode;
this.tail = this.head;
this.length = 1;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
}
prepend(value) {
const newNode = new Node(value)
if (this.length === 0) {
this.head = newNode;
this.tail = this.head;
this.length = 1;
} else {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
}
insert(index, value) {
if (index <= 0) {
return this.prepend(value);
} else if (index >= this.length) {
return this.append(value);
} else {
const newNode = new Node(value);
const beforeNode = this.getTheIndex(index - 1);
const afterNode = this.getTheIndex(index);
newNode.next = afterNode;
newNode.prev = beforeNode;
beforeNode.next = newNode;
afterNode.prev = newNode;
this.length++;
return this;
}
}
getTheIndex(index) {
let probe = this.head;
for (let i = 0; i < index; i++) {
probe = probe.next;
}
return probe;
}
print(reverse = false) {
if (this.isEmpty()) {
return "The linked list is empty";
}
let result = "";
if (!reverse) {
let head = this.head;
for (let i = 0; i < this.length; i++) {
result += `${head.value.toString()} `;
head = head.next;
}
} else {
let tail = this.tail;
for (let i = 0; i < this.length; i++) {
result += `${tail.value.toString()} `;
tail = tail.prev;
}
}
return result
}
pop() {
if (this.isEmpty()) {
return undefined;
}
const lastNode = this.tail;
const newTail = this.tail.prev;
if (newTail != null) { newTail.next = null };
lastNode.prev = null;
this.tail = newTail;
this.length--;
return lastNode;
}
shift() {
if (this.isEmpty()) {
return undefined;
}
const firstNode = this.head;
const newHead = this.head.next;
firstNode.next = null;
if (newHead != null) { newHead.prev = null };
this.head = newHead;
this.length--;
return firstNode;
}
remove(index) {
if (this.isEmpty()) {
return undefined;
}
if (index <= 0) {
return this.shift();
} else if (index >= this.length) {
return this.pop();
} else {
const beforeNode = this.getTheIndex(index - 1);
const afterNode = this.getTheIndex(index + 1);
const removedNode = this.getTheIndex(index);
beforeNode.next = afterNode;
afterNode.prev = beforeNode
removedNode.next = null;
removedNode.prev = null;
this.length--;
return removedNode;
}
}
isEmpty() {
return (this.length <= 0) ? true : false;
}
}
Es muy complejo al principio pero se entiende
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) {
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);
}
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;
}
remove(index) {
if (index >= this.length) {
console.error("index is out of limits of the array");
return;
}
if (index == 1) {
this.head.next.prev = null;
this.head = this.head.next;
this.length--;
return this;
}
const beforePointer = this.getTheIndex(index - 1);
const currentPointer = this.getTheIndex(index);
const afterPointer = this.getTheIndex(index + 1);
afterPointer.prev = beforePointer;
beforePointer.next = afterPointer;
this.length--;
return this;
}
getTheIndex(index) {
let counter = 1;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
}
let myDoublyLinkedList = new MyDoublyLinkedList(1);
La Double Linked List tiene las mismas particularidades y funcionalidades que una single link list, pero se diferencian en que estas tienen una conexión(o nodo) de más que las single que les permiten establecer una conexión de vuelta referenciando a su elemento anterior.
++Aquí les dejo la contrucción de esta Double Link list en codigo Javascript: ++
class node {
constructor(value) {
this.next = null
this.back = null
this.value = value
}
}
class DoubleLinkedList {
constructor(value) {
this.head = {
next: null,
back: null,
value: value
}
this.tail = this.head
this.length = 1
}
append(value) {
const newNode = new node(value)
this.tail.next = newNode
newNode.back = this.tail
this.tail = newNode
this.length++;
}
prepend(value) {
const newNode = new node(value)
newNode.next = this.head
this.head.back = newNode
this.head = newNode
this.length++;
}
InsertBefore(value, index) {
if (typeof index !== "number") {
throw new Error("The position have to be a integer")
}
const newNode = new node(value)
let parentNode = this._SearchNodeBeforeOf(index)
newNode.next = parentNode.next
newNode.back = parentNode
parentNode.next = newNode
this.length++;
}
_SearchNodeBeforeOf(index) {
if(index >= this.length || index < 0) throw new Error("The index searched doesn´t exist");
let actualNode = this.head
let counter = 0
while(counter < (index-1)) {
actualNode = actualNode.next
counter++;
}
return actualNode;
}
remove() {
const tailBefore = this._SearchNodeBeforeOf(this.length - 1)
const nodeDeleted = tailBefore.next
tailBefore.next = null
this.tail = tailBefore
this.length--;
return nodeDeleted;
}
removeAt(index) {
const positionBefore = this._SearchNodeBeforeOf(index)
const nextNodes = positionBefore.next.next
const positionDeleted = positionBefore.next
delete positionBefore.next
positionBefore.next = nextNodes
this.length--;
return positionDeleted;
}
}
const doubleList = new DoubleLinkedList(1803)
doubleList.append(255)
doubleList.prepend("hello")
doubleList.prepend("It is Working")
doubleList.InsertBefore("Yeff", 2)```
comparto mi propia implementacion en java
primero una interface con los metodos
public interface InterfaceDoubleLinkedList<E> {
public void addFirst(E elemento);
public void addLast(E elemento);
public void add(E elemento, int index);
public void removeFirst();
public void removeLast();
public void remove(int index);
public boolean isEmpty();
public int size();
public E getFirst();
public E getLast();
public boolean contains(E elemento);
}
una clase que me crea nodos
public class Nodo<E> {
E elemento;
Nodo<E> prev;
Nodo<E> next;
public Nodo() {
elemento = null;
prev = null;
next = null;
}
public E getElemento() {
return elemento;
}
public void setElemento(E elemento) {
this.elemento = elemento;
}
public Nodo<E> getPrev() {
return prev;
}
public void setPrev(Nodo<E> prev) {
this.prev = prev;
}
public Nodo<E> getNext() {
return next;
}
public void setNext(Nodo<E> next) {
this.next = next;
}
}
por ultimo la implementacion de la Doubly Linked List
public class DoubleLinkedList<E> implements InterfaceDoubleLinkedList<E> {
int size;
Nodo<E> head;
Nodo<E> tail;
public DoubleLinkedList() {
size=0;
head=null;
tail=null;
}
@Override
public boolean isEmpty() {
if(this.size == 0){
return true;
}else{
return false;
}
}
@Override
public int size() {
return size;
}
@Override
public void addFirst(E elemento) {
//añade por la cabecera por la parte izquierda
if(this.isEmpty()==true){
Nodo<E> newNode = new Nodo<E>();
newNode.setElemento(elemento);
newNode.setNext(null);
newNode.setPrev(null);
this.head = newNode;
this.tail = newNode;
this.size =1;
}else{
Nodo<E> newNode = new Nodo<E>();
newNode.setElemento(elemento);
newNode.setNext(this.head);
newNode.setPrev(null);
this.head.setPrev(newNode);
this.head=newNode;
this.size++;
}
}
@Override
public void addLast(E elemento) {
//añadir por el final
if(this.isEmpty()==true){
Nodo<E> newNode = new Nodo<E>();
newNode.setElemento(elemento);
newNode.setNext(null);
newNode.setPrev(null);
this.head = newNode;
this.tail = newNode;
this.size =1;
}else{
Nodo<E> newNode = new Nodo<E>();
newNode.setElemento(elemento);
newNode.setNext(null);
newNode.setPrev(this.tail);
this.tail.setNext(newNode);
this.tail=newNode;
this.size++;
}
}
@Override
public void add(E elemento, int index) {
//añadir elemento con indice especifico
if(index==0){
this.addFirst(elemento);
}else if(index == this.size){
this.addLast(elemento);
}else if(index > this.size){
System.out.println("el indice es incorrecto");
}else{
DoubleLinkedList<E> nuevaLista = new DoubleLinkedList<E>();
int contador=0;
while(this.isEmpty() == false){
if(index==contador){
nuevaLista.addLast(elemento);
contador++;
}else{
nuevaLista.addLast(this.getFirst());
this.removeFirst();
contador++;
}
}
this.head = nuevaLista.head;
this.tail = nuevaLista.tail;
this.size = nuevaLista.size;
}
}
@Override
public void removeFirst() {
//quitar el primero
if(this.isEmpty()==true){
System.out.println("la lista esta vacia");
}else{
this.head=head.getNext();
this.size--;
}
}
@Override
public void removeLast() {
//quitar el ultimo
if(this.isEmpty()==true){
System.out.println("la lista esta vacia");
}else{
this.tail=tail.getPrev();
this.size--;
}
}
@Override
public void remove(int index) {
//Borrar con indice
if(index==0){
this.removeFirst();
}else if(index == this.size-1){
this.removeLast();
}else if(index > this.size){
System.out.println("el indice es incorrecto");
}else{
DoubleLinkedList<E> nuevaLista = new DoubleLinkedList<E>();
int contador=0;
while(this.isEmpty() == false){
if(index==contador){
contador++;
}else{
nuevaLista.addLast(this.getFirst());
this.removeFirst();
contador++;
}
}
this.head = nuevaLista.head;
this.tail = nuevaLista.tail;
this.size = nuevaLista.size;
}
}
@Override
public E getFirst() {
E elemento;
if(this.isEmpty()==true){
elemento = null;
System.out.println("la lista esta vacia");
}else{
elemento= head.getElemento();
}
return elemento;
}
@Override
public E getLast() {
E elemento;
if(this.isEmpty()==true){
elemento = null;
System.out.println("la lista esta vacia");
}else{
elemento= tail.getElemento();
}
return elemento;
}
@Override
public boolean contains(E elemento) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
}
}
Chicos les comparto ayuda visual para armar los métodos. Ojala les ayude
Mi implementación de una lista doblemente ligada.
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);
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = this.tail.next;
this.length++;
return this
}
prepend(value) {
const newNode = new Node(value);
newNode.next = this.head;
this.head.prev = newNode;
this.head = this.head.prev;
this.length++;
return this;
}
insert(index, value) {
if(index>=this.length) {
return this.append(value);
}
const newNode = new Node(value);
let currentNode = this.head;
index--;
while(index--) {
currentNode = currentNode.next;
}
const auxNode = currentNode.next;
currentNode.next = newNode;
newNode.next = auxNode;
newNode.prev = currentNode;
this.length++;
return this;
}
remove(index){
index--;
let currentNode = this.head;
while(index--) {
currentNode = currentNode.next;
}
const auxNode = currentNode.next.next;
currentNode.next = auxNode;
auxNode.prev = currentNode;
this.length--;
return this;
}
}
const myDoublyLinkedList = new DoublyLinkedList(1);
Retos cumplidos
prepend(value) {
const newNode = new Node(value);
newNode.next = this.head;
newNode.next.prev = newNode;
this.head = newNode;
this.length++;
return console.log(this.head);
}
insert(index, value) {
if (index >= this.length) {
this.append(value);
} else if (index === 0){
this.prepend(value);
} else {
const newNode = new Node(value);
let target = this.head;
let slice = undefined;
for (let i = 1; i < index; i++) {
target = target.next;
}
slice = target.next;
slice.prev = newNode;
newNode.next = target.next;
newNode.prev = target;
target.next = newNode;
this.length++;
return console.log(this.head);
}
}
remove(index) {
if (index >= this.length) {
return console.log("Índice no Válido")
} else {
let target = this.head;
let slice = undefined;
for (let i = 1; i < index; i++) {
target = target.next;
}
slice = target.next.next;
slice.prev = target;
target.next = slice;
this.length--;
return console.log(this.head);
}
}
Compañeros aquí les dejo mi solución del reto, espero les guste.
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) {
const newNode = new Node(value);
newNode.next = this.head;
this.head.prev = newNode;
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;
}
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(`Este valor ${index} excede la longitud de la LinkedList, por lo tanto no cambia`);
return this;
} else if (index == (this.length - 1)) {
const beforeNode = this.getTheIndex(index - 1);
const nextNode = null;
beforeNode.next = nextNode;
this.length--;
return this;
} else if (index == 0) {
const nextNode1 = this.getTheIndex(index).next;
nextNode1.prev = null;
this.head = nextNode1;
this.length--;
return this;
} else {
const beforeNode2 = this.getTheIndex(index - 1);
const nextNode2 = this.getTheIndex(index + 1);
beforeNode2.next = nextNode2;
nextNode2.prev = beforeNode2;
this.length--;
return this;
}
}
}
Hola, les dejo mi implementación del método para encontrar el índice:
_indexFinder(index){
const relativeIndex = index / this.length
if (relativeIndex <= 0.5){
let pointer = this.head
for (let i = 0; i < index; i++){
pointer = pointer.next
}
return pointer
} else {
let pointer = this.tail
for (let i = this.length; i > index; i--) {
pointer = pointer.prev
}
return pointer
}
}
Acá aprovecho que la lista se puede recorrer en ambos sentidos, y con la variable relativeIndex calculo si el índice que quiero encontrar está más cerca del head o del tail, para empezar desde allí, y optimizar un poco la busqueda.
class Node {
constructor(value){
this.value = value
this.next = null
this.prev = null
}
}
class MyDoublyLinkedList{
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 += 1
}
prepend(value){
const newNode = new Node(value)
newNode.prev = null
newNode.next = this.head
this.head.prev = newNode
this.head = newNode
this.length += 1
}
insert(value, position){
if(position > this.length + 1) throw new Error('Position not available')
else if(position === 0) this.prepend(value)
else if(position === this.length +1) this.append(value)
else {
const newNode = new Node(value)
let prev = this.head
let next = this.head
for(let i = 1; i < position; i++){
if( i < position -1) prev = prev.next
next = next.next
}
newNode.prev = prev
newNode.next = next
next.prev = newNode
prev.next = newNode
this.length+=1
}
}
}
let myLinkedList = new MyDoublyLinkedList(0)
myLinkedList.append(1)
myLinkedList.append(3)
myLinkedList.insert(2, 3)
console.log(myLinkedList)
Ahí va la implementación de los métodos para la Doubly Linked List:
class MyDoublyLinkedList {
constructor( value ) {
this.head = {
value: value,
next: null,
prev: null
}
this.tail = this.head
this.length = 1
}
append( value ) {
const appendedNode = new Node( value )
appendedNode.prev = this.tail
this.tail.next = appendedNode
this.tail = appendedNode
this.length += 1
return this
}
prepend( value ) {
const prependedNode = new Node( value )
// const previousHead = this.head
// this.head = prependedNode
// this.head.next = previousHead
this.head.prev = prependedNode
prependedNode.next = this.head
this.head = prependedNode
this.length += 1
return this
}
get( index ){
let currentNode = this.head
for( let i=0; i < index; i++){
currentNode = currentNode.next
}
return currentNode
}
insert ( value, position ){
if( position === 0)
return this.prepend( value )
else if( position >= this.length )
return this.append( value )
else {
const insertedNode = new Node( value )
let previousNode = this.get( position - 1 )
let nextNode = previousNode.next
insertedNode.next = nextNode
previousNode.next = insertedNode
insertedNode.prev = previousNode
nextNode.prev = insertedNode
}
this.length += 1
return this
}
remove( index ){
const removedNode = this.get( index )
if( index === 0) {
removedNode.next.prev = null
this.head = this.head.next
}
else{
const previousNode = this.get( index - 1 )
if( index === this.length - 1 ){
previousNode.next = null
this.tail = previousNode
}
else {
previousNode.next = removedNode.next
removedNode.next.prev = previousNode
}
}
this.length -= 1
return removedNode
}
}
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
}
preppend(value) {
const newNode = new Node(value)
newNode.next = this.head
this.head = newNode
this.head.next.prev = this.head
this.length++
return this
}
insert(index, value) {
if (index >= this.length) {
return this.append(value)
}
const newNode = new Node(value)
const firstPointer = this.getIndex(index - 1)
const holdingPointer = firstPointer.next
holdingPointer.prev = newNode
firstPointer.next = newNode
newNode.next = holdingPointer
newNode.prev = firstPointer
this.length++
return this
}
getIndex(index) {
let counter = 0
let currentNode = this.head
while (counter !== index) {
currentNode = currentNode.next
counter++
}
return currentNode
}
}
Adjunto mi respuesta del remove
getTheIndex (index) {
let counter = 0
let currentNode = this.head
while (counter !== index) {
currentNode = currentNode.next
counter++
}
return currentNode
}
remove (index) {
// Validar que el index exista
if (index >= this.length) {
return console.log('Este index se sale del rango del linkedList')
}
// Busco el index
const firstPointer = this.getTheIndex(index - 1)
const removePoint = this.getTheIndex(index)
const holdingPointer = removePoint.next
firstPointer.next = holdingPointer
this.length--
return this
}
Hola a todos, dejo la solución al problema planteado con los métodos vistos anteriormente
class Node {
constructor(value){
this.value = value;
this.next = null;
this.prev = null;
}
}
class myDoubleLinkedList {
constructor(value){
this.head = {
value: value,
next: null,
prev: null,
}
this.tail = this.head;
this.length = 0;
}
append(value){
const newNode = new Node(value);
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
this.length++;
}
preppend(value){
const newNode = new Node(value);
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
insert(value, index){
if( index === 0 ){
this.preppend(value);
return this;
}else if( index >= this.length ){
this.append(value);
return this;
}
const newNode = new Node(value);
const itemsSelected = this.findIndexNode(index - 1);
newNode.next = itemsSelected.next;
newNode.prev = itemsSelected;
itemsSelected.next = newNode;
this.length++;
return this;
}
remove(index){
if( index === 0){
this.head = this.head.next;
this.head.prev = null;
}else if( index === (this.length - 1) ){
const getLastNode = this.findIndexNode(index);
getLastNode.next = null;
this.tail = getLastNode;
}else{
if( index >= this.length ){
console.error('No existe indice insertado');
return this;
}
let getNode = this.findIndexNode(index - 1);
getNode.next = getNode.next.next;
getNode.next.prev = getNode;
}
this.length--;
}
findIndexNode(index){
let returnedItem = this.head;
let counter = 0;
while( counter < index ){
returnedItem = returnedItem.next;
counter++;
}
return returnedItem;
}
}
let myDoubledList = new myDoubleLinkedList(1);
Dejo mi consejo para lograr comprender mejor el tema y que el mismo quede bien claro.
-
Buscar explicaciones más o menos didácticas, de acuerdo a cual es nuestra carencia en la comprensión (Foros, webs informativas, YouTube, etc).
-
Escribir el código y hacer los ejercicios sin copiarlos hasta que se le agarre el truco.
-
NO RENDIRSE!! Sé que es un tema difícil de comprender a la primera, pero nada que el trabajo y la persistencia no solucione. Ánimos!
Mi aporte de double linked list
class Node {
constructor(value){
this.value = value
this.next = null
this.prev = null
}
setNext(next) {
this.next = next
}
setPrevious(previous) {
this.prev = previous
}
getValue(){
return this.value
}
getNext(){
return this.next
}
getPrevious(){
return this.prev
}
}
class DoubleLinkedList {
constructor(value){
this.head = new Node(value)
this.tail = this.head
this.length = 1
}
append(value){
const newNode = new Node(value)
newNode.setPrevious(this.tail)
this.tail.setNext(newNode)
this.tail = this.tail.next
this.length++
return this
}
preppend(value){
const newNode = new Node(value)
newNode.setNext(this.head)
this.head = newNode
this.length++
return this
}
insert(index, value){
if(index > this.length) {
return this.append(value)
}
if (index <= 0) {
return this.preppend(value)
}
const newNode = new Node(value)
let actualNode = this.head
for (let i = 0; i < index - 1; i++) {
actualNode = actualNode.getNext()
}
newNode.setPrevious(actualNode)
newNode.setNext(actualNode.getNext())
newNode.getNext().setPrevious(newNode)
actualNode.setNext(newNode)
this.length++
return this
}
remove(index){
let actualNode = this.head
let del = false
let count = 0;
if(index >= this.length) {
return undefined
}
while (!del) {
if(index === count + 1){
const replaceNode = actualNode.getNext()
if(replaceNode !== null){
actualNode.setNext(replaceNode.getNext())
actualNode.getNext().setPrevious(actualNode)
} else {
actualNode.setNext(null)
this.tail = actualNode
}
del = true
} else {
actualNode = actualNode.getNext()
count++
}
}
this.length--
return this
}
}
const myList = new DoubleLinkedList(1)
Tal cual como nos indica el profesor, al entender la lógica, la modificación de las funciones es más fácil.
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class MyDoublyListkedList {
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) {
const newNode = new Node(value);
this.head.prev=newNode;
newNode.next = this.head;
this.head = newNode;
this.length++
return this
}
getTheIndex(index) {
let counter = 0;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
insert(value, index) {
if(!index){
return this.prepend(value);
}
if (index >= this.length) {
return this.append(value)
}
const newNode = new Node(value);
let firstPointer = this.getTheIndex(index - 1);
let holdingPointer = firstPointer.next;
firstPointer.next = newNode;
newNode.prev = firstPointer;
newNode.next = holdingPointer;
holdingPointer.prev = newNode;
this.length++
return this
}
passEnd(value) {
let pointer = this.head;
if (this.head.value == value) {
this.head = this.head.next;
this.length--;
return this.append(value);
}
while (pointer.next !== null) {
if (pointer.next.value == value) {
if (pointer.next.next !== null) {
pointer.next = pointer.next.next;
} else {
return this;
}
this.append(value);
this.length--;
return this;
}
pointer = pointer.next;
}
this.append(value);
return this;
}
}```
Comparto mi código con sus métodos
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) { // Agrega un nodo al final de la lista
const newNode = new Node(value);
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
prepend(value) { // Agrega un nodo al inicio de la lista
const newNode = new Node(value);
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
this.length++;
return this;
}
insert(index, value) { // Agrega un nodo en la posición (index) seleccionada de la lista
if(index <= 0) {
return this.prepend(value);
}
if(index > this.length -1) {
return this.append(value);
}
const newNode = new Node(value);
let currentNode = this.head;
for(let i = 0; i < index -1; i++) {
currentNode = currentNode.next;
}
let afterPointer = currentNode.next;
currentNode.next = newNode;
newNode.next = afterPointer;
newNode.prev = currentNode;
afterPointer.prev = newNode;
this.length++;
return this;
}
remove(index) { // Elimina un nodo en la posición (index) seleccionada de la lista
let currentNode = this.head;
if(index < 0 || index > this.length -1) {
return new Error("Index out of range");
}
if(index === 0) {
this.head = currentNode.next;
this.head.prev = null;
this.length--;
return this;
}
for(let i = 0; i < index -1; i++) {
currentNode = currentNode.next;
}
let afterPointer = currentNode.next;
currentNode.next = afterPointer.next;
currentNode.next.prev = currentNode;
if(!currentNode.next) {
this.tail.value = currentNode.value;
}
this.length--;
return this;
}
}
let myLinkedList = new MyDoublyLinkedList(1);
Reto Cumplido!
class Node{
constructor(value){
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoubleLinkedList{
constructor(value){
this.head ={
value: value,
next:null,
prev:null,
}
this.tail=this.head;
this.length = 1;
}
append(item){
const value = new Node(item);
value.prev = this.tail;
this.tail.next = value;
this.tail = value;
this.length++
return this;
}
prepend(item){
const value = new Node(item);
this.head.prev = value;
value.next = this.head;
this.head = value;
this.length++;
return this.head;
}
validate(index){
if (isNaN(index)){
console.log("Ups... " + index + " no es un numero valida.");
return true;
} else {
if (!(index % 1 == 0)) {
console.log(`El numero ${index} debe de ser un numero decimal`);
return true;
}
}
if(index < 0){
console.log('no existe esa posicion');
return true;
}
return false;
}
search(index){
let nextitem = this.head;
for (let i = 0; i < index-1; i++) {
nextitem = nextitem.next;
}
return nextitem;
}
insert(index, item){
// Verificar que los valores sean correctos
if(this.validate(index)){
return console.log('huvo un error');
}
if(index === 0){
return this.prepend(item);//si es igual a 0, que ejecute la funcion prepend
}
if(index >= this.length){
return this.append(item);
}
// Comienza con el codigo
const nextitem = this.search(index);
const temporal = nextitem.next;
const value = new Node(item);
nextitem.next = value;
temporal.prev = value;
value.prev = nextitem;
value.next = temporal;
this.length++;
return this.head;
}
delete(index){
if(this.validate(index)){
return console.log('huvo un error');
}
if(index >= this.length){
return console.log('El numero no puede ser mayor a la cantidad de nodos')
}
if( index == 0) {
this.head = this.head.next;
this.head.prev = null;
this.length--;
return this.head;
}
const nextitem = this.search(index);
const temporal = nextitem.next.next;
temporal.prev = nextitem;
nextitem.next = temporal;
this.length--;
return this.head;
}
}
Mi solución al reto
prepend(value) {
const newHead = new Node(value)
newHead.next = this.head
newHead.prev = null
this.head.prev = newHead
this.head = newHead
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.prev = firstPointer
holdingPointer.prev = newNode
this.length++
return this
}
remove(index) {
if(index >= this.length || index < 0) {
return console.error(`No existe el nodo ${index}`)
}
const beforeNodeToRemove = this.getIndex(index - 1)
const nodeToRemove = this.getIndex(index)
const holdingPointer = nodeToRemove.next
beforeNodeToRemove.next = holdingPointer
holdingPointer.prev = beforeNodeToRemove
this.length--
return this
}
Métodos prepend, insert y remove
// Prepend
prepend(value) {
const newNode = new Node(value);
newNode.next = this.head;
this.head.prev = newNode
this.head = newNode;
this.length++;
return this;
}
// Insert
insert(index, value) {
if (index >= this.length) {
console.log('Index mayor a tamaño lista');
return this.append(value);
}
const newNode = new Node(value);
const firstPointer = this.getTheIndex(index - 1);
const holdingPointer = firstPointer.next;
const nextPointer = this.getTheIndex(index + 1);
const prevPointer = nextPointer.prev;
firstPointer.next = newNode;
newNode.next = holdingPointer;
newNode.prev = prevPointer;
this.length++;
return this;
}
// Remove
remove(index) {
const previousPointer = this.getTheIndex(index - 1);
const holdingPointer = this.getTheIndex(index + 1);
previousPointer.next = holdingPointer;
holdingPointer.prev = previousPointer;
this.length--;
return this;
}
Saludos y sigan metiéndole!
les dejo mi código, me ayudo mucho el siguiente link , que lo compartió un compañero en clases anteriores. Me falto el insert por falta de timepo.
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class MyDoubleLinkedList {
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) {
const newNode = new Node(value);
if (this.head) {
this.head.prev = newNode;
newNode.next = this.head
} else {
this.tail = newNode;
}
this.head = newNode;
this.length++;
return this;
}
deleteFirst() {
if (!this.head) { return null }
this.head = this.head.next;
if (this.head) {
this.head.prev = null;
} else {
this.tail = null;
}
this.length--;
return this;
}
deleteLast() {
if (!this.tail) { return null }
this.tail = this.tail.prev;
if (this.tail) {
this.tail.next = null;
} else {
this.head = null;
}
this.length--;
return this;
}
}
let myDoublyLinkedList = new MyDoubleLinkedList(1);
Reto completado para los metodos trabajados! 😎
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) {
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);
}
if (index === 0) {
return this.prepend(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;
holdingPointer.prev = newNode;
this.length++;
return this;
}
getTheIndex(index) {
let counter = 0;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
//Remove node
remove(index) {
if (this.length === 0) {
console.log("List already empty");
return undefined;
}
if (index > this.length - 1) {
return undefined;
}
const selectedNode = this.getTheIndex(index);
const previousNode = this.getTheIndex(index - 1);
if (index === 0) {
this.head = selectedNode.next;
} else if (index === this.length - 1) {
this.tail = previousNode;
previousNode.next = null;
} else {
const postNode = this.getTheIndex(index + 1);
previousNode.next = selectedNode.next;
postNode.prev = previousNode;
}
this.length--;
return this;
}
}
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);
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
this.length++;
return this;
}
insert(index, value){
if(index >= this.length){
return this.append(value);
}else if(inde === 0){
return this.prepend(value);
}
const newNode = new Node(value);
const before = this.getIndex(index - 1);
const after = this.getIndex(index);
newNode.prev = before;
newNode.next = after;
before.next = newNode;
after.prev = newNode;
this.length++;
return this;
}
remove(index){
if(index >= this.length){
return this.removeLast();
}else if(index === 0){
return this.removeFirst();
}
const before = this.getIndex(index - 1);
const after = this.getIndex(index + 1);
before.next = after;
after.prev = before;
this.length--;
return this;
}
removeFirst(){
this.head = this.head.next;
this.head.prev = null;
this.length--;
return this;
}
removeLast(){
const newLast = this.getIndex(this.length - 2);
newLast.next = null;
this.tail = newLast;
this.length--;
return this;
}
getIndex(index){
let pointer = this.head;
for(let i = 0; i < index; i++){
pointer = pointer.next;
}
return pointer;
}
}
Los otros métodos:
prepend(value){
const newNode = new Node(value);
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
this.length++;
return this;
}
insert(value, index){
if( index >= this.length){
return this.append(value);
}
const newNode = new Node(value);
const firstPointer = this.getIndex(index -1);
const holdingPointer = firstPointer.next;
holdingPointer.prev = newNode;
firstPointer.next = newNode;
newNode.prev = firstPointer;
newNode.next = holdingPointer;
this.length ++;
return this;
}
remove(index){
if(index >= this.length){
console.log("esta fuera del alcance");
}else if(index === 0){
this.head = this.head.next;
this.head.prev = null;
this.length --;
return this;
}else{
const firstPointer = this.getIndex(index -1);
const holdingPointer = firstPointer.next.next;
const eliminatePointer = firstPointer.next;
eliminatePointer.prev = null;
firstPointer.next = holdingPointer;
holdingPointer.prev = firstPointer;
this.length --;
return this;
}
}
getIndex(index){
let counter = 0;
let currentNode = this.head;
while(counter !== index){
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
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) {
const newNode = new Node (value);
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
this.length++;
}
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.getTheIndex(index - 1);
const holdingPointer = firstPointer.next;
firstPointer.next = newNode;
newNode.prev = firstPointer;
newNode.next = holdingPointer;
holdingPointer.prev = newNode;
}
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.log(`Ingresaste un valor no valido, ingresa un valor entre 0 y ${this.length}`)
} else if (index == 0 ) {
this.head = this.head.next;
this.head.prev = null;
this.length--;
} else if (index == this.length) {
const firstPointer = this.getTheIndex(this.length - 1);
this.tail = firstPointer;
this.tail.next = null;
this.length--;
} else {
const beforePointer = this.getTheIndex(index - 1);
const afterPointer = this.getTheIndex(index + 1)
beforePointer.next = afterPointer;
afterPointer.prev = beforePointer;
this.length--;
}
}
}
let myLinkedList = new MyDoublyLinkedList(1);
prepent(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);
//encontramos el nodo en la posicion index-1
const nodeInsert = this.getIndexNode(index - 1);
//guardamos su next en holdingPointer para que no se pierda
const holdingPointer = nodeInsert.next;
console.log(holdingPointer);
//el nodeInset.next le añadimos el newNode
nodeInsert.next = newNode;
//le holdingPointer.pren ahora apunta a newNode
holdingPointer.prev = newNode;
//newNode.next ahora apunta a holdingPointe
newNode.next = holdingPointer;
//y su previus a apunta al node Insert
newNode.prev = nodeInsert;
this.length++;
return this;
}
getIndexNode(index) {
let counter = 0;
let current = this.head;
while (counter !== index) {
counter++;
current = this.head.next;
}
return current;
}```
La implementación en los otros métodos me quedó así:
class DoubleNode {
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) {
let newNode = new DoubleNode(value)
newNode.prev = this.tail
this.tail.next = newNode
this.tail = newNode
this.length ++
return this
}
prepend(value) {
let newNode = new DoubleNode(value)
newNode.next = this.head
this.head.prev = newNode
this.head = newNode
this.length ++
return this
}
getTheIndex(index) {
let currentNode = this.head
let counter = 0
for (let i = 0; i < index; i++){
currentNode = currentNode.next
counter = i
}
return currentNode
}
insert(index, value) {
if (index === 0) return this.prepend(value)
if (index >= this.length) return this.append(value)
let newNode = new DoubleNode(value)
let previousNode = this.getTheIndex(index -1)
let nextNode = previousNode.next
newNode.prev = previousNode
nextNode.prev = newNode
newNode.next = nextNode
previousNode.next = newNode
this.length++
return this
}
remove(index) {
if (index === 0) return this.shift()
if (index === this.length - 1) return this.pop()
if (index >= this.length) return undefined
let removedElement = this.getTheIndex(index)
let previousNode = this.getTheIndex(index - 1)
let nextNode = this.getTheIndex(index + 1)
previousNode.next = nextNode
nextNode.prev = previousNode
this.length --
return removedElement
}
shift() {
let deletedElement = this.head
this.head = this.head.next
this.head.prev = null
this.length --
return deletedElement
}
pop() {
let deletedElement = this.tail
let newTail = this.getTheIndex(this.length - 2)
newTail.next = null
this.tail = newTail
this.length --
return deletedElement
}
}
Métodos para Double Linked List
🖤 Método insert
insert(index ,value){
if(index >= this.length){
return this.add(value)
}
const newNode = new Nodes(value)
const currentNode = this.getTheIndex(index)
const previousNode = this.getTheIndex(index -1)
previousNode.next = newNode
newNode.prev = previousNode
newNode.next = currentNode
currentNode.prev = newNode
this.length ++;
}
🖤 Método remove
remove(index){
const nodoTraslated = this.getTheIndex(index +1)
const nodoReceptor = this.getTheIndex(index -1)
nodoReceptor.next = nodoTraslated
nodoTraslated.prev = nodoReceptor
this.length --;
}
🖤Método get
get(){
let currentNode = this.head;
for(let i = 0; i < this.length; i++){
if(currentNode){
console.log(currentNode.value)
currentNode = currentNode.next
}
}
}
Here is my code:
.
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
constructor(value) {
this.head = new Node(value);
this.tail = this.head;
this.length = 1;
}
append(value) {
let node = new Node(value);
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
this.length++;
}
prepend(value) {
let node = new Node(value);
node.next = this.head;
this.head.prev = node;
this.head = node;
this.length++;
}
get(index) {
let pointer = this.head;
let count = 0;
while (pointer != null) {
if (count === index) return pointer;
pointer = pointer.next;
count++;
}
return null;
}
insert(value, index) {
if (index === 0) return this.prepend(value);
if (index >= this.length) return this.append(value);
if (index > 0 && index < this.length) {
const pointer = this.get(index);
if (pointer) {
const prevPointer = pointer.prev;
const node = new Node(value);
prevPointer.next = node;
pointer.prev = node;
node.prev = prevPointer;
node.next = pointer;
this.length++;
return;
}
}
console.log("index out of bounds: " + index);
}
remove(index) {
if (index === 0) {
this.head = this.head.next;
this.head.prev = null;
this.length--;
return;
}
if (index > 0 && index < this.length) {
const pointer = this.get(index);
if (pointer) {
const nextPointer = pointer.next;
const prevPointer = pointer.prev;
prevPointer.next = nextPointer;
if (nextPointer) nextPointer.prev = prevPointer;
else this.tail = prevPointer;
this.length--;
return;
}
}
console.log("index out of bounds: " + index);
}
toString() {
let pointer = this.head;
let s = "";
while (pointer != null) {
s +=
pointer === this.head
? "(H: "
: pointer === this.tail
? "(T: "
: "(N: ";
s += pointer.value + ") -> ";
pointer = pointer.next;
}
s += "NULL | length = " + this.length;
console.log(s);
}
}
Por poco y no me animo a hacerlos…
prepend(value) {
const newNode = new Node(value);
// Doubly: sgt linea
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
this.length++;
}
insert(index, value) {
if(index >= this.length) {
console.log("No hay suficientes elementos, será enviado al final");
return this.append(value);
}
const newNode = new Node(value);
let firstPointer = this.getTheIndex(index - 1);
let secondPointer = this.getTheIndex(index);
let holdingPointer = firstPointer.next;
firstPointer.next = newNode;
newNode.next = holdingPointer;
// Doubly: sgts 3 líneas
holdingPointer.prev = newNode;
firstPointer = newNode.prev;
holdingPointer = secondPointer;
this.length++;
return this;
}
El getTheIndex es el mismo que el del singly
Del método insert solo hay que añadir esas 3 líneas y convertir al first y secondPointer a let porque hay que modificarlos
Para insertar un nodo al inicio de la lista:
prepend(value){//*Inserta al inicio
const newNode = new Node(value)
newNode.next = this.head
this.head.prev = newNode
this.head = newNode
this.lenght++
return this
}
Para insertar un nuevo nodo en un lugar específico solamente agregué esta línea después de ‘newNode.next = holdingPointer’
newNode.prev = firstPointer
Para eliminar un nodo específico:
remove(index){
if (index >= this.lenght) {
console.error("Index is out of limits of array")
}else if(index === 0){ //* Si es el primer elemento
this.head = this.head.next //* Apunta a sí mismo
//!No hace falta this.tail=null porque así empieza
this.lenght--
}else if(index === this.lenght-1){ //* Si es el último
const firstPointer = this.getTheIndex(index-1)
firstPointer.next = null
this.tail = firstPointer
this.tail.prev = null
this.lenght--
}else{ //* Si es uno de en medio
const firstPointer = this.getTheIndex(index-1)
const nextPointer = this.getTheIndex(index+1)
let pointerToRemove1 = this.getTheIndex(index)
let pointerToRemove2 = this.getTheIndex(index)
pointerToRemove1 = firstPointer.next
firstPointer.next = pointerToRemove1.next
pointerToRemove2 = nextPointer.prev
nextPointer.prev = pointerToRemove2.prev
this.lenght--
}
}
Reto de la clase
Plantear el problema en papel primero ayuda bastante
Añadí validaciones cuando index sea un valor negativo o 0
LES COMPARTO MI CÓDIGO CON LAS MODIFICACIONES CORRESPONDIENTES
prepend(value){
const newNode = new Node(value);
// si insertamos al inicio de la linked list
// no tiene sentido retornar un valor previo
// entonces su valor será null
newNode.prev = null;
newNode.next = this.head;
this.head = newNode;
this.length++
return this;
}
insert(index, value){
if(index === 0){
return this.prepend(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;
//validación para ejecutar correctamente el valor "prev"
if(index > 0){
newNode.prev = firstPointer;
} else{
newNode.prev = null
}
this.length++;
return this;
}```
Este es el metodo remove ajustado
// Elimina nodo por indice
remove (index) {
const nextPointer = this.getTheIndex(index + 1);
const previoPointer = this.getTheIndex(index - 1);
// const currentPointer = this.getTheIndex(index);
if (index > this.length) {
console.log("Indice no existe");
}
if (index < 0) {
console.log("Indice menor a 0");
}
if (index === 0) {
this.head = nextPointer;
nextPointer.prev = null;
this.length--;
return this;
}
previoPointer.next = nextPointer;
nextPointer.prev = previoPointer;
this.length--;
return this
}
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;
}
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class MySingleLinkedList {
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);
newNode.next = this.head;
newNode.prev = null;
this.head = newNode;
this.tail.prev = 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;
holdingPointer.prev = newNode;
this.length++;
return this;
}
remove(index) {
if (index >= this.length) {
return 'indice no valido';
}
if (index == 0) {
this.head = this.head.next;
this.head.prev = null;
this.length--;
return this;
}
const firstPointer = this.getTheIndex(index - 1);
const removePointer = this.getTheIndex(index);
firstPointer.next = removePointer.next;
firstPointer.next.prev = firstPointer;
this.length--;
return this;
}
getTheIndex(index) {
let counter = 0;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
}
let myDoublyLinkedList = new MySingleLinkedList(1);```
las doubly linked list son las que tienen dos referencias en memoria, los cuales corresponden al nodo anterior y al nodo siguiente, esto nos permite avanzar al siguiente nodo y retroceder al nodo anterior.
Solución al reto
Aquí les comparto mi código fuente, lo he probado y esta funcionando bien.
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;
}
/** Agregar un nodo al final */
append(value) {
const newNode = new Node(value);
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
/** Agregar un nodo al principio */
prepend(value)
{
const newNode = new Node(value);
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
/** Inserta un nuevo nodo en la posicion index */
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;
holdingPointer.prev = newNode;
this.length++;
return this;
}
/** Remueve el nodo de la posición index */
remove(index)
{
if (index > this.length) {
console.log('Indice no valido');
return this;
}
if (index == 0) {
this.head = this.head.next;
this.head.prev = null;
this.length--;
return this;
}
const firstPointer = this.getTheIndex(index - 1);
const removePointer = this.getTheIndex(index);
firstPointer.next = removePointer.next;
firstPointer.next.prev = firstPointer;
this.length--;
return this;
}
/** Obtengo el nodo del indice dado */
getTheIndex(index)
{
let counter = 0;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
}
let myDoublyLinkedList = new MyDoublyLinkedList(1);
// Para probar
myDoublyLinkedList.append(2);
myDoublyLinkedList.append(3);
myDoublyLinkedList.append(4);
myDoublyLinkedList.prepend(0);
myDoublyLinkedList.insert(4, 20);
myDoublyLinkedList.remove(4);
No la probé mucho si encuentran algún bug me avisan o me comentan sus versiones
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) {
const newNode = new Node(value);
newNode.prev = null;
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
insert(index, value) {
if (index < 0) {
const inverseIndex = this.length - Math.abs(index);
index = inverseIndex > 0 ? inverseIndex : 0;
}
if (index >= this.length) {
return this.append(value);
}
if (index === 0) {
return this.prepend(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;
holdingPointer.prev = newNode;
this.length++;
return this;
}
remove(index) {
if (index < 0) {
const inverseIndex = this.length - Math.abs(index);
index = inverseIndex > 0 ? inverseIndex : 0;
}
if (index >= this.length) {
console.error("index out of range");
return;
}
this.length--;
const nextPointer = this.getTheIndex(index + 1);
if(index === 0) {
this.head = nextPointer;
this.head.prev = null;
return this;
}
const previousPointer = this.getTheIndex(index - 1);
previousPointer.next = nextPointer;
nextPointer.prev = previousPointer;
return this;
}
getTheIndex(index) {
let counter = 0;
let currentNode = this.head;
while (counter != index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
}```
¿Quieres ver más aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesión.