Olá? Bem-vindo de volta a esta série sobre listas vinculadas. Em nosso último artigo, aprendemos os fundamentos das listas vinculadas, incluindo sua definição, terminologias, sua diferença com arrays e os tipos de listas vinculadas. Prometi que nos aprofundaríamos na implementação de listas vinculadas, então vamos começar.

Resumo do curso

1. Introdução
2. Implementando listas vinculadas individualmente
   • Criando novo nó
   • Inserir no início
   • Inserir no final
   • Excluir um nó
   • Pesquisar um nó
   • Percorra a lista
3. Conclusão

Introdução

Como aprendemos no artigo anterior, Linked Lists são estruturas de dados fundamentais no mundo da programação. Eles consistem em nós, onde cada nó contém dados e uma referência (ou link) para o próximo nó (em uma lista vinculada individualmente) ou para os nós seguintes e anteriores (em uma lista duplamente vinculada) na sequência. Ao contrário dos arrays, as listas vinculadas não armazenam elementos em locais de memória contíguos, permitindo inserções e exclusões eficientes.

Compreender o conceito de lista vinculada é crucial para dominar estruturas de dados e algoritmos. Neste artigo, nos aprofundaremos na implementação de listas vinculadas, começando com o básico de uma lista vinculada individualmente.

Implementando listas vinculadas individualmente

Uma lista vinculada individualmente é o tipo mais simples de lista vinculada, onde cada nó aponta para o próximo nó na sequência. Assim como na imagem abaixo.

Agora é hora de começar a implementar nossas operações básicas de lista vinculada individualmente. Devemos nós?

Criando novo nó

Vamos começar criando uma nova classe Node. A classe Node terá um construtor que coleta os dados do nó e um próximo ponteiro que é inicialmente definido como nulo.

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

Esta classe Node recém-criada (que representa um nó na lista vinculada) pode ser visualizada como abaixo.

Antes de prosseguirmos, vamos criar uma nova instância de nossa classe SinglyLinkedList que conterá nossas operações de lista vinculada.

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

  // Operations come here ?
}

Inserir no início

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 ?
  // .
  // .
  // .
}

Explicação: Inserir no início é como se alguém novo entrasse na linha da frente. Eles se tornam a nova primeira pessoa, vinculando-se à primeira pessoa anterior.

Inserir no 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 ?
  // .
  // .
  // .
}

Explicação: Inserir no final é como alguém entrando na linha bem no final. Precisamos caminhar até o fim para encontrar a última pessoa e, em seguida, vinculá-la à nova pessoa.

Excluir um nó

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 ?
  // .
  // .
  // .
}

Explicação: Excluir um nó é como alguém no meio da fila decidindo sair. Encontramos essa pessoa e conectamos aquela que está antes dela com aquela que vem depois dela.

Procure um nó

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 ?
  // .
  // .
  // .
}

Explicação: Procurar um nó é como tentar encontrar uma pessoa específica na fila. Começamos pela frente e perguntamos a cada pessoa até encontrá-la ou chegar ao fim.

Percorra a 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

Explicação: Atravessar é como caminhar pela linha e cumprimentar cada pessoa. Começamos na frente e seguimos em frente até chegar ao fim.

Conclusão

Neste artigo, aprendemos sobre as operações básicas de listas vinculadas e como implementá-las em JavaScript. No próximo artigo, aprenderemos sobre listas duplamente vinculadas.

Lembre-se de que dominar listas vinculadas requer prática. Continue resolvendo problemas e implementando essas estruturas de dados em vários cenários.

Fique atualizado e conectado

Para garantir que você não perca nenhuma parte desta série e se conectar comigo para discussões mais aprofundadas sobre desenvolvimento de software (Web, servidor, móvel ou scraping/automação), estruturas de dados e algoritmos e outras tecnologias interessantes tópicos, siga-me em:

• GitHub
• Linkedin
• X (Twitter)

Fique ligado e boa programação ?‍??