Lista Ligada Simples e Lista Ligada Duplamente

Duas das estruturas de dados mais comumente ensinadas em ciência da computação são a lista encadeada simples e a lista encadeada dupla.

Quando me ensinaram essas estruturas de dados, pedi aos meus colegas analogias para conceituá-las. O que ouvi foram vários exemplos, como uma lista de mantimentos e um trem. Essas analogias, como acabei descobrindo, eram imprecisas. Uma lista de compras era mais análoga a uma fila; um trem era mais análogo a uma matriz.

Com o passar do tempo, acabei descobrindo uma analogia que descrevia com precisão uma lista ligada simples e uma lista duplamente ligada: uma caça ao tesouro. Se você está curioso sobre a relação entre uma caça ao tesouro e uma lista vinculada, leia abaixo a resposta!

Uma lista de links simples

Na ciência da computação, uma lista vinculada simples é uma estrutura de dados que contém uma sequência de nós vinculados. Cada nó, por sua vez, contém dados e um ponteiro, que pode apontar para outro nó.

Os nós de uma lista vinculada simples são muito semelhantes às etapas de uma caça ao tesouro. Cada etapa contém uma mensagem (por exemplo, “Você chegou à França”) e ponteiros para a próxima etapa (por exemplo, “Visite estas coordenadas de latitude e longitude”). Quando começamos a sequenciar essas etapas individuais para formar uma sequência de etapas, estamos criando uma caça ao tesouro.

Agora que temos um modelo conceitual de uma lista encadeada simples, vamos explorar as operações de uma lista encadeada simples.

Operações de uma lista vinculada simples

Uma vez que uma lista de ligação simples contém nós, que podem ser um construtor separado de uma lista de ligação simples, descrevemos as operações de ambos os construtores: Node e SinglyList .

Node

• data armazena um valor
• next aponta para o próximo nó na lista

SinglyList

• _length recupera o número de nós em uma lista
• head atribui um nó como o cabeça de uma lista
• add(value) adiciona um nó a uma lista
• searchNodeAt(position) procura um nó na posição n em nossa lista
• remove(position) remove um nó de uma lista

Implementação de uma Lista Ligada Simples

Para nossa implementação, primeiro definiremos um construtor chamado Node e, em seguida, um construtor chamado SinglyList .

Cada instância de Node precisa da capacidade de armazenar dados e da capacidade de apontar para outro nó. Para adicionar essa funcionalidade, criaremos duas propriedades: data e nextrespectivamente.

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

A seguir, precisamos definir SinglyList:

class SinglyList {
  constructor() {
    this._length = 0;
    this.head = null;
  }
}

Cada instância de SinglyList terá duas propriedades: _length e head. Ao primeiro é atribuído o número de nós em uma lista; o último aponta para o início da lista – o nó na frente da lista. Uma vez que cada nova instância de SinglyList não contém um nó, o valor padrão de head é null e o valor padrão de _length é 0 .

Métodos de uma Lista Ligada Simples

Precisamos definir métodos que possam adicionar, pesquisar e remover um nó de uma lista.

Adicionando dados a uma lista com add(value)

Vamos começar adicionando nós a uma lista.

//  add value to singly-linked list
add(value) {
  let node = new Node(value),
    currentNode = this.head;

  // 1st use-case: an empty list
  if (!currentNode) {
    this.head = node;
    this._length++;

    return node;
  }

  // 2nd use-case: a non-empty list
  while (currentNode.next) {
    currentNode = currentNode.next;
  }

  currentNode.next = node;
  this._length++;

  return node;
}

Adicionar um nó à nossa lista envolve muitas etapas. Vamos começar do início do nosso método. Usamos o argumento de add(value) para criar uma nova instância de um Nodeque é atribuído a uma variável chamada node. Também declaramos uma variável chamada currentNode e inicialize-o no head da nossa lista. Se não houver nós na lista, então o valor de head é null.

Após este ponto em nosso código, lidamos com dois casos de uso.

O primeiro caso de uso considera adicionar um nó a uma lista vazia. Se head não aponta para um nó, então atribui node como o cabeçalho de nossa lista, incremente o comprimento de nossa lista em um e retorne node.

