No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Construyendo una Singly Linked List

16/29
Recursos

Aportes 55

Preguntas 5

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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.

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

<h4>Cabe destacar que:</h4>
  • 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.

隆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)

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;
    }
}

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);

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```

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 鈥減rivada鈥 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;
    }
}

}

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;
  }