A informação está ao nosso redor.

No mundo do software, as maneiras que escolhemos para organizar nossas informações são metade da batalha. Mas o problema é o seguinte: existem muitas maneiras de resolver um problema. E quando se trata de organizar nossos dados, existem muitas ferramentas que podem funcionar para o trabalho. O truque é saber qual ferramenta é a certa para usar.

Independentemente da linguagem em que começamos a codificar, uma das primeiras coisas que encontramos são as estruturas de dados , que são as diferentes maneiras como podemos organizar nossos dados; variáveis , matrizes , hashes e objetos são todos tipos de estruturas de dados. Mas isso ainda é apenas a ponta do iceberg quando se trata de estruturas de dados; há muito mais, alguns dos quais começam a soar super complicados quanto mais você ouve sobre eles.

Uma daquelas coisas complicadas para mim sempre foram as listas vinculadas . Conheço as listas vinculadas há alguns anos, mas nunca consigo mantê-las bem fixas na minha cabeça. Só penso realmente neles quando estou me preparando para (ou às vezes, no meio) uma entrevista técnica e alguém me pergunta sobre eles. Vou fazer uma pequena pesquisa e acho que entendo do que se trata, mas depois de algumas semanas, eu os esqueço de novo. A coisa toda é bastante ineficiente e tudo decorre do fato de que eu sei que eles existem, mas fundamentalmente não os entendo ! Então, é hora de mudar isso e responder à pergunta: o que diabos é uma lista encadeada, afinal?

Estruturas de dados lineares

Se realmente quisermos entender os fundamentos das listas vinculadas, é importante que falemos sobre que tipo de estrutura de dados elas são.

Uma característica das listas vinculadas é que são estruturas de dados lineares , o que significa que há uma sequência e uma ordem de como são construídas e percorridas. Podemos pensar em uma estrutura de dados linear como um jogo de amarelinha : para chegar ao final da lista, temos que percorrer todos os itens da lista em ordem ou sequencialmente . Estruturas lineares, no entanto, são o oposto de estruturas não lineares. Em estruturas de dados não lineares , os itens não precisam ser organizados em ordem, o que significa que poderíamos atravessar a estrutura de dados não sequencialmente .

Nem sempre percebemos, mas todos nós trabalhamos com estruturas de dados lineares e não lineares todos os dias! Quando organizamos nossos dados em hashes (às vezes chamados de dicionários ), estamos implementando uma estrutura de dados não linear. Árvores e gráficos também são estruturas de dados não lineares que percorremos de maneiras diferentes, mas falaremos mais sobre eles com mais detalhes no final do ano.

Da mesma forma, quando usamos arrays em nosso código, estamos implementando uma estrutura de dados linear! Pode ser útil pensar em matrizes e listas vinculadas como semelhantes na maneira como sequenciamos os dados. Em ambas as estruturas, a ordem é importante . Mas o que torna os arrays e as listas vinculadas diferentes?

Gerenciamento de memória

O maior diferenciador entre arrays e listas vinculadas é a maneira como eles usam a memória em nossas máquinas. Aqueles de nós que trabalham com linguagens tipadas dinamicamente como Ruby, JavaScript ou Python não precisam pensar sobre quanta memória um array usa quando escrevemos nosso código no dia a dia, porque existem várias camadas de abstração que acabam sem a necessidade de nos preocuparmos com a alocação de memória.

Mas isso não significa que a alocação de memória não esteja acontecendo! Abstração não é mágica, é apenas a simplicidade de esconder coisas que você não precisa ver ou lidar o tempo todo. Mesmo que não tenhamos que pensar sobre a alocação de memória ao escrever o código, se quisermos realmente entender o que está acontecendo em uma lista encadeada e o que a torna poderosa, temos que descer ao nível rudimentar.

Já aprendemos sobre binários e como os dados podem ser divididos em bits e bytes. Assim como caracteres, números, palavras e frases requerem bytes de memória para representá-los, o mesmo ocorre com as estruturas de dados.

Quando um array é criado, ele precisa de uma certa quantidade de memória. Se tivéssemos 7 letras que precisássemos armazenar em um array, precisaríamos de 7 bytes de memória para representar esse array. Mas, precisaríamos de toda essa memória em um bloco contíguo . Ou seja, nosso computador precisaria localizar 7 bytes de memória que estavam livres, um byte ao lado do outro, todos juntos, em um só lugar.

Por outro lado, quando uma lista encadeada nasce, ela não precisa de 7 bytes de memória em um só lugar. Um byte pode residir em algum lugar, enquanto o próximo byte pode ser armazenado em outro lugar na memória! Listas vinculadas não precisam ocupar um único bloco de memória; em vez disso, a memória que eles usam pode ser espalhada por toda parte .

A diferença fundamental entre matrizes e listas vinculadas é que matrizes são estruturas de dados estáticas , enquanto listas vinculadas são estruturas de dados dinâmicas . Uma estrutura de dados estáticos precisa que todos os seus recursos sejam alocados quando a estrutura é criada; isso significa que, mesmo que a estrutura aumente ou diminua de tamanho e os elementos sejam adicionados ou removidos, ela sempre precisa de um determinado tamanho e quantidade de memória. Se mais elementos precisassem ser adicionados a uma estrutura de dados estáticos e ela não tivesse memória suficiente, você precisaria copiar os dados desse array, por exemplo, e recriá-lo com mais memória, para que pudesse adicionar elementos ao isto.

Por outro lado, uma estrutura de dados dinâmica pode diminuir e aumentar na memória. Ele não precisa de uma quantidade definida de memória a ser alocada para existir, e seu tamanho e forma podem mudar, e a quantidade de memória de que precisa também pode mudar.

