DSA LinkedList

Trabajando con la lista vinculada

Conceptos clave

• La lista vinculada es una estructura de datos lineal similar a una matriz. Sin embargo, a diferencia de las matrices, los elementos no se almacenan en una ubicación o índice de memoria particular. Más bien, cada elemento es un objeto separado que contiene un puntero o un enlace al siguiente objeto en esa lista.
• El nodo es el nombre de cada elemento en la lista. Contienen dos elementos: los datos almacenados y un enlace al siguiente nodo. Los datos pueden ser cualquier tipo de datos válido.
• Head es el punto de entrada a una lista vinculada. El cabezal es una referencia al primer nodo en la lista vinculada. El último nodo en la lista apunta a NULL. Si una lista está vacía, la cabeza es una referencia nula.

Pros y contras

• Los nodos se pueden eliminar o agregar fácilmente de una lista vinculada sin reorganizar toda la estructura de datos. Esta es una ventaja que tiene sobre matrices.
• Las operaciones de búsqueda son lentas en listas vinculadas. A diferencia de las matrices, no se permite el acceso aleatorio de elementos de datos. Se accede a los nodos secuencial a partir del primer nodo.
• Utiliza más memoria que matrices debido al almacenamiento de los punteros.

Tipos de lista vinculada

• Listas vinculadas individualmente : cada nodo contiene solo un puntero al siguiente nodo.
• Listas de doble vinculación : cada nodo contiene dos punteros, un puntero al siguiente nodo y un puntero al nodo anterior.
• Listas circulares vinculadas : las listas circulares vinculadas son una variación de una lista vinculada en la que el último nodo apunta al primer nodo o cualquier otro nodo antes, formando así un bucle.

Ejemplos de código JavaScript

Clase de nodo

 class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

Clase de lista vinculada

 class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

Crear lista vinculada

 let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2
let list = new LinkedList(node1)

console.log(list.head.next.data) //returns 5

Métodos de la lista vinculada

• Tamaño : este método devuelve el número de nodos presentes en la lista vinculada.

 size() {
    let count = 0; 
    let node = this.head;
    while (node) {
        count++;
        node = node.next
    }
    return count;
}

• Pantalla : este método muestra todos los nodos en la lista.

 const ListFunctions = {
  display: (linkedList) => {
    items = [];

    if (linkedList.head === null) {
      return "The list is empty";
    } else {

      let currNode = linkedList.head;

      while (currNode.next !== null) {
        items.push(currNode.data);
        currNode = currNode.next;
      }

      items.push(currNode.data);
    }

    return `Linked List Items: ${items.join("->")}`;
  }

• IsEmpty : este método verifica si la lista está vacía sin usar el método size ().

  isEmpty: (linkedList) => {
    if (linkedList.head === null) {
      return `This list is empty`;
    }
    return `There are items in this list`;
  }

• Buscar : este método encuentra un nodo en la lista.

  find(item) {
    let currNode = this.head;

    if (!this.head) {
      return null;
    }

    while (currNode.data !== item) {
      if (currNode.next === null) {
        return null;
      } else {
        currNode = currNode.next;
      }
    }
    return currNode;
  }
}

• Borrar : este método vacía la lista.

 clear() {
    this.head = null;
}

• Eliminar : este método elimina un nodo de la lista.

  remove(item) {
    if (!this.head) {
      return null;
    }

    if (this.head.data === item) {
      this.head = this.head.next;
      return;
    }

    let currNode = this.head;
    let previousNode = this.head;

    while (currNode !== null && currNode.data !== item) {
      previousNode = currNode;
      currNode = currNode.next;
    }

    if (currNode === null) {
      return;
    }
    previousNode.next = currNode.next;
  }

• InsertFirst : este método inserta un nodo en la primera posición de la lista vinculada.

 insertFirst(item) {
    this.head = new _Node(item, this.head);
  }

• InsertLast : este método inserta un nodo en la última posición de la lista vinculada.

  insertLast(item) {
    if (this.head === null) {
      this.insertFirst(item);
    } else {
      let tempNode = this.head;
      while (tempNode.next !== null) {
        tempNode = tempNode.next;
      }
      tempNode.next = new _Node(item, null);
    }
  }

• InsertBefore : este método inserta un nodo antes de un nodo dirigido en la lista vinculada.

 insertBefore(item, key) {
    if (!this.head) {
      return;
    }

    if (this.head.data === key) {
      this.insertFirst(item);
      return;
    }

    let currNode = this.head;
    let previousNode = this.head;

    while (currNode !== null && currNode.data !== key) {
      previousNode = currNode;
      currNode = currNode.next;
    }

    if (currNode === null) {
      console.log(`key value not found`);
      return;
    }

    previousNode.next = new _Node(item, currNode);
  }

• InsertAfter : este método inserta un nodo después de un nodo dirigido en la lista vinculada.

  insertAfter(item, key) {

    if (!this.head) {
      return;
    }

    if (this.head.data === key) {
      this.insertFirst(item);
      return;
    }

    let currNode = this.head;
    let nextNode = this.head;

    while (currNode !== null && currNode.data !== key) {
      currNode = nextNode;
      nextNode = nextNode.next;
    }

    if (currNode === null) {
      console.log(`key value not found`);
      return;
    }

    currNode.next = new _Node(item, nextNode);
  }

• GetLast : este método devuelve el último nodo de la lista vinculada.

 getLast() {
    let lastNode = this.head;
    if (lastNode) {
        while (lastNode.next) {
            lastNode = lastNode.next
        }
    }
    return lastNode
}

• GetFirst : este método devuelve el primer nodo de la lista vinculada.

 getFirst() {
    return this.head;
}

