Back in 2009, eu me desafiei a escrever um post de blog por semana durante o ano inteiro. Eu tinha lido que a melhor maneira de ganhar mais tráfego para um blog era postar consistentemente. Um post por semana parecia ser um objetivo realista devido a todas as idéias do artigo que eu tinha, mas afinal eu estava bem aquém de 52 idéias. Cavei alguns capítulos semi-escritos que acabariam por se tornar JavaScript Profissional e encontrei muito material sobre tópicos clássicos da ciência da computação, incluindo estruturas de dados e algoritmos. Peguei esse material e o transformei em vários posts em 2009 e (e alguns poucos em 2012), e obtive muito feedback positivo sobre eles.

Agora, no décimo aniversário desses posts, decidi atualizar, republicar e expandir sobre eles usando JavaScript em 2019. Tem sido interessante ver o que mudou e o que não mudou, e espero que gostem.

O que é uma lista ligada?

Uma lista ligada é uma estrutura de dados que armazena múltiplos valores de uma forma linear. Cada valor em uma lista ligada está contido em seu próprio nó, um objeto que contém os dados juntamente com um link para o próximo nó da lista. A ligação é um ponteiro para outro objeto de nó ou null se não houver um próximo nó. Se cada nó tem apenas um ponteiro para outro nó (mais frequentemente chamado next) então a lista é considerada uma lista ligada individualmente (ou apenas lista ligada) enquanto que se cada nó tem dois links (normalmente previous e next) então é considerada uma lista duplamente ligada. Neste post, estou focando em listas ligadas individualmente.

Por que usar uma lista ligada?

O benefício principal das listas ligadas é que elas podem conter um número arbitrário de valores enquanto usam apenas a quantidade de memória necessária para esses valores. Preservar a memória era muito importante em computadores mais antigos onde a memória era escassa. Naquela época, um array em C exigia que você especificasse quantos itens o array poderia conter e o programa reservaria aquela quantidade de memória. Reservar essa memória significava que ela não poderia ser usada para o resto do programa ou qualquer outro programa em execução ao mesmo tempo, mesmo que a memória nunca estivesse cheia. Uma máquina de memória, você poderia facilmente esgotar a memória disponível usando arrays. Listas vinculadas foram criadas para contornar este problema.

As listas vinculadas também se tornaram populares quando os desenvolvedores não sabiam quantos itens um array acabaria por conter. Era muito mais fácil usar uma lista de links e adicionar valores conforme necessário do que adivinhar com precisão o número máximo de valores que um array poderia conter. Como tal, listas linkadas são frequentemente usadas como base para estruturas de dados embutidas em várias linguagens de programação.

O tipo embutido JavaScript Array não é implementado como uma lista linkada, embora seu tamanho seja dinâmico e é sempre a melhor opção para começar. Você pode fazer toda sua carreira sem precisar usar uma lista ligada em JavaScript, mas listas ligadas ainda são uma boa maneira de aprender a criar suas próprias estruturas de dados.

O desenho de uma lista ligada

A parte mais importante de uma lista ligada é a sua estrutura de nós. Cada nó deve conter alguns dados e um ponteiro para o próximo nó da lista. Aqui está uma representação simples em JavaScript:

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

Na classe LinkedListNode, a propriedade data contém o valor que o item da lista vinculada deve armazenar e a propriedade next é um ponteiro para o próximo item da lista. A propriedade next começa como null porque você ainda não conhece o próximo nó. Você pode então criar uma lista ligada usando a classe LinkedListNode assim:

// create the first nodeconst head = new LinkedListNode(12);// add a second nodehead.next = new LinkedListNode(99);// add a third nodehead.next.next = new LinkedListNode(37);

O primeiro nó de uma lista ligada é tipicamente chamado de head, então o identificador head neste exemplo representa o primeiro nó. O segundo nó é criado um atribuído a head.next para criar uma lista com dois itens. Um terceiro nó é adicionado atribuindo-o a head.next.next, que é o ponteiro next do segundo nó na lista. O ponteiro next do terceiro nó da lista permanece null. A imagem seguinte mostra a estrutura de dados resultante.

A estrutura de uma lista ligada permite atravessar todos os dados seguindo o ponteiro next em cada nó. Aqui está um exemplo simples de como atravessar uma lista ligada e imprimir cada valor para a consola:

let current = head;while (current !== null) { console.log(current.data); current = current.next;}

Este código usa a variável current como o ponteiro que se move através da lista ligada. A variável current é inicializada no cabeçalho da lista e o laço while continua até que current seja null. Dentro do loop, o valor armazenado no nó current é impresso e então o ponteiro next é seguido para o próximo nó.