Agora, já podemos começar a ver algumas diferenças importantes entre arrays e listas vinculadas. Mas isso levanta a questão: o que permite que uma lista vinculada tenha sua memória espalhada por toda parte? Para responder a essa pergunta, precisamos examinar a maneira como uma lista vinculada é estruturada.

Partes de uma lista ligada

Uma lista vinculada pode ser pequena ou enorme, mas não importa o tamanho, as partes que a compõem são na verdade bastante simples. Uma lista vinculada é composta por uma série de nós , que são os elementos da lista.

O ponto de partida da lista é uma referência ao primeiro nó, conhecido como cabeça . Quase todas as listas vinculadas devem ter um cabeçalho, porque este é efetivamente o único ponto de entrada para a lista e todos os seus elementos e, sem ele, você não saberia por onde começar! O final da lista não é um nó, mas sim um nó que aponta para nulo ou um valor vazio.

Um único nó também é muito simples. Ele tem apenas duas partes: dados , ou as informações que o nó contém, e uma referência ao próximo nó .

Se pudermos envolver nossas cabeças em torno disso, então estamos no meio do caminho. A maneira como os nós funcionam é super importante e superpoderosa e pode ser resumida assim:

Um nó só sabe quais dados ele contém e quem é seu vizinho.

Um único nó não sabe o tamanho da lista vinculada e pode nem mesmo saber onde começa ou termina. Tudo o que um nó se preocupa são os dados que ele contém e a qual nó seu ponteiro se refere - o próximo nó na lista.

E esta é a razão pela qual uma lista vinculada não precisa de um bloco contíguo de memória. Como um único nó tem o “endereço” ou uma referência ao próximo nó, eles não precisam morar um ao lado do outro, como os elementos precisam em um array. Em vez disso, podemos apenas confiar no fato de que podemos percorrer nossa lista apoiando-nos nas referências do ponteiro para o próximo nó, o que significa que nossas máquinas não precisam bloquear um único pedaço de memória para representar nossa lista.

Essa também é a explicação de por que as listas vinculadas podem aumentar e diminuir dinamicamente durante a execução de um programa. Adicionar ou remover um nó com uma lista vinculada torna-se tão simples quanto reorganizar alguns ponteiros, em vez de copiar os elementos de um array! No entanto, também existem algumas desvantagens nas listas vinculadas que não estou mencionando a você ainda - mas mais sobre elas na próxima semana.

Por enquanto, vamos apenas nos deleitar com a glória de como as listas vinculadas são legais!

Listas para todas as formas e tamanhos

Mesmo que as partes de uma lista vinculada não mudem, a maneira como estruturamos nossas listas vinculadas pode ser bem diferente. Como a maioria das coisas em software, dependendo do problema que estamos tentando resolver, um tipo de lista vinculada pode ser uma ferramenta melhor para o trabalho do que outro.

Listas unidas individualmente são o tipo mais simples de lista vinculada, com base apenas no fato de que elas vão apenas em uma direção. Há uma única trilha na qual podemos percorrer a lista; começamos nonó principal e atravessamos da raiz até o último nó, que terminará com umvalor nulo vazio.

Mas, assim como um nó pode referenciar seu nó vizinho subsequente, ele também pode ter um ponteiro de referência para seu nó precedente! Isso é o que chamamos de lista duplamente vinculada , porque há duas referências contidas em cada nó: uma referência ao próximo nó, bem como ao nó anterior . Isso pode ser útil se quisermos atravessar nossa estrutura de dados não apenas em uma única trilha ou direção, mas também para trás.

Por exemplo, se quisermos poder saltar entre um nó e o nó anterior sem ter que voltar para o início da lista , uma lista duplamente vinculada seria uma estrutura de dados melhor do que uma lista unida individualmente. No entanto, tudo requer espaço e memória, então se nosso nó tivesse que armazenar dois ponteiros de referência em vez de apenas um, isso seria outra coisa a considerar.

Uma lista ligada circular é um pouco estranha porque não termina com um nó apontando para um valor nulo. Em vez disso, ele possui um nó que atua como o final da lista (em vez do nó principal convencional), e o nó após o nó final é o início da lista. Esta estrutura organizacional torna realmente fácil de adicionar algo para o fim da lista, porque você pode começar a atravessá-lo na cauda nó, como o primeiro elemento e último ponto elemento ao outro. Listas circulares vinculadas podem começar a ficar realmente malucas porque podemos transformar uma lista vinculada simples e uma lista duplamente vinculada em uma lista vinculada circular!

Mas não importa o quão complicada seja uma lista encadeada, se pudermos lembrar os fundamentos de um nó e como ele funciona e como as diferentes referências de ponteiro em nossa lista são estruturadas, não há lista encadeada que não possamos resolver!

Na próxima semana, na parte 2 desta série, vamos mergulhar na complexidade do espaço-tempo das listas vinculadas e como elas se comparam a sua prima, a matriz. Eu prometo que na verdade é muito mais divertido do que parece!

Recursos

Se você acha que as listas vinculadas são muito legais, verifique estes recursos úteis.

1. Diferenças entre matrizes e listas vinculadas , Damien Wintour
2. Estruturas de dados: matrizes vs listas vinculadas , mycodeschool
3. Listas vinculadas: o básico , Dr. Edward Gehringer
4. Introdução às listas vinculadas , Dr. Victor Adamchik
5. Estruturas e implementações de dados , Dra. Jennifer Welch
6. Estruturas de dados estáticas vs. estruturas de dados dinâmicas , Ayoma Gayan Wijethunga