• FindPrevious : este método devuelve el nodo anterior antes del elemento que busca en la lista vinculada.

  findPrevious: (linkedList, key) => {

    if (linkedList.head === null) {
      return null;
    }
    let prevNode;
    let currNode = linkedList.head;

    while (currNode.data !== key) {
      prevNode = currNode;
      currNode = currNode.next;
    }

    return `The previous node is ${prevNode.data}`;
  }

Descripción general de los ejercicios

En estos ejercicios, practicará la creación de una lista vinculada, implementando su núcleo y algunas operaciones complementarias. También usará su lista vinculada para resolver preguntas de entrevistas. No olvide evaluar la gran O para cada uno de estos ejercicios. Inicie cada problema indicando 1 o más entradas y salidas de muestra.

1. Cree una clase de lista vinculada

Escriba una clase de lista vinculada y estas funciones centrales (InsertFirst, InsertLast, Eliminar, buscar) desde cero.

2. Cree una lista vinculada individualmente

• Escribe una función principal. Dentro de la función, utilizando la clase de lista vinculada anterior, cree una lista vinculada con el nombre SLL y agregue los siguientes elementos a su lista vinculada: Apollo, Boomer, Helo, Husker, Starbuck.
• Agregue tauhida a la lista.
• Retire la ardilla de la lista.
• Implemente una función llamada InsertBore () en la clase que inserta un nuevo nodo antes de que un nodo dado que contenga una clave.
• Implemente una función llamada InsertAfter () en la clase que inserta un nuevo nodo después de un nodo que contiene la clave.
• Implemente una función llamada InsertAt () que inserta un elemento en una posición específica en la lista vinculada.
• Agregue Athena antes de Boomer usando su función InsertBore ().
• Agregue HotDog después de Helo usando el método InsertAfter ().
• Usando el método Insertat () Insertar kat en la tercera posición de la lista.
• Eliminar tauhida de la lista.

3. Funciones complementarias para una lista vinculada

Implemente las siguientes funciones que operan en su clase de lista vinculada. Tenga en cuenta que estas deberían ser funciones gratuitas en lugar de los métodos de la clase de lista vinculada, por lo que impleméntelos fuera de la clase de lista vinculada. Pruebe cada función utilizando la lista creada en el Ejercicio 1.

• Pantalla: muestra la lista vinculada
• Tamaño: Devuelve el tamaño de la lista vinculada
• isEmpty: encuentra si la lista está vacía o no (sin usar la función size ())
• findprevious: encuentra el nodo antes del elemento que está buscando
• FindLast: Devuelve el último nodo en la lista vinculada

4. Programa de misterio

Analice la siguiente función (sin ejecutarla en un IDE) para determinar qué problema está tratando de resolver. ¿Cuál es la complejidad del tiempo de este algoritmo?

 function WhatDoesThisProgramDo(lst) {
    let current = lst.head;
    while (current !== null) {
        let newNode = current;
        while (newNode.next !== null) {
            if (newNode.next.value === current.value) {
                newNode.next = newNode.next.next;
            }
            else {
                newNode = newNode.next;
            }
        }
        current = current.next;
    }
}

5. Invertir una lista

Escriba un algoritmo para revertir una lista vinculada. La complejidad del tiempo de su algoritmo debe ser lineal (o (n)). Para este ejercicio, observe que no le pedimos que solo imprima la lista vinculada en reversa o use otra lista vinculada para almacenar el valor en orden inverso. Su programa debe revertir la dirección de una lista vinculada individual determinada. En otras palabras, todos los punteros deben señalar hacia atrás. Bonificación: resuelva este problema usando algoritmos recursivos e iterativos.

6. 3er desde el final

Escriba un algoritmo para encontrar el tercer elemento desde el final de una lista vinculada. Nota Puede que tenga la tentación de agregar una propiedad de longitud a su clase de lista vinculada. La propiedad de longitud no es una propiedad típica de la lista vinculada, por lo tanto, no realice ninguna modificación en la clase de lista vinculada que se le proporcione.

7. Medio de una lista

Escriba un algoritmo para encontrar el elemento medio de una lista vinculada. Nota Puede que tenga la tentación de agregar una propiedad de longitud a su clase de lista vinculada. La propiedad de longitud no es una propiedad típica de la lista vinculada, por lo tanto, no realice ninguna modificación en la clase de lista vinculada que se le proporcione. Además, encontrar el tamaño de la lista vinculada utilizando la función size () y dividirla a la mitad no encontrará el medio correcto de la lista vinculada. Entonces, no use ninguno de estos enfoques.

8. Ciclo en una lista

Escriba un algoritmo para encontrar si una lista vinculada tiene un ciclo (es decir, si un nodo en la lista tiene su siguiente valor apuntando a un nodo anterior en la lista). Para este ejercicio, cree una lista vinculada con el nombre Cyclelist. Asegúrese de insertar nodos en la lista para que tenga un ciclo. Luego pruebe su programa con una función de ciclista.

9. Lista doblemente vinculada

Implementar una lista doblemente vinculada. Las funciones principales de la lista doblemente vinculada se insertarían (primero, por último, antes, después y en), eliminar y encontrar. Escriba una función maindll, y dentro de ella crea la lista doblemente vinculada DLL y agregue los siguientes elementos: Acuaria, Caprica, Gemenon, Picon, Sagitaron.

• Agregar Tauron a la lista
• Eliminar Picon de la lista

10. Invertir una dll

Dada la lista doblemente vinculada anterior, escriba un programa que revierta la lista doblemente vinculada. ¿En qué se diferencia esta implementación de revertir la lista vinculada individualmente?