Cómo implementar la estructura de datos de la lista enlazada en JavaScript

Cómo implementar la estructura de datos de la lista enlazada en JavaScript

En este tutorial, aprenderemos qué es una lista vinculada y cómo implementar una lista vinculada individualmente en JavaScript.

Índice
  1. ¿Qué es una lista enlazada?
    1. Lista enlazada individualmente
    2. Implementación de algoritmos
    3. método de empuje
    4. metodo pop
    5. obtener método
    6. Pruebas de listas enlazadas simples

¿Qué es una lista enlazada?

La lista enlazada es una colección lineal de datos donde cada nodo tiene una conexión con el siguiente nodo. es una estructura de datos con un grupo de nodos en la secuencia.

Las listas vinculadas fueron desarrolladas en 1955-1956 por Allen Newell, Cliff Shaw y Herbert A. Simon de RAND Corporation como la estructura de datos principal para su lenguaje de procesamiento de información.

Lista enlazada individualmente

Una lista enlazada única es una colección de nodos donde cada nodo tiene una conexión con el siguiente nodo.



Diagrama javascript de lista enlazada única

Implementación de algoritmos

Implementemos la lista enlazada individualmente en javascript.

Usamos clases de javascript si no está familiarizado con las clases, consulte mi tutorial anterior ¿Cómo funcionan las clases en javascript?

class Node{

  constructor(data){
   this.data = data;
   this.next = null;
 }

}

Nuestro nodo tiene dos propiedades que son data Y next.

class SinglyLinkedList{

  constructor(){
    this.head = null;
    this.tail = null;
    this.length= 0;
  }

}

La clase SinglyLinkedList tiene tres propiedades

  • head: este es el primer nodo de la lista.
  • cola: último nodo de la lista.
  • longitud: ¿Cuántos nodos presentes en la lista?

implementamos nuestro primer método.

método de empuje

  • El método push toma el único argumento y lo empuja al final de la lista.
  • Cada vez que necesitamos incrementar la propiedad de longitud en 1.
class SinglyLinkedList{

  constructor(){
    this.head = null;
    this.tail = null;
    this.length= 0;
  }


  push(data){

    let node = new Node(data)

    if(!this.head){
      
      
      this.head= node;
      this.tail= node ;
    }else{
      
      this.tail.next = node;
      this.tail = node;
    }
    
    this.length++
  }

}


const list = new SinglyLinkedList();


list.push(3);
list.push(4);
list.push(5);

console.log(list);

Salir



método de envío de lista enlazada

¿Has visto en la imagen de arriba que la cola apunta hacia 5 porque empujamos 5 en el último.

metodo pop

  • El método pop nos ayuda a eliminar el último nodo de la lista enlazada
  • Si eliminamos el nodo de la lista, tenemos que disminuir la longitud del nodo

por 1.

pseudocódigo

  1. si no hay head entonces regresa null.
  2. Declarar dos variables node y deleteNode
  • nodo: inicializar con this.head.
  • deleteNode: actualmente tratamos el primer nodo como un nodo eliminado.
  1. Si hay un solo nodo, asignamos la cabeza y la cola a nulo.

    • disminuir la longitud en 1
    • devuelve eliminarNodo.
  2. while loop comienza si hay más de un nodo.

  3. disminuir la longitud en 1.

  pop(){

    if(!this.head) return null

    let node = this.head;
    let deleteNode = node;

    if(!node.next){
    
      this.head= null
      this.tail = null
    }
     
     while(node.next){
       if(!node.next.next){
        
          deleteNode=node.next;
          node.next = null;
          this.tail=node;
          break
       }
        node = node.next
     }

    this.length--
    return deleteNode
  }

obtener método

El método Get nos ayuda a obtener el nodo en el índice particular.

pseudocódigo

  1. si no hay head O index es menor que 0 o index es más alto que el length luego devuelve nulo.
  2. Declare una variable currentNode e inicialícela en this.head.
  3. si el índice es mayor que 0, se inicia el ciclo while.
  • actualizar el nodo actual.
  • disminuir el índice en 1.
  1. devuelve el nodo actual.
get(index){

    if(!this.head || index < 0 || index > this.length-1) return null

     
    let currentNode = this.head;

    while(index){
     
      currentNode = currentNode.next;
      index--;
    }
    return currentNode;
 }

Pruebas de listas enlazadas simples

Si quieres conocer otros artículos parecidos a Cómo implementar la estructura de datos de la lista enlazada en JavaScript puedes visitar la categoría Tutoriales.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Subir

Esta página web utiliza cookies para analizar de forma anónima y estadística el uso que haces de la web, mejorar los contenidos y tu experiencia de navegación. Para más información accede a la Política de Cookies . Ver mas