5

Tengo una pregunta y espero que alguien me pueda ayudar, aun sigo aprendiendo sobre el mundo de JavaScript.

En el siguiente código se esta creando algo que los gringos llaman Singly linked list y la verdad todo esto lo estoy aprendiendo desde un libro en inglés pero no hay mas información :(

En el método reverse lo que hace es básicamente revertir la lista, algo simple. Entiendo cómo logra poner todo en reverso, pero lo que no entiendo tiene que ver con referencias, entendía o creía entender como funcionaba esto pero resulta que no.

En el siguiente código, la variable node esta apuntando a head (var node = this.head), this.head esta apuntando a this.tail (this.head = this.tail) y this.tail ahora esta apuntando a node, en resumen la cabeza ahora es la cola y la cola ahora es la cabeza, todo bien hasta aquí.

reverse(){
  var node = this.head;
  this.head = this.tail;
  this.tail = node;
  var next;
  var prev = null;
  for(var i = 0; i < this.length; i++){
    next = node.next;
    node.next = prev;
    prev = node;
    node = next;
  }
  return this;
}

Ahora cuando el for termina de iterar, para mí supuestamente todo lo esta revirtiendo para la variable node, si this.head esta apuntando a this.tail y cuando this.tail es aplastado por node, ahora si se hace un console.log(this.head === this.tail) dara como resultado false, lo que significa que ahora los dos son independientes del uno del otro, pero al finalizar this.tail solo tiene un elemento osea el primer elemento de la cabeza y mágicamente this.head tiene todo el node revertido.

¿Cómo logra actualizar this.head si solo se esta actualizando la variable node y ni si quiera this.head esta apuntando a la variable node???

Aquí les dejo el código completo:

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

    class List{
        constructor(){
            this.head = null;
            this.tail = null;
            this.length = 0;
        }
        push(val){
            var newNode = new Node(val);
            if(!this.head){
                this.head = newNode;
                this.tail = this.head;
            } else {
                this.tail.next = newNode;
                this.tail = newNode;
            }
            this.length++;
            return this;
        }
        reverse(){
          var node = this.head;
          this.head = this.tail;
          this.tail = node;
          var next;
          var prev = null;
          for(var i = 0; i < this.length; i++){
            next = node.next;
            node.next = prev;
            prev = node;
            node = next;
          }
          return this;
        }
    }

    var list = new List()
list.push(1)
list.push(2)
list.push(3)
list.push(4)
list.push(5)

2 respuestas 2

3

Voy a modificar un poco el código para añadir comentarios durante la ejecución, a ver si lo ves más claro:

const listado = document.querySelector('ol');

function log(...textos) {
  const li = document.createElement("li");
  li.appendChild(document.createTextNode(textos.join(' ')));
  listado.appendChild(li);
}

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

class List{
  constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
  }
  
  push(val){
    log('Añadiendo el valor', val, 'a la cola de la lista');
    var newNode = new Node(val);
    if(!this.head){
        log('La lista está vacía,', val, 'es cola y cabeza');
        this.head = newNode;
        this.tail = this.head;
    } else {
        this.tail.next = newNode;
        this.tail = newNode;
    }
    this.length++;
    return this;
  }
  
  reverse() {
    log('revirtiendo, la cola será la cabeza y viceversa')
    var node = this.head;
    this.head = this.tail;
    this.tail = node;
    var next;
    var prev = null;
    log('Node apunta a la cabeza');
    for(var i = 0; i < this.length; i++){
      log('Node es', node.val);
      next = node.next;
      node.next = prev;
      log('Node.next pasa a ser', (node.next) ? node.next.val : 'null');
      prev = node;
      node = next;
      log('Movemos node:');
    }
    return this;
  }
}

var list = new List()
list.push(1)
list.push(2)
list.push(3)
list.push(4)
list.push(5)
list.reverse();
<ol>
</ol>

Lo que está haciendo es ir a cada nodo de la lista y "girarlo", haciendo que next apunte al que anteriormente le apuntaba a él. Por tanto, si dos tenía como siguiente (next) a 3, ahora es 3 el que tiene como siguiente a 2, mientras que 2 tiene como siguiente a 1. Node empezó apuntando a la cabeza, pero en cada iteración ha ido apuntando al que era el siguiente nodo para ir girándolo, ayudándose de las variables auxiliares next y prev.

5
  • Si entiendo el procedimiento de como se vuelve reverso eso esta muy claro para mi, lo que yo pregunto es sobre this.head el esta apuntando a la cola, que solo tiene un elemento y al finalizar tiene todo el reverso, si en console.log(this.head === this.tail) da como resultado falso. Commented el 11 sept. 2019 a las 13:06
  • Es lo que te estoy explicando: 5 pasa a tener como next a 4, que a su vez pasa a tener como next a 3... y así hasta el elemento 1. Commented el 11 sept. 2019 a las 13:09
  • Ok es oficial soy idiota xd, no pregunto por el procedimiento del reverso, lo que a mi me llama la antencion es que si haces un console.log(this.head === this.tail) dara falso, lo que significa que cada uno es un objecto diferente verdad?? y si es un objecto diferente como llega a tener el reverso osea el node si para que pase esto para mi la logica seria this.head.next = node al final Commented el 11 sept. 2019 a las 13:17
  • var node = this.head; this.head = this.tail; this.tail = node; console.log(this.head === this.tail) // false Commented el 11 sept. 2019 a las 13:27
  • Pásate por el chat y lo hablamos, porque no entiendo la duda y va a ser más sencillo Commented el 11 sept. 2019 a las 13:47
-1

Ok ya lo entendí :), y estaba en lo correcto cuando decía que todo esto es por temas de referencias.

Lo voy a explicar para que alguien en el futuro le sirva de ayuda.

Mi pregunta era sobre como llegaba a actualizarse this.head y solo tenia un elemento {val:5, next:null} osea los valores de la cola.

En el siguiente código tengo mi head (mi cabeza):

var head = {
    val:1,
    next: {
        val:2,
        next:{
            val:3,
            next:{
                val:4,
                next: {
                    val:5,
                    next:null
                }
            }
        }
    }
}

y aqui tengo mi tail (mi cola):

var tail = head.next.next.next.next

Mi tail esta apuntado a ultimo objecto de mi cabeza: {val:5, next:null}.

y si se modifica de esta manera: head pasa a apuntar a la cola y la cola pasa a apuntar a la cabeza:

var node = head
head = tail;
tail = node;

Por lo que yo al hacer console.log(head === tail) // false eso da falso por que son dos objectos diferentes es obvio.

pero que pasaría si tu haces esto tail.next.next.next.next.val = 6, si revisas tu head veras que el valor se cambio y esto se debe a la referencia, ya que tail.next.next.next.next === head // true

Antes de comenzar el for tail.next tiene todo el head, pero al iniciar tail.next es null y head sigue teniendo un solo valor {val:5, next:null}.

Al finalizar el for y tocar la referencia {val:5, next:null} osea la cola, guardada en head, lo que va a pasar es lo que paso cuando yo hice tail.next.next.next.next.val = 6head tendra todo el reverso y asi es como todo esto tiene mas sentido para mi xd.

Se que quisas esto sea obvio para otros, pero yo aun sigo aprendiendo cosas que parecen fáciles, tarde mucho pero al final lo entendí y espero qe esto motive a los demás programadores novatos a no rendirse nunca :)

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.