O segundo caso de uso considera adicionar um nó a uma lista não vazia. Entramos no while loop, e durante cada iteração, avaliamos se currentNode.next aponta para outro nó. (Durante a primeira iteração, currentNode está sempre apontando para o início de uma lista.)

Se a resposta for não, atribuímos node para currentNode.next e retorno node.

Se a resposta for sim, entramos no corpo do while ciclo. Dentro do corpo, nós reatribuímos currentNode para currentNode.next. Este processo é repetido até que currentNode.next não aponta mais para outro nó. Em outras palavras, currentNode aponta para o último nó da nossa lista.

o while quebras de loop. Por fim, atribuímos node para currentNode.next incrementamos _length por um, e depois voltamos node.

Encontrar um item com searchNodeAt(position)

Agora podemos adicionar nós à nossa lista, mas não podemos procurar nós em posições específicas em nossa lista. Vamos adicionar esta funcionalidade e criar um método chamado searchNodeAt(position) que aceita um argumento chamado position . Espera-se que o argumento seja um inteiro que indique um nó na posição n em nossa lista.

//search an element at a specific position
function searchNodeAt(position) {
  let currentNode = this.head,
    length = this._length,
    count = 1,
    message = { failure: 'Failure: non-existent node in this list.' };

  //  1st use-case: an invalid position
  if (length === 0 || position < 1 || position > length) {
    throw new Error(message.failure);
  }

  // 2nd use-case: a valid position
  while (count < position) {
    currentNode = currentNode.next;
    count++;
  }

  return currentNode;
}

o if A instrução verifica o primeiro caso de uso: uma posição inválida é passada como argumento.

Se o índice passou para searchNodeAt(position) é válido, então chegamos ao segundo caso de uso - o while ciclo. Durante cada iteração do while ciclo, currentNode— que primeiro aponta para head— é reatribuído ao próximo nó na lista. Essa iteração continua até que a contagem seja igual à posição.

Quando o loop finalmente se rompe, currentNode é devolvido.

Remover um item com remove(position)

O método final que vamos criar se chama remove(position) .

//remove a node at a specific position
function removeAt(position) {
  let currentNode = this.head,
    length = this._length,
    count = 0,
    message = { failure: 'Failure: non-existent node in this list.' },
    beforeNodeToDelete = null,
    nodeToDelete = null,
    deletedNode = null;

  //  1st use-case: an invalid position
  if (length === 0 || position < 1 || position > length) {
    throw new Error(message.failure);
  }

  // 2nd use-case: the first node is removed
  if (position === 1) {
    this.head = currentNode.next;
    deletedNode = currentNode;
    currentNode = null;
    this._length--;

    return deletedNode;
  }

  // 3rd use-case: any other node is removed
  while (count < position) {
    beforeNodeToDelete = currentNode;
    nodeToDelete = currentNode.next;
    count++;
  }

  beforeNodeToDelete.next = nodeToDelete.next;
  deletedNode = nodeToDelete;
  nodeToDelete = null;
  this._length--;

  return deletedNode;
}

Nossa implementação de remove(position) envolve três casos de uso:

1. uma posição inválida é passada como um argumento
2. uma posição de um (head de uma lista) é passado como um argumento
3. uma posição existente (não a primeira posição) é passada como um argumento

O primeiro e o segundo casos de uso são os mais simples de manusear. Em relação ao primeiro cenário, se a lista estiver vazia ou for passada uma posição inexistente, um erro será lançado.

O segundo caso de uso trata da remoção do primeiro nó da lista, que também é head. Se for esse o caso, ocorre a seguinte lógica:

1. head é reatribuído a currentNode.next
2. deletedNode aponta para currentNode
3. currentNode é reatribuído a null
4. diminuir _length da nossa lista por um
5. deletedNode é devolvido

O terceiro cenário é o mais difícil de entender. A complexidade decorre da necessidade de rastrear dois nós durante cada iteração de um while ciclo. Durante cada iteração do nosso loop, rastreamos o nó antes do nó a ser excluído e o nó a ser excluído. Quando nosso loop finalmente atinge o nó na posição que queremos remover, o loop termina.