As operações da lista mais ligada usam este algoritmo de atravessamento ou algo similar, então entender este algoritmo é importante para entender as listas ligadas em geral.

A classe LinkedList

Se você estivesse escrevendo uma lista ligada em C, você poderia parar neste ponto e considerar sua tarefa completa (embora você usaria uma estrutura ao invés de uma classe para representar cada nó). Entretanto, em linguagens orientadas a objetos como JavaScript, é mais usual criar uma classe para encapsular essa funcionalidade. Aqui está um exemplo simples:

const head = Symbol("head");class LinkedList { constructor() { this = null; }}

A classe LinkedList representa uma lista ligada e conterá métodos para interagir com os dados que ela contém. A única propriedade é uma propriedade símbolo chamada head que conterá um ponteiro para o primeiro nó da lista. Uma propriedade symbol é usada ao invés de uma propriedade string para deixar claro que esta propriedade não pretende ser modificada fora da classe.

Adicionar novos dados à lista

Adicionar um item a uma lista ligada requer andar na estrutura para encontrar a localização correta, criando um novo nó, e inserindo-o no lugar. O único caso especial é quando a lista está vazia, neste caso você simplesmente cria um novo nó e o atribui a head:

const head = Symbol("head");class LinkedList { constructor() { this = null; } add(data) { // create a new node const newNode = new LinkedListNode(data); //special case: no items in the list yet if (this === null) { // just set the head to the new node this = newNode; } else { // start out by looking at the first node let current = this; // follow `next` links until you reach the end while (current.next !== null) { current = current.next; } // assign the node into the `next` pointer current.next = newNode; } }}

O método add() aceita um único argumento, qualquer dado, e o adiciona ao final da lista. Se a lista estiver vazia (this é null) então você atribui this igual ao novo nó. Se a lista não estiver vazia, então você precisa atravessar a lista já existente para encontrar o último nó. A travessia acontece em um loop while que começa em this e segue os links next de cada nó até que o último nó seja encontrado. O último nó tem uma propriedade next igual a null, então é importante parar a travessia nesse ponto ao invés de quando current é null (como na seção anterior). Você pode então atribuir o novo nó a essa propriedade next para adicionar os dados na lista.

A complexidade do método add() é O(n) porque você deve atravessar a lista inteira para encontrar a localização para inserir um novo nó. Você pode reduzir essa complexidade para O(1) rastreando o final da lista (normalmente chamado de cauda) além da cabeça, permitindo que você insira imediatamente um novo nó na posição correta.

Retrieving data from the list

Linked lists don’t allow random access to its contents, but you can still get get get data in any given position by traversing the list and returning the data. Para fazer isso, você adicionará um método get() que aceita um índice baseado em zero dos dados a recuperar, assim:

class LinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } }}

O método get() verifica primeiro se index é um valor positivo, caso contrário ele retorna undefined. A variável i é usada para manter o registro da profundidade da travessia para a lista. O loop em si é a mesma travessia básica que você viu anteriormente com a condição adicionada de que o loop deve sair quando i é igual a index. Isso significa que existem duas condições sob as quais o loop pode sair:

1. current é null, o que significa que a lista é menor que index.
2. i é igual a index, o que significa que current é o nó na index posição.

Se current é null então undefined é retornado e caso contrário current.data é retornado. Esta verificação assegura que get() nunca irá lançar um erro para um index que não seja encontrado na lista (embora você possa decidir lançar um erro ao invés de retornar undefined).

A complexidade do método get() varia de O(1) ao remover o primeiro nó (não é necessário atravessar) a O(n) ao remover o último nó (é necessário atravessar a lista inteira). É difícil reduzir a complexidade porque uma busca é sempre necessária para identificar o valor correto para retornar.

Remover dados de uma lista ligada

Remover dados de uma lista ligada é um pouco complicado porque você precisa garantir que todos os ponteiros next permaneçam válidos depois que um nó for removido. Por exemplo, se você quiser remover o segundo nó de uma lista de três nós, você precisará assegurar que a propriedade next do primeiro nó agora aponta para o terceiro nó ao invés do segundo. Saltar sobre o segundo nó desta forma remove-o efetivamente da lista.

A operação de remoção é na verdade duas operações:

1. Localizar o índice especificado (o mesmo algoritmo que em get())
2. Remover o nó naquele índice

