Hola ?, bienvenido de nuevo a esta serie sobre listas enlazadas. En nuestro último artículo, aprendimos los conceptos básicos de las listas vinculadas, incluida su definición, terminología, su diferencia con las matrices y los tipos de listas vinculadas. Prometí que profundizaríamos en la implementación de listas vinculadas, así que comencemos.

Esquema del curso

1. Introducción
2. Implementación de listas enlazadas individualmente
   • Creando nuevo nodo
   • Insertar al principio
   • Insertar al final
   • Eliminar un nodo
   • Buscar un nodo
   • Recorrer la lista
3. Conclusión

Introducción

Como hemos aprendido en el artículo anterior, las Listas Enlazadas son estructuras de datos fundamentales en el mundo de la programación. Consisten en nodos, donde cada nodo contiene datos y una referencia (o enlace) al siguiente nodo (en una lista simplemente enlazada) o al nodo siguiente y anterior (en una lista doblemente enlazada) de la secuencia. A diferencia de las matrices, las listas vinculadas no almacenan elementos en ubicaciones de memoria contiguas, lo que permite inserciones y eliminaciones eficientes.

Comprender el concepto de lista enlazada es crucial para dominar las estructuras de datos y los algoritmos. En este artículo, profundizaremos en la implementación de listas enlazadas, comenzando con los conceptos básicos de una lista enlazada individualmente.

Implementación de listas enlazadas individualmente

Una lista enlazada individualmente es el tipo más simple de lista enlazada, donde cada nodo apunta al siguiente nodo de la secuencia. Como en la imagen de abajo.

Ahora es el momento de comenzar a implementar nuestras operaciones básicas de listas enlazadas individualmente. ¿Debemos?

Creando nuevo nodo

Comencemos creando una nueva clase de Nodo. La clase Nodo tendrá un constructor que toma los datos del nodo y un puntero siguiente que inicialmente se establece en nulo.

// Node class for Singly Linked List
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Esta clase de nodo recién creada (que representa un nodo en la lista vinculada) se puede visualizar como se muestra a continuación.

Antes de continuar, creemos una nueva instancia de nuestra clase SinglyLinkedList que contendrá nuestras operaciones de lista vinculada.

// Singly Linked List class
class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Operations come here ?
}

Insertar al principio

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the beginning
  insertAtBeginning(data) {
    const newNode = new Node(data); // Create a new node with the given data
    newNode.next = this.head; // Set the new node's next pointer to the current head
    this.head = newNode; // Update the head to be the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Explicación: Insertar al principio es como si alguien nuevo se uniera a la línea al principio. Se convierten en la nueva primera persona, vinculándose con la primera persona anterior.

Insertar al final

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  // Insert at the end
  insertAtEnd(data) {
    const newNode = new Node(data); // Create a new node with the given data

    // check if the list does not have a head i.e the list is empty
    // NOTE: Every non-empty linked list will have a head
    if (!this.head) {
      this.head = newNode; // If the list is empty, set the new node as the head
      return;
    }
    let current = this.head; // Start at the head of the list
    while (current.next) {
      current = current.next; // Move to the next node in the list by updating the current node
    }
    current.next = newNode; // Set the next pointer of the last node to the new node
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Explicación: Insertar al final es como si alguien se uniera a la línea al final. Necesitamos caminar hasta el final para encontrar a la última persona y luego vincularla con la nueva persona.

Eliminar un nodo

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Delete a node
  deleteNode(data) {
    if (!this.head) return; // If the list is empty, do nothing
    if (this.head.data === data) {
      this.head = this.head.next; // If the node to delete is the head, update the head to the next node
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next; // If the node to delete is found, update the next pointer to skip it
        return;
      }
      current = current.next;
    }
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Explicación: Eliminar un nodo es como si alguien en medio de la fila decidiera irse. Encontramos a esa persona y conectamos a la que está delante con la que está detrás.

Buscar un nodo

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }

  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .

  // Search note
  search(data) {
    let current = this.head; // Start at the head of the list
    while (current) {
      if (current.data === data) {
        // If the data is found, return true
        return true;
      }
      current = current.next; // Move to the next node
    }
    return false;
  }

  // Other operations come here ?
  // .
  // .
  // .
}

Explicación: Buscar un nodo es como intentar encontrar una persona específica en la línea. Empezamos por el frente y preguntamos a cada persona hasta encontrarlos o llegar al final.

Recorrer la lista

class SinglyLinkedList {
  constructor() {
    this.head = null;
  }
  // Previous `SinglyLinkedList` class codes here ?
  // .
  // .
  // .
  traverse() {
    let current = this.head; // Start at the head of the list
    while (current) {
      console.log(current.data); // Print the data of the current node
      current = current.next; // Move to the next node
    }
  }
}

// End of class

Explicación: Atravesar es como caminar por la línea y saludar a cada persona. Empezamos por delante y seguimos avanzando hasta llegar al final.

Conclusión

En este artículo, aprendimos sobre las operaciones básicas de las listas vinculadas y cómo implementarlas en JavaScript. En el próximo artículo, aprenderemos sobre las listas doblemente enlazadas.

Recuerde, dominar las listas enlazadas requiere práctica. Continúe resolviendo problemas e implementando estas estructuras de datos en varios escenarios.

Manténgase actualizado y conectado

Para garantizar que no se pierda ninguna parte de esta serie y conectarse conmigo para discusiones más profundas sobre desarrollo de software (web, servidor, móvil o scraping/automatización), estructuras de datos y algoritmos, y otras tecnologías interesantes. temas, sígueme en:

• GitHub
• Linkedin
• X (Twitter)

Estén atentos y felices codificando ?‍??