Neste ponto, mantemos referências a três nós: beforeNodeToDelete , nodeToDelete e deletedNode . Antes de excluir nodeToDelete devemos atribuir seu valor de next para o próximo valor de beforeNodeToDelete . Se o objetivo desta etapa não estiver claro, lembre-se de que temos uma lista de nós vinculados; apenas remover um nó quebra o link do primeiro nó da lista para o último nó da lista.

A seguir, atribuímos deletedNode para nodeToDelete . Em seguida, definimos o valor de nodeToDelete para null decrementar o comprimento da lista em um e retornar deletedNode .

De Individualmente a Duplamente

Incrível, nossa implementação de uma lista de links simples está completa. Agora podemos usar uma estrutura de dados que adiciona, remove e pesquisa nós em uma lista que ocupa espaço não contíguo na memória.

No entanto, neste momento, todas as nossas operações começam do início de uma lista e vão até o final de uma lista. Em outras palavras, eles são unidirecionais.

Pode haver casos em que queremos que nossas operações sejam bidirecionais. Se você considerou esse caso de uso, acabou de descrever uma lista duplamente vinculada.

Uma lista duplamente ligada

Uma lista duplamente encadeada pega toda a funcionalidade de uma lista encadeada simples e a estende para movimento bidirecional em uma lista. Podemos percorrer, em outras palavras, uma lista encadeada do primeiro nó da lista até o último nó da lista; e podemos percorrer do último nó da lista até o primeiro nó da lista.

Nesta seção, manteremos nosso foco principalmente nas diferenças entre uma lista duplamente vinculada e uma lista vinculada simples.

Operações de uma lista duplamente ligada

Nossa lista incluirá dois construtores: Node e DoublyList . Vamos descrever suas operações.

Node

• data armazena um valor
• next aponta para o próximo nó na lista
• previous aponta para o nó anterior na lista

DoublyList

• _length recupera o número de nós em uma lista
• head atribui um nó como o cabeça de uma lista
• tail atribui um nó como a cauda de uma lista
• add(value) adiciona um nó a uma lista
• searchNodeAt(position) procura um nó na posição n em nossa lista
• remove(position) remove um nó de uma lista

Implementação de uma lista duplamente ligada

Vamos escrever algum código!

Para nossa implementação, criaremos um construtor chamado Node :

class Node {
  constructor(value) {
    this.data = value;
    this.previous = null;
    this.next = null;
  }
}

Para criar o movimento bidirecional de uma lista duplamente ligada, precisamos de propriedades que apontem em ambas as direções de uma lista. Essas propriedades foram nomeadas previous e next .

Em seguida, precisamos implementar um DoublyList e adicione três propriedades: _length , head e tail . Ao contrário de uma lista encadeada simples, uma lista encadeada dupla tem uma referência tanto ao início de uma lista quanto ao final de uma lista. Uma vez que cada instância de um DoublyList é instanciado sem nós, os valores padrão de head e tail estão definidos para null .

class DoublyList {
  constructor() {
    this._length = 0;
    this.head = null;
    this.tail = null;
  }
}

Métodos de uma lista duplamente ligada

Vamos agora explorar os seguintes métodos: add(value) , remove(position) e searchNodeAt(position) . Todos esses métodos foram usados ​​para uma lista encadeada; no entanto, eles devem ser reescritos para movimento bidirecional.

Adicione um valor com add(value)

// add value to doubly-linked list
add(value) {
  let node = new Node(value);

  if (this._length) {
    this.tail.next = node;
    node.previous = this.tail;
    this.tail = node;
  } else {
    this.head = node;
    this.tail = node;
  }

  this._length++;

  return node;
}

Neste método, temos dois cenários. Primeiro, se uma lista estiver vazia, atribua à sua head e tail o nó que está sendo adicionado. Segundo, se a lista contiver nós, encontre o final da lista e atribua a tail.next o nó que está sendo adicionado; da mesma forma, precisamos configurar a nova cauda para movimento bidirecional. Precisamos definir, em outras palavras, tail.previous para a cauda original.

Procurar um nó com searchNodeAt(position)

A implementação de searchNodeAt(position) é idêntico a uma lista encadeada simples. Se você esqueceu como implementá-lo, eu o incluí abaixo:

