Construcción de Listas Enlazadas en JavaScript

Algo importante que quiero que noten, miren cómo Diego pone esta imagen con los cuadritos al azar:

Bueno, no los puso así porque si, los puso así porque las Linked List guardan los nodos aleatoriamente en la memoria, sí, aunque esta estructura de datos solo conoce a su siguiente nodo, los nodos pueden estar guardados aleatoriamente en la memoria porque cada nodo sabe cuál es la referencia de memoria del siguiente nodo 😉

Hay dos formas en las que se puede accesar a la información.

-Acceso Aleatorio: Se puede acceder al n-ésimo elemento de una lista de elementos en un tiempo constante. Ejemplo de esto son los arreglos, ya que como se ha mencionado en el curso, se reservan espacios de memorias seguidos (sean arreglos dinámicos o no). Por esto, se puede acceder directamente a las posición 3 de un arreglo (myArray[2]).

• Acceso Secuencial: En este caso, un grupo de elementos es accedido en un predeterminado orden secuencial. Las linked list son ejemplo de esto. Como no están de manera continua en memoria, para acceder a un nodo en particular, debemos recorrer la lista, accediendo a los apuntadores del siguiente elemento. Es decir, si quiero acceder a la posición 3 de la lista, debo pasar por la posición 1, luego a la 2 y ahí llego a la 3.
  
  

El recurso Array vs Linked List Data Structures lo explica muy bien 🙋🏽‍♀️.

Se parece al callback hell v:

Una diferencia visual entre una lista y un arreglo

Linked List

Array

Dejo mi código usando recursividad:

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

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

    this.length = 1;
  }

  checkNode(node){
    if(!node.next){
      return node;
    }
    return this.checkNode(node.next);
  }

  append(val){
    const newNode = new Node(val);
    const lastNode = this.checkNode(this.head);
    lastNode.next = newNode;
    this.tail = newNode;
    this.length++;
    return this.head;
  }
}

let myLinkedList =  new MySingleLinkedList(1);
myLinkedList.append(2)
myLinkedList.append(3)
console.log(myLinkedList);

Las Linked List siempre se deben leer desde el primer elemento.

Estamos rompiendo con el paradigma de prototipos de JavaScript parece clase de java. las clases no están mal, esta muy claro, pero creo que deberíamos hacer uso los prototipos y la estructura de JavaScript con funciones. Aunque al final casi todo es un objeto, pero en JavaScript son de tipo prototipos.

¡Hola! Les dejo el código con los apuntes de esta clase y la anterior, espero les sirva.

// ¿Cómo se ve una linked list?

//El null permite un colocar un nodo nuevo
1 --> 2 --> 3 --> 4 --> 5 --> null

//La linked List nos regresa un objeto, como la que se muestra a continuación
let singlyLinkedList = {
    head: {
        value: 1,
        next: {
            value: 2,
            next: {
                value: 3,
                next: {
                    value: 4,
                    next: null
                }
            }
        }
    }
}

// A continuación construimos la clase en Javascript de el objeto mostrado.

//Cada uno de los elementos tiene que tener un nodo, así que hacemos una instancia del Nodo con una clase para no tener que repetir código en la class MySinglyLinkesList.

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

class MySinglyLinkedList {
    //El valor nos permite iniciar esta estructura de datos con un elemento dentro. 
    constructor(value) {
        //Cabeza de la Linked List
        this.head = {
            value: value,
            next: null,
        }
        //La cola de la Linked List también está apuntada a la cabeza por lo que no existe ningún otro valor 

        this.tail = this.head

        //Contamos los elementos de la lista
        this.lenght = 1
    }
    append(value) {
        //Recibimos el valor y lo añadimos al final
        let currentNode = new Node(value)
        //Cambiamos el valor siguiente(next) de la cola(tail).
        this.tail.next = currentNode
        //El último Nodo se convierte ahora en la nueva cola (tail)
        this.tail = currentNode
        this.lenght++
    }
}

let mySinglyLinkedList = new MySinglyLinkedList(1)

