Odd Even Linked List en JavaScript

<h1>Introducción</h1>

En el curso de Algoritmos Avanzados: Estructuras de datos lineales se enseñan los principales tipos de datos lineales, así como diversos algoritmos que usan a estos datos lineales.

Sin embargo, muchos de estos algoritmos son resueltos en lenguajes de programación con los que talvez no estés muy familiarizado, como Java o C++. Esto puede llegar a ser un poco frustante, ya que tu quieres saber como implementar todos estos tipos de datos lineales en el mundo real, con los lenguajes que tu uses en tu trabajo o para proyectos personales.

Pero no te preocupes, en este tutorial se ve una implementación sencilla de una lista enlazada en JavaScript (el lenguaje favorito de todo desarrollador web), así como la solución del algoritmo “Odd Even Linked List”

<h1>Descripción del problema</h1>

El algoritmo se llama “Odd Even Linked List”, el cual consiste en modificar una lista enlazada para que primero esten acomodados los nodos impares y al final los nodos pares.

Esta imagen lo que representa son 5 nodos, donde cada uno tiene su indice. Lo que el problema propone es que primero se esten apuntando a los nodos impares, para que los pares queden al final.

Antes de empezar a pensar en una posible solución a este problema, necesitamos recordar que es una lista enlazada y cómo funciona.

<h1>Lista Enlazada/Linked List</h1>

Esta estructura de datos lineal nos permite tener una referencia en memoria de cada uno de los nodos que la conforman. Lo que quiere decir que el primer nodo, conocido como “Cabeza”, apunta hacia otro nodo y este a su vez apunta hacia la referencia de otro.

Al final del día, si nosotros vemos una lista enlazada desde arriba, se parece mucho a un “array”. La principal diferencia es como se guardan estos espacios en la memoria. Un array lo hace de manera secuencial, mientras que una lista enlazada lo hace de manera aleatoria. Cada una de estas implementaciones cuenta con ciertas ventajas y desventajas, en términos del performance para acceder a los datos.

En la imagen de arriba se puede ver de una mejor manera como se guardan los datos en un array, así como en una lista enlazada en la memoria.

<h1>Lista Enlazada en JavaScript</h1>

classNode{
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

classLinkedList{
  constructor() {
    this.size = 0;
    this.head = null;
  }

  add(node) {
    if (this.size === 0) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }

    this.size++;
  }
}

El código de arriba demuestra una implementación muy sencilla de una lista enlazada. Las listas enlazadas estan conformadas por Nodos, por lo que esta clase esta al principio. Después tenemos la clase de la lista enlazada, que solo tiene el método de add(Node), ya que es el único que vamos a utilizar para este algoritmo.

Para empezar con una lista enlazada de cinco elementos como en la imagen del ejemplo, tendriamos que hacer algo así:

const myLinkedList = new LinkedList();
myLinkedList.add(new Node(1));
myLinkedList.add(new Node(2));
myLinkedList.add(new Node(3));
myLinkedList.add(new Node(4));
myLinkedList.add(new Node(5));

Ok, esa es una muy mala implementación, no solo se ve feo, puede llegar a ser confuso. Vamos a hacer un poco mejor este código:

// Modificación en el constructor de la clase LinkedListclassLinkedList{
  constructor(...args) {
    this.size = 0;
    this.head = null;

    args.forEach((item) => this.add(new Node(item)));
  }
}

// La creación de la lista enlazadaconst myLinkedList = new LinkedList(1, 2, 3, 4, 5);

Eso se ve mucho mejor. Sin embargo, todavía tenemos un problema. ¿Cómo sabemos qué nuestra Lista Enlazada realmente esta en orden, cómo sabemos que nuestra implementación del código realmente funciona?

Bueno, yo personalmente me encargue de hacer una pequeña abstracción para que en consola nos muestre cada uno de nuestros nodos, de manera ordenada:

// FunciónfunctionforEachNode(linkedList, callback) {
  let current = linkedList.head;
  for (let i = 0; i < linkedList.size; i++) {
    callback(current);
    current = current.next;
  }
}

// Cómo usarlaconst myLinkedList = new LinkedList(1, 2, 3, 4, 5);
forEachNode(myLinkedList, (node) => console.log(node));

Básicamente lo que se hace es pasarle una lista enlazada a la función forEachNode y el callback lo que recibe es cada uno de los Nodos, justo como en funciones de JS tales como Array.prototype.map o Array.prototype.filter.

Con esta función puedes ver en consola que los Nodos estan ordenados de manera correcta.

<h1>Solución al algoritmo</h1>

Ahora que ya tenemos un LinkedList y sabemos que funciona de manera correcta, el siguiente paso es pensar en una solución.

La solución propuesta en el curso habla de iterar toda la Lista Enlazada e ir modificando la propiedad next de cada Nodo de acuerdo a si es Odd (par) o Even (impar) y al ultimo Nodo darle el valor de next a una variable que tengamos guardada desde el principio. Todo esto sin olvidarnos de que hay que agregar dos apuntadores hacia la cabeza y cabeza.next.

Ok, esto fue mucha información, vamos a resumir la solución paso a paso:

Paso #1

Tener dos apuntadores. Uno hacia linkedList.head y otro hacia linkedList.head.next. Esto porque cada uno de estos apuntadores se van a ir cambiando por toda la lista enlazada mientras recorremos cada uno de sus Nodos. Además de que haciendolo de esa forma, sabemos cuál es el primer Nodo Par y el primero Impar.

functionoddEvenOrder(linkedList) {
  let oddPointer = linkedList.head;
  let evenPointer = oddPointer.next;
}

Paso #2

Una vez teniendo los apuntadores, hay que encontrar una manera de poder iterar cada uno de los Nodos. Por suerte, nosotros ya teniamos una pequeña función que nos ayuda a eso: forEachNode