// Method to Search an Element at a Specific Position
searchNodeAt(position) {
  let currentNode = this.head,
    length = this._length,
    count = 1,
    message = { failure: 'Failure: non-existent node in this list.' };

  //  1st use-case: an invalid position
  if (length === 0 || position < 1 || position > length) {
    throw new Error(message.failure);
  }

  // 2nd use-case: a valid position
  while (count < position) {
    currentNode = currentNode.next;
    count++;
  }

  return currentNode;
}

Remover um item com remove(position)

Este método será o mais difícil de entender. Vou exibir o código e depois explicá-lo.

// Method to Remove a Node at a Specific Position
remove(position) {
  let currentNode = this.head,
    length = this._length,
    count = 1,
    message = {
      failure: 'Failure: non-existent node in this list.',
      success: 'Success: node removed.',
    },
    beforeNodeToDelete = null,
    afterNodeToDelete = null,
    nodeToDelete = null,
    deletedNode = null;

  //  1st use-case: an invalid position
  if (length === 0 || position < 1 || position > length) {
    throw new Error(message.failure);
  }

  // 2nd use-case: the first node is removed
  if (position === 1) {
    this.head = currentNode.next;

    // 2nd use-case: there is a second node
    if (!this.head) {
      this.head.previous = null;
    }
    // 2nd use-case: there is no second node
    else {
      this.tail = null;
    }
  }
  // 3rd use-case: the last node is removed
  else if (position === length) {
    this.tail = this.tail.previous;
    this.tail.next = null;
  }
  // 4th use-case: a middle node is removed
  else {
    while (count < position) {
      currentNode = currentNode.next;
      count++;
    }

    beforeNodeToDelete = currentNode.previous;
    nodeToDelete = currentNode;
    afterNodeToDelete = currentNode.next;

    beforeNodeToDelete.next = afterNodeToDelete;
    afterNodeToDelete.previous = beforeNodeToDelete;
    deletedNode = nodeToDelete;
    nodeToDelete = null;
  }

  this._length--;

  return message.success;
}

remove(position) lida com quatro casos de uso:

1. A posição sendo passada como um argumento de remove(position) é inexistente. Nesse caso, lançamos um erro.
2. A posição sendo passada como um argumento de remove(position) é o primeiro nó (head) de uma lista. Se for esse o caso, vamos atribuir deletedNode para head e depois reatribuir head para o próximo nó da lista. Neste momento, devemos considerar se nossa lista possui mais de um nó. Se a resposta for não, head será atribuído a null e vamos entrar no if parte do nosso if-else declaração. No corpo de if devemos também definir tail para null— em outras palavras, voltamos ao estado original de uma lista duplamente encadeada vazia. Se estivermos removendo o primeiro nó de uma lista e tivermos mais de um nó em nossa lista, inserimos o else seção do nosso if-else declaração. Neste caso, devemos definir corretamente o previous propriedade de head para null— não há nós antes do cabeçalho de uma lista.
3. A posição sendo passada como um argumento de remove(position) é a cauda de uma lista. Primeiro, deletedNode é atribuído a tail . Segundo, tail é reatribuído ao nó anterior à cauda. Terceiro, a nova cauda não tem nó depois dela e precisa de seu valor de next para ser definido null .
4. Muita coisa está acontecendo aqui, então vou focar na lógica mais do que em cada linha do código. Nós quebramos nosso while loop uma vez currentNode está apontando para o nó na posição que está sendo passada como um argumento para remove(position) . Neste momento, reatribuímos o valor de beforeNodeToDelete.next para o nó depois nodeToDelete e, inversamente, reatribuímos o valor de afterNodeToDelete.previous para o nó antes nodeToDelete . Em outras palavras, removemos ponteiros para o nó removido e os reatribuímos aos nós corretos. A seguir, atribuímos deletedNode para nodeToDelete . Por fim, atribuímos nodeToDelete para null .

Por fim, decrementamos o comprimento de nossa lista e retornamos deletedNode .

Conclusão

Nós cobrimos muitas informações neste artigo. Se algo parecer confuso, leia-o novamente e experimente o código. Quando eventualmente fizer sentido para você, sinta-se orgulhoso. Você acabou de descobrir os mistérios tanto de uma lista ligada simples quanto de uma lista duplamente ligada. Você pode adicionar essas estruturas de dados ao seu cinto de ferramentas de codificação!