• Para recorrer una linked list tenemos que pasar por todos y cada uno de los nodos, y siempre desde la cabeza, entonces ya podemos ver que es un poco ineficiente para algunos casos ya que no podemos acceder al valor de un nodo de manera rapida solo como su indice o su key como si seria el caso en los arrays y las tablas de hash.
• Sino que por el contrario debemos de recorrer cada uno de los nodos si o si hasta llegar al que nos interesa.
• Una ventaja es que al tener direccionenes de en donde esta en siguiente nodo, no hace falta que estén en memoria continua, como los arrays, sino que estos pueden estar en cualquier parte de la memoria y simplemente se referencia la ubicación en memoria de los nodos.

LinkedList y Array: Imagina que tienes una fila de personas. Si la fila de personas fuera una matriz, podrías darle a cada una un número y llamarlas por ese número. Si fueran una LinkedList, entonces para acceder a cualquiera tendrías que empezar por la primera persona y pasar por cada una de las siguientes hasta llegar a la persona que quieres encontrar.

Por lo tanto, un array siempre puede acceder a una cosa sin ninguna espera, pero es posible que tenga que mirar a cada persona en una lista enlazada.

Una LinkedList es mejor cuando no se conoce el número de cosas de antemano que se almacenan, ya que las matrices son de tamaño fijo

Mi reto:

class SinglyList{
    constructor(value){
        this.head={
            value:value,
            next: null,
        }
        this.tail = this.head;
        this.length = this.size();
        //this.length = 1;
    }
    size() {
        let i = 0;
        let nodo = this.head;
        while(nodo){
            i++
            nodo = nodo.next;
        }
        return i;
    }
}

Me gusta cuando el profe dice “si no puedes no te preocupes” porque a veces no puedo y no me preocupo

Así fue como hice yo el metodo append para agregar un elemento a la LinkedList:

    append(value){
        let newNode = new Node(value)

        let lastNode = this.head;
        
        for(let i = 1; i  < this.length; i++){
            lastNode = lastNode.next;
        }

        lastNode.next = newNode;

        this.length++;
        this.tail = newNode;
    }

MY NOTES FOR LINKED LIST

//Graficamente se veria asi la funcion de linkedlist solo 
  //Que nos regresaria un objeto
    // 1 --> 2 --> 3 --> 4 --> 5 --> null


//Esta es la estructura que manejan los linkedlist 
  //Tenemos un objeto con un valor y que tendria el valor siguiente
    //Puesto en un segundo objeto y asi sucesivamente 
      //Hasta llegar al valor que queremos obtener
let singlyLinkedList = {

  head:{

    value:1,
    next: {

      value : 2,
      next: {

        value:3,
        next:{

          value:4,
          next:{

            next: null
          }
        }
      }
    }

  }


}

//Creamos una clase la cual se encargara de generar nodos
  //Con esto cada vez que haga un metodo donde necesite inicializar
    // Un nodo hago una instancia de este nodo, agrego el valor
      //Y iniciamos el metodo

class Node{

  constructor(value){

    this.value = value;
    this.next  = null;
  }
}

//Creamos una clase para generar el linkedlist
class MySinglyLinkedList{

  //Va a tener un contructor que recibe un valor por parametro
  constructor(value){

    this.head = {
      //Este valor viene del valor que le pasamos por parametro al constructor
      value: value,
      next: null,


    }
    //La cola del linkedlist la cual apuntaria a la cabeza porque no tiene ningun valor
    this.tail = this.head;

    this.length = 1;
  }


  }

Academind siempre me ayuda a entender algunos conceptos que no quedan del todo claros
Academind

Aplicando la clase con prototipos de JS.
Por cierto redefini el constructor de la clase LinkedList para iniciar con una lista vacia…

/** Define Node class */
function Node(value) {
  this.value = value;
  this.next = null;
}

/** Define SinglYLinkedList class */
function LinkedList() {
  this.head = null;
  this.tail = null;
  this.length = 0;
}