functionoddEvenOrder(linkedList) {
  let oddPointer = linkedList.head;
  let evenPointer = oddPointer.next;
  let count = 0;

  forEachNode(linkedList, (current) => {
    count++;

    if (count >= 3) {
      console.log(current)
    }
  });
}

Lo que se hizo en el código de arriba fue iterar por cada Nodo, saltandose los primeros dos.
¿Porqué nos saltamos los primeros dos? Me alegra que preguntes! Esto se hizo así ya que los primeros dos Nodos ya los tenemos en los apuntadores. El primer Nodo dentro de una Lista Enlazada siempre va ser el head y el segundo head.next

Paso #3

Este paso es uno de los más dificiles de entender, ya que entra un poco de lógica, pero tu ya tienes experiencia en esto, por lo que no creo que sea un gran problema para ti.
Lo que se hace aqui es un validación. Si el Nodo actual es par, se modifica la propiedad next del puntero que contiene al nodo par, para que apunte al actual (el cual debería ser par) y a su vez, el puntero se actualiza por el nodo actual. Lo mismo pasa con el impar.

Para que quede un poco más claro, lo que nosotros ya sabemos es que después de saltarnos los dos primeros Nodos, el número 3 es impar:

forEachNode(linkedList, (current) => {
  count++;

  if (count >= 3) {
    if (count % 2 !== 0) { // odd// 👇// Estaríamos entrando aquí cuando el Nodo es 3
    } else { // even

    }
  }

  if (count === linkedList.size) current.next = circularNode;
});

De la misma manera, sabemos que el apuntador oddPointer en ese momento es la cabeza (osea el primer Nodo). Entonces, lo que hacemos es cambiar la propiedad .next de la cabeza, que en ese momento es oddPointer para que sea el Nodo número 3

if (count >= 3) {
   if (count % 2 !== 0) { // odd// 👇// Estaríamos entrando aquí cuando el Nodo es 3
     oddPointer.next = current
   } else { // even

   }
}

Así mismo, ahora debemos cambiar el valor de oddPointer, ya que ahora en lugar de ser la cabeza, queremos que sea el Nodeo3:

if (count >= 3) {
   if (count % 2 !== 0) { // odd// 👇// Estaríamos entrando aquí cuando el Nodo es 3
     oddPointer.next = current
     oddPointer = current
   } else { // even

   }
}

Esto mismo se hace para cuando el Nodo es par, por lo que el código hasta ahora quedaría de la siguiente manera:

functionoddEvenOrder(linkedList) {
  let oddPointer = linkedList.head;
  let evenPointer = oddPointer.next;
  let count = 0;

  forEachNode(linkedList, (current) => {
    count++;

    if (count >= 3) {
      if (count % 2 !== 0) {
        // odd
        oddPointer.next = current;
        oddPointer = current;
      } else {
        // even
        evenPointer.next = current;
        evenPointer = current;
      }
    }
  });
}

Llevamos un gran avance, aunque algo importante a mencionar es que lo que hace la función oddEvenOrder() es mutar al linkedList que se le manda por parametro. Por lo tanto, lo que te reto a hacer ahora es con el código que llevamos hasta ahora trata de modificar el linked list, haber que es lo que la consola nos muestra. Algo como lo siguiente:

// Crea un linkedListconst myLinkedList = new LinkedList(1, 2, 3, 4, 5);

// Logealo antes y después de que haya sido mutado// por oddEvenOrder
forEachNode(myLinkedList, (node) => console.log(node));
oddEvenOrder(myLinkedList);
forEachNode(myLinkedList, (node) => console.log(node));

<h1>Último paso 😎</h1>

Probablemente te salio un error dentro de la función forEachNode, cierto. Lo que te dice es que hay un nodo que no tiene la propiedad de next. Si analizamos nuestra solución, esto tiene mucho sentido, ya que al último nodo de nuestro ejemplo (El Nodo5) no le estamos asignando ningún valor siguiente, lo que significa que la lista enlazada esta rota. Sin embargo, hay una manera muy sencilla de arreglarlo:

• Asignar una variable llamada nodoCircular, que nos ayude a atar la lista de nuevo. Esta variable debe ser asignada al principio de la solución. En teoría debe ser alguno de los apuntadores declarados al principio (linkedList.head o linkedList.head.next). Esto depende si el último valor de la lista enlazada es par o impar:

functionoddEvenOrder(linkedList) {
  const circularNode = linkedList.size % 2 === 0 ? linkedList.head : linkedList.head.next;

  // Mode code...
}

• Al final de nuestra iteración, le asignamos como propiedad next al último Nodo nuestro nodoCircular, atando de nuevo la lista enlazada

if (count === linkedList.size) current.next = circularNode;

Y listo, ahora por último, vamos a ver cómo queda todo el código de nuestro algoritmo:

functionoddEvenOrder(linkedList) {
  const circularNode =
    linkedList.size % 2 === 0 ? linkedList.head : linkedList.head.next;
  let oddPointer = linkedList.head;
  let evenPointer = oddPointer.next;
  let count = 0;

  forEachNode(linkedList, (current) => {
    count++;

    if (count >= 3) {
      if (count % 2 !== 0) {
        // odd
        oddPointer.next = current;
        oddPointer = current;
      } else {
        // even
        evenPointer.next = current;
        evenPointer = current;
      }
    }

    if (count === linkedList.size) current.next = circularNode;
  });
}

Ahora sí has de nuevo la validación para ver si en verdad el resultado es el esperado.

const myLinkedList = new LinkedList(1, 2, 3, 4, 5);

forEachNode(myLinkedList, (node) => console.log(node));
oddEvenOrder(myLinkedList);
forEachNode(myLinkedList, (node) => console.log(node));