Implementando listas vinculadas em JavaScript

Uma lista encadeada é uma estrutura de dados muito semelhante a um array, exceto pelo fato de que os dados não são armazenados em um único local de memória. Em JavaScript, cada elemento (nó) de uma lista encadeada é um objeto que aponta para o próximo elemento (nó) que também aponta para o próximo elemento da lista encadeada, até que o último elemento aponte para nada (fim da lista encadeada) .

O ponto de entrada para uma lista encadeada é chamado de cabeça. A cabeça é uma referência ao primeiro nó na lista encadeada. O último nó da lista aponta para nulo. Se uma lista estiver vazia, o cabeçalho é uma referência nula.

Em termos pictóricos, suas melhores listas vinculadas de visualização são as seguintes;

Isso também pode ser visto como;

// Skeletal View of a Linked List

const list = {
  head: {
    data: 12,
    next: {
      data: 99,
      next: {
        data: 37,
        next: null
      }
    }
  }
}

//  Joshua Ajagbe

1. Music Player — As músicas no music player são vinculadas às músicas anteriores e posteriores. Assim, você pode reproduzir músicas do início ou do fim da lista.
2. Visualizador de imagens — As imagens anteriores e posteriores são vinculadas e podem ser acessadas pelos botões seguinte e anterior.
3. Página anterior e seguinte em um navegador da web — Podemos acessar o URL anterior e seguinte pesquisado em um navegador da web pressionando os botões voltar e próximo, pois eles estão vinculados como uma lista vinculada.

Existem três tipos principais de listas encadeadas, que são lista encadeada simples, lista encadeada duplamente e lista encadeada circular. Para o propósito deste aprendizado, iremos implementar a Lista Encadeada Simples.

Conforme declarado anteriormente, uma lista encadeada é simplesmente uma combinação de elementos (nós) que apontam uns para os outros. A unidade básica de uma lista encadeada é um nó. Um nó abriga os dados e o ponteiro para o próximo nó, implementado da seguinte forma;

// A Singly Linked List Node
function SinglyLinkedListNode(data) {
  this.data = data;
  this.next = null; // the pointer to the next node...
}

//  Joshua Ajagbe

function SinglyLinkedList() {
  this.head = null;
  this.size = 0; // this helps keep track of the size of the linked list.
}

SinglyLinkedList.prototype.insert = function (data) {
  // checking if linked list is empty
  if(this.head === null){
    this.head = new SinglyLinkedListNode(data);
  } else {
    let temp = this.head;
    this.head = new SinglyLinkedListNode(data);
    this.head.next = temp;
  }
  this.size++; // updating the linked list size.
}

// Let's add method to check if the linked list is empty here. Bonus 
SinglyLinkedList.prototype.isEmpty = function () {
  return this.size === 0;
}

//  Joshua Ajagbe

A remoção de um nó de uma lista vinculada é implementada removendo seu ponteiro. Isso significa que o nó anterior apontando para o nó (a ser removido) seria feito para pular o nó (a ser removido), portanto, apontando para o próximo nó.

SinglyLinkedList.prototype.remove = function (data) {
  let currentHead = this.head;
  if(currentHead.data === data) {
    this.head = currentHead.next;
    this.size--;
  } else {
    let prev = currentHead;
    while(currentHead.next) {
      if(currentHead.data === data){
        prev.next = currentHead.next;
        prev = currentHead;
        currentHead = currentHead.next
        this.size--;
        break;
      }
      prev = currentHead;
      currentHead = currentHead.next;
    }
  }
}


//  Joshua Ajagbe

Espero que isso tenha ajudado você a entender a lista vinculada e sua implementação.

Apenas no caso de você querer alguma explicação adicional, você pode entrar em contato comigo no LinkedIn:https://www.linkedin.com/in/joshua-ajagbe/ou envie-me um e-mail para [email protected].

Bons aprendizados