Uma lista ligada é uma estrutura de dados linear na qual cada nó está conectado ao próximo nó na sequência. Essas conexões criam uma estrutura de dados que se parece com uma cadeia de nós, onde cada nó armazena dados e uma referência para o próximo nó na lista ligada. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-singly-linked-lists-work-and-how-do-they-differ-from-doubly-linked-list-1.png" alt="linked list basic structure visualization"> Usamos essas referências para ir do primeiro nó para o próximo nó e assim por diante. Listas encadeadas são comumente usadas para implementar outras estruturas de dados, como pilhas, filas e deques. Eles também podem ser usados para implementar algoritmos essenciais de grafos, como depth-first search e breadth-first search.

Listas Ligadas Simples

Uma lista simplesmente encadeada é um tipo de lista encadeada na qual cada nó está conectado ao próximo nó na sequência. Cada nó está conectado ao próximo armazenando uma referência a ele. Essa referência única por nó permite que você percorra a lista encadeada em uma direção, do início ao fim. A busca só pode avançar, não retroceder. Neste exemplo, você começaria no nó head, nó A. O nó head é o primeiro nó na lista ligada. Em uma lista simplesmente encadeada, o nó head geralmente é o único nó que é diretamente acessível. É aqui que o processo de busca começará quando você estiver tentando encontrar um nó específico. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-singly-linked-lists-work-and-how-do-they-differ-from-doubly-linked-list-2.webp" alt="singly linked list traversal visualization"> O processo começará no nó A, depois continuará para o nó B, depois para o nó C e finalmente para o nó D, o nó tail. Também pode parar antes disso se você implementar uma lógica específica no seu código. O nó tail é o último nó. É usado para determinar quando o processo alcançou o final da lista encadeada.

Inserindo Nós

Uma das grandes vantagens das listas encadeadas é que elas não têm um tamanho fixo. Eles podem ser expandidos ou reduzidos conforme necessário simplesmente atualizando as conexões entre os nós. Você pode inserir um nó no início, meio e fim de uma lista ligada. Listas encadeadas não precisam necessariamente armazenar os nós em uma ordem específica. A ordem será determinada pelas conexões entre os nós. No entanto, se você precisar manter os nós em uma ordem específica para seu caso de uso particular, você pode fazer isso implementando essa lógica no seu código e os critérios que você implementar determinarão se o nó será inserido no início, meio ou fim. Para inserir um nó no início da lista ligada, você só precisa criar uma conexão entre o novo nó e o nó que costumava ser o nó cabeça e fazer do novo nó o nó cabeça. Este é um exemplo, onde inserimos o nó E no início e fazemos deste novo nó o nó head da lista ligada. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-singly-linked-lists-work-and-how-do-they-differ-from-doubly-linked-list-3.png" alt="singly linked list insert at beginning visualization"> Inserir um nó no início da lista ligada tem uma complexidade de tempo constante O(1) porque requer apenas atualizar a referência para o nó head e a conexão entre o novo nó head e o próximo nó na sequência. Neste exemplo, estamos inserindo o nó E no início da lista ligada. Isso funcionará corretamente. Mas se quisermos manter a lista encadeada ordenada em ordem alfabética, o nó E teria que ser inserido no final da lista encadeada. Para inserir um nó no final da lista encadeada, primeiro você precisa chegar ao final e então adicionar uma conexão ao novo nó para torná-lo o novo nó final. Esta operação tem complexidade de tempo linear, O(n), onde n é o número de nós armazenados na lista encadeada, porque primeiro você precisa chegar ao final da lista encadeada para fazer a inserção e isso exigiria ir de um nó para o próximo e assim por diante até que o final seja alcançado. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-singly-linked-lists-work-and-how-do-they-differ-from-doubly-linked-list-4.png" alt="singly linked list insert at end visualization"> Se o nó precisar ser inserido em algum lugar no meio da lista ligada, as conexões entre os nós também terão que ser atualizadas. O nó anterior na sequência deve estar conectado ao novo nó e o novo nó deve estar conectado ao próximo nó, como no diagrama a seguir. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-singly-linked-lists-work-and-how-do-they-differ-from-doubly-linked-list-5.webp" alt="singly linked list insert in middle visualization"> A operação de inserção tem uma complexidade de espaço constante O(1), já que inserir um novo nó requer apenas criá-lo e atualizar as conexões entre os nós. Esta operação não depende do tamanho da lista ligada em si.

Removendo Nós

Assim como você pode inserir nós, você também pode removê-los do início, meio e fim da lista ligada. Para remover um nó do início, você precisa atualizar a referência para o nó head, que deve ser o próximo nó na sequência. Esta operação tem uma complexidade de tempo constante O(1), porque ela só requer a atualização da referência da lista encadeada para o nó cabeça. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-singly-linked-lists-work-and-how-do-they-differ-from-doubly-linked-list-6.png" alt="singly linked list remove from beginning visualization"> Para remover um nó do meio da lista encadeada, você precisa atualizar a referência do nó anterior para conectá-lo ao próximo nó na sequência, formando uma espécie de "ponte" entre eles, como você pode ver neste diagrama. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-singly-linked-lists-work-and-how-do-they-differ-from-doubly-linked-list-7.png" alt="singly linked list remove from middle visualization"> Isso removerá o nó que você deseja remover, neste caso o nó B, da sequência de conexões, para que ele não seja alcançado na próxima vez que você percorrê-la. Para remover um nó do final da lista encadeada, você precisa remover a conexão do nó anterior e tornar este nó o novo nó final. Agora a lista ligada terminará no novo nó final. Esta operação tem uma complexidade de tempo linear O(n), porque primeiro você precisa alcançar o final da lista encadeada. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-singly-linked-lists-work-and-how-do-they-differ-from-doubly-linked-list-8.png" alt="singly linked list remove from end visualization"> A operação de exclusão tem uma complexidade de espaço constante O(1), porque nenhuma memória adicional é necessária para excluir um nó.

Listas Duplamente Ligadas

Agora que você sabe mais sobre listas simplesmente encadeadas, vamos falar sobre listas duplamente encadeadas. Em uma lista duplamente encadeada, cada nó armazena duas referências: uma referência para o próximo nó e uma referência para o nó anterior na sequência. Isso significa que listas duplamente encadeadas podem ser percorridas em ambas as direções. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-singly-linked-lists-work-and-how-do-they-differ-from-doubly-linked-list-9.webp" alt="doubly linked list structure visualization"> Neste tipo de lista encadeada, também é comum manter uma referência para o nó tail na própria lista encadeada para iniciar a travessia a partir do final se necessário. Isso soa ótimo, certo? Eles são mais flexíveis do que listas simplesmente encadeadas. No entanto, listas duplamente encadeadas exigem mais memória do que listas simplesmente encadeadas porque cada nó armazena duas referências em vez de uma. Isto é algo que você deve ter em mente ao escolher a estrutura de dados certa para o seu projeto. Há uma troca. As operações de inserção e exclusão funcionam exatamente da mesma forma. A única diferença é que agora você precisará atualizar duas referências por nó e acompanhar a referência para o nó tail para inserir elementos no final da doubly linked list de forma muito eficiente e iniciar o processo de travessia a partir da parte de trás, se necessário. Listas simplesmente e duplamente encadeadas são estruturas de dados essenciais em ciência da computação usadas para armazenar e manipular elementos em uma ordem sequencial. Entender suas diferenças é essencial para escolher o certo para sua aplicação específica.