/** Define "methods" for SinglYLinkedList class */
LinkedList.prototype.append = function (value) {
  const newNode = new Node(value);
  if (!this.tail) {
    this.tail = newNode;
    this.head = this.tail;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.length += 1;
};

/** Instanciated */
const newLinkedList = new LinkedList();
newLinkedList.append(6);
newLinkedList.append(5);
newLinkedList.append(1);
newLinkedList.append(8);
newLinkedList.append(2);
newLinkedList.append(7);

console.log(newLinkedList);

Comparte éste artículo: https://medium.com/@bohndez.dev/estructuras-de-datos-linked-list-en-javascript-e84f3c50a4c4

Mi solución al reto

  append(value) {
    const newTale = new Node(value);
    if (this.tail === this.head) {
      this.head.next = newTale;
      this.tail = newTale;
      this.length++;
      return this.tail;
    }
    this.tail.next = newTale;
    this.tail = newTale;
    this.length++;
    return newTale;
  }

Les dejo mi código.

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

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

    append(value){
        //Recibimos un valor
        let currentNode = new Node(value)
        //Cambiamos el valor del next del tail
        this.tail.next = currentNode
        //el ultimo nodo se convierte ahora en el tail
        this.tail = currentNode
        this.length++
    }

}

let myLinkedList = new MySinglyLinkedList(1)
myLinkedList.append(12)
myLinkedList.append(13)
myLinkedList```

Lo modifique para que la lista pueda inicializarse vacia

class ENode {
  constructor(value) {
    this.value = value;
    this.next = undefined;
  }
}

class ELinkedList {


  constructor($_item = undefined) {
    this.length = 0,
      this.head = this.tail = new ENode($_item);
    $_item && this.length++
  }

  toArray() {
    let pointer = this.head, out = [];
    while (pointer) {
      out.push(pointer.value);
      pointer = pointer.next;
    }
    return out;
  }

  addFirst($_item) {
    // Create a new node
    const node = new ENode($_item);

    if (this.length === 0) {
      this.head = this.tail = node;
    }
    else {
      // Set the new element to the head
      node.next = this.head;
      this.head = node;
    }
    this.length++
  }

  addLast($_item) {
    const node = new ENode($_item);

    if (this.length === 0) {
      this.head = this.tail = node;
    }
    else {
      // Set the new element to the tail
      this.tail.next = node;
      this.tail = node;
    }
    this.length++

  }

}

export default ELinkedList;

Método append

class MySinglyLinkedList {

    constructor(value) {

        this.head = {

            value: value,
            next: null

        }

        this.tail = this.head;

        this.length = 1;

    };

    append(value) {

        const newNode = new Node(value);

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

        return this;;

    };

};

Habria sido util que en este curso se agregaran operaciones con estructuras de datos, seria un curso mas completo.

Lo hice de esta manera y creo que funciona bien:

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

Reto cumplido (al menos como imaginé la estructura planteada en la clase):
.
.
.

class Node {
    constructor(value){ //instance the node with a mandatory value, therefore impossible to create empty nodes
        this.value = value;
        this.next = null;
    }
}
//creating class node to not repeat the same structure every time we add a new node to the linked list

class MySinglyLinkedList {
    constructor(value){
       this.head = {
        value: value, //head will have its value that is mandatory to instance the class
        next: null, //first node as will be the head, will have null as next value, allowing to insert a tail
       };
        this.tail = this.head; //tail will be the same head as being the first and only node when instancing the class

        this.length = 1; //our first value
    }
    append(node){
        this.tail = node;
        this.head.next = this.tail;
        this.length++;
        //appending nodes at the end of the list
    }
}
//each singly linked list will start with one head as only node with mandatory value (as for this case), a tail (pointing to head) and a total length of 1

const mySinglyLinkedList = new MySinglyLinkedList(1);
console.log(mySinglyLinkedList);
// MySinglyLinkedList {
//     head: { value: 1, next: null },
//     tail: { value: 1, next: null },
//     length: 1
//   }

const node = new Node(3);
console.log(node);
// Node { value: 3, next: null }

console.log(mySinglyLinkedList.append(node));
console.log(mySinglyLinkedList)
// MySinglyLinkedList {
//     head: { value: 1, next: Node { value: 3, next: null } },
//     tail: Node { value: 3, next: null },
//     length: 2
//   }

Mi aporte

  append(value){
        let newNode = new Node(value)
        newNode.next=this.tail
        this.tail=newNode
    }

Yo lo hice de esta manera y al parecer funciona

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

Les comparto mi método para insertar antes de ver la solución:

    insert(value) {
        const newElement = new Node(value);
        let pointer = this.head;
        while (pointer.next) {
            pointer = pointer.next;
        }
        pointer.next = newElement;
        this.tail = pointer;
        this.length += 1;
    }

Mi solución al reto con operador rest para poder añadir muchos al mismo tiempo:

 class Node<T> {
  constructor(
    public value: T,
    public next: Node<T> | null = null
  ) {}
}

export class SinglyLinkedList<T> {
  private head: Node<T> | null = null;
  private tail: Node<T> | null = null;
  private _length: number = 0;

  constructor(...values: T[]) {
    this.append(...values);
  }

  append (...values: T[]) {
    for (const value of values) {
      const node = new Node(value);
      if (this.head === null || this.tail === null) {
        this.head = node;
        this.tail = node;
      } else {
        this.tail.next = node;
        this.tail = node;
      }
      this._length++;
    }
  }

  get length(): number {
    return this._length;
  }
}

Les dejo mi solución al reto:
.

Dejo mi solución al método append:
.

No estoy 100% seguro si esta solucion esta bien 🧐

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

La memoria no siempre tiene los espacios requeridos de forma contigua y una de las ventajas de las LinkedList es que pueden guardar sus datos en espacios no contiguos

Solución:

prepend(value){
        let newNode = new Node(value);
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        return this;
    }

Mi solucion al metodo append:

class MySingleLinkedList {

    //...código igual al video

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

Función Append:

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

        let head = this.head;

        for (let i = 0; i < this.lenght; i++) {
            if (!head.next) {
                head.next = node;
                this.lenght++;
                this.tail = node;
                return node;
            }
            head = head.next;
        }
        return undefined;
    }

Les comparto el codigo de mi metodo, no recuero si ya se los había compartido, pero aquí se los dejo jeje

append(value){
        this.tail = new Node(value)
        this.head.pointer = this.tail
        this.length++
    }

Les comparto el códgio de como construí el método appnend, espero su retroalimentacion ❤️

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

class MySinglyLinkedList {
    constructor(value){
        this.head = {
            value: value,
            next:null
        }

        this.tail = this.head;

        this.length = 1
    }

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

let myLinkedList = new MySinglyLinkedList(1);

Uff, me costó lo suyo, pero aquí está mi reto 😄

append(value) {
  let node = new Node(value);

  if (this.head.next == null) {
    this.head.next = this.tail = node;
    this.length++;
    return node;
  }

  this.tail.next = node;
  this.tail = node;
  this.length++;

  return node;
}

Mi método append

  append(value) {
    let node = new Node(value);

    if(!this.tail) {
      this.head = this.tail = node;
      return node;
    }

    this.tail.next = node;
    this.tail = node;

    return node;
  }

Comparto mi solución con su explicación

Aun no acabo la clase, y Diego cada día me sorprende mas con sus excelentes explicaciones.

Les dejo por aqui mi codigo, es una manera de no tener que preocuparnos de establecer el length en cada método de la función

class ListaSimplementeEnlazada{
    constructor(value){
        this.head={
            value:value,
            next: null,
        }
        this.tail = this.head;
        this.length = this.size();
        //this.length = 1;
    }
    size() {
        let i = 0;
        let nodo = this.head;
        while(nodo){
            i++
            nodo = nodo.next;
        }
        return i;
    }
}

Mi solución basada en la de un compañero:

append(value) {
        let currentNode = this.head;

        while (currentNode.next !== null) {
            currentNode = currentNode.next;
        }

        currentNode.next = new Node(value);
        this.tail = new Node(value);
        this.length++;
    }

Mi solución

class Node {
    constructor(value){
        this.value = value
        this.next = null
    }
    setNext(value) {
        this.next = new Node(value)
    }
    getValue(){
        return this.value
    }
    getNext(){
        return this.next
    }
}

class SingleLinkedList{
    constructor(value){
        this.head = new Node(value)
        this.tail = this.head
        this.length = 1
    }
    append(value){
        this.tail.setNext(value)
        this.tail = this.tail.next
        this.length++
    }
}

Hola mi solucion al reto

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

el append para la proxima clase

append(value){
        this.tail = new Nodo(value);
        this.length++;
        this.head.next = this.tail;
        return this.head;
    }

Reto:

Mi implementación del método de append.

    append(value) {
        if(this.head.next === null){
            this.head.next = new Node(value);
            this.tail = this.tail.next;
            this.length++;
        }else {
            const currentNode = this.head;
            while(currentNode != this.tail){
                currentNode = currentNode.next;
            }
            currentNode.next = new Node(value);
            this.tail = currentNode.next;
            this.length++;
        }
    }

Comparto mi solución a la siguiente clase sin haberla visto, espero lo haya hecho bien jeje

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

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

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

Cambie un poco la estructura de la clase Node para que al crearla nos devuelva un objeto con la misma caracteristica de this.head, esto lo hice mas que nada para seguir un mismo orden de objetos (Object. Object, Object… ) y no mezclar clases (Object, Node, Node, Node…)

Tambien se puede crear una funcion “privada” que nos genere un objecto de forma {value, next} y evitar crear una clase aparte como Node

class Node{
  constructor(value){
    return {
      value,
      next: null
    }
  }
}

class SinglyLinkedList{
  constructor(value){
    this.head = {
      value,
      next: null
    }

    this.tail = this.head;
    this.length = 1;
  }

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

const singlyList = new SinglyLinkedList(1);
singlyList.append(2);
singlyList.append(3);
singlyList.append(4);
singlyList.append(5);

Mi solución al reto :

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

        if (this.head.next === null) {
            this.head.next = newTail;
            this.tail = newTail;
            this.length ++;
            return value;
        }

        this.tail.next = newTail;
        this.tail = newTail;
        this.length ++;
        return value;
    }

:3

<code>

class node{
    constructor(value){
        this.value = value
        this.next = null
    }
}

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

        this.lenght = 1
    }
    append(value){
        let currentNode = new node(value)

        this.tail.next = currentNode
        this.tail = currentNode
        this.lenght++
    }
}

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

class MySinglyLinkedList{
    constructor(node){
        this.head = node
        this.tail = this.head
        this.length = 1
    }
    append(node){
        let prev = this.tail
        this.tail = node
        prev.next = node
        this.length += 1
    }
}
let node1 = new Node(1)
let node2 = new Node(2)
let node3 = new Node(3)
let myLinkedList = new MySinglyLinkedList(node1)
myLinkedList.append(node2)
myLinkedList.append(node3)
console.log(myLinkedList)

append(valor){
let nodo = new Node(valor); // este nodo ya tiene como next a null , por lo que ya es el tail

let currentNode = this.head;

for(let i = 0 ; i < this.length ; i++){

    if (currentNode.next != null ){
      currentNode = currentNode.next ;
    }else{
      currentNode.next = nodo ;
      this.tail = nodo;
      this.length++;
      break;
    }
}

}

https://carbon.now.sh/

Ahí va el reto con los métodos para agregar un valor al inicio y al final:

    append( value ) {

        const appendedNode = new Node( value )

        this.tail.next = appendedNode
        this.tail = appendedNode

        this.length += 1

    }

    preppend( value ) {

        const preppendedNode = new Node( value )

        const previousHead = this.head

        this.head = preppendedNode
        this.head.next = previousHead

        this.length += 1

    }

Listo el reto!!! hice el método para agregar al final de la lista:

    add (valor) {
        let currentNode = this.head;
        // Recorrer lista hasta llegar al último nodo
	while(currentNode.next != null)
        {
	    // Desplazarse en los nodos
            currentNode = currentNode.next;
        }

	// Agregar el nuevo nodo, ponerlo como cola y aumentar lenght
        currentNode.next = new Nodo(valor);
        this.lenght++;
        this.tail = currentNode.next;
    }

}

// Instanciar
let List = new SingleList(1);
List.add(2);
List.add(3);

 append(value) {
    const nodo = new Nodo(value);
    this.tail.next = nodo;
    this.tail = nodo;
  }