Localizar o índice especificado é o mesmo que no método get(), mas neste laço você também precisa rastrear o nó que vem antes de current porque você precisará modificar o ponteiro next do nó anterior.

Há também quatro casos especiais a considerar:

1. A lista está vazia (não é possível atravessar)
2. O índice é menor que zero
3. O índice é maior que o número de itens na lista
4. O índice é zero (removendo a cabeça)

Nos primeiros três casos, a operação de remoção não pode ser completada, pelo que faz sentido lançar um erro; o quarto caso especial requer a reescrita da propriedade this. Eis como se parece a implementação de um método remove():

class LinkedList { // other methods hidden for clarity remove(index) { // special cases: empty list or invalid `index` if ((this === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // temporary store the data from the node const data = this.data; // just replace the head with the next node in the list this = this.next; // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this; // keeps track of the node before current in the loop let previous = null; // used to track how deep into the list you are let i = 0; // same loops as in `get()` while ((current !== null) && (i < index)) { // save the value of current previous = current; // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove previous.next = current.next; // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); }}

O método remove() verifica primeiro dois casos especiais, uma lista vazia (this é null) e um index que é inferior a zero. Um erro é lançado em ambos os casos.

O próximo caso especial é quando index é 0, o que significa que você está removendo a cabeça da lista. A nova cabeça da lista deve ser o segundo nó da lista, assim você pode definir this igual a this.next. Não importa se há apenas um nó na lista porque this acabaria igual a null, o que significa que a lista está vazia após a remoção. O único senão é armazenar os dados da cabeça original em uma variável local, data, para que possam ser retornados.

Com três dos quatro casos especiais resolvidos, você pode agora proceder com uma travessia semelhante à encontrada no método get(). Como mencionado anteriormente, este laço é ligeiramente diferente na medida em que a variável previous é usada para acompanhar o nó que aparece pouco antes de current, já que essa informação é necessária para remover propulsamente um nó. Similar a get(), quando o laço sai current pode ser null, indicando que o índice não foi encontrado. Se isso acontecer então um erro é lançado, caso contrário, previous.next é ajustado para current.next, removendo efetivamente current da lista. Os dados armazenados em current são retornados como o último passo.

A complexidade do método remove() é a mesma de get() e varia de O(1) quando removendo o primeiro nó a O(n) quando removendo o último nó.

Fazendo a lista iterável

Para ser usado com o JavaScript for-of desestruturação de loop e array, coleções de dados devem ser iteráveis. As coleções JavaScript embutidas como Array e Set são iteráveis por padrão, e você pode tornar suas próprias classes iteráveis especificando um método Symbol.iterator gerador na classe. Prefiro primeiro implementar um método values() gerador (para combinar com o método encontrado nas classes de coleção embutidas) e depois ter Symbol.iterator chamado values() diretamente.

O método values() só precisa fazer uma travessia básica da lista e yield os dados que cada nó contém:

class LinkedList { // other methods hidden for clarity *values(){ let current = this; while (current !== null) { yield current.data; current = current.next; } } () { return this.values(); } }

O método values() está marcado com um asterisco (*) para indicar que é um método gerador. O método atravessa a lista, usando yield para retornar cada pedaço de dado encontrado. (Note que o método Symbol.iterator não está marcado como um gerador porque está retornando um iterador do método values() gerador.)

Usando a classe

Após completar, você pode usar a implementação da lista ligada assim:

const list = new LinkedList();list.add("red");list.add("orange");list.add("yellow"); // get the second item in the listconsole.log(list.get(1)); // "orange"// print out all itemsfor (const color of list) { console.log(color);}// remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the listconsole.log(list.get(1)); // "yellow"// convert to an arrayconst array1 = ;const array2 = ;

Esta implementação básica de uma lista ligada pode ser arredondada com uma propriedade size para contar o número de nós na lista, e outros métodos familiares como indexOf(). O código fonte completo está disponível no GitHub no meu projeto Computer Science em JavaScript.

Conclusion

Linked lists não são algo que você provavelmente usará todos os dias, mas eles são uma estrutura de dados fundamentais em ciência da computação. O conceito de usar nós que apontam um para o outro é usado em muitas outras estruturas de dados são incorporados em muitas outras linguagens de programação de nível superior. Um bom entendimento de como as listas ligadas funcionam é importante para um bom entendimento geral de como criar e usar outras estruturas de dados.

Para programação JavaScript, você está quase sempre melhor usando as classes de coleção embutidas como Array em vez de criar a sua própria. As classes de coleção incorporadas já foram otimizadas para uso em produção e são bem suportadas em ambientes de execução.