Lista Encadeada

Uma lista encadeada é uma estrutura de dados linear que consiste em uma sequência de elementos chamados de nós.

Cada nó contém dois componentes: um campo de valor e uma referência (ou ponteiro) para o próximo nó na sequência.

Estrutura

Uma lista encadeada é composta por nós, onde cada nó contém:

• Valor: O valor ou informação a ser armazenado.
• Próximo: Uma referência para o próximo nó na sequência.

O último nó da lista aponta para nulo, indicando o fim da lista.

Tipos de Listas Encadeadas

Existem diferentes tipos de listas encadeadas, incluindo:

• Lista Encadeada Simples: Cada nó aponta para o próximo nó na sequência.
• Lista Encadeada Dupla: Cada nó tem referências tanto para o próximo quanto para o nó anterior.
• Lista Encadeada Circular: O último nó aponta de volta para o primeiro nó, formando uma estrutura circular.

Este repositório abordará listas encadeadas simples e duplamente encadeadas.

Casos de Uso

Listas encadeadas têm aplicações versáteis em vários cenários, tornando-as uma estrutura de dados fundamental em ciência da computação. Aqui estão alguns casos de uso comuns onde listas encadeadas são amplamente empregadas:

• Implementação de Pilhas, Filas e Tabelas de Hash: Listas encadeadas fornecem uma base para implementar outras estruturas de dados, como pilhas, filas e tabelas de hash.
  • Pilhas: Uma pilha pode ser implementada usando uma lista encadeada simples, onde os nós são adicionados e removidos de uma extremidade (topo) da lista. O último nó inserido representa o topo da pilha. Pilhas são usadas em várias aplicações, como avaliação de expressões, algoritmos de retrocesso e gerenciamento de histórico do navegador.
  • Filas: Uma fila também pode ser implementada usando uma lista encadeada simples, onde os nós são adicionados em uma extremidade (traseira) e removidos na outra extremidade (frente) da lista. O primeiro nó inserido representa a frente da fila. Filas encontram aplicações em algoritmos de agendamento, sistemas de gerenciamento de tarefas e armazenamento de impressão.
  • Tabelas de Hash: Em implementações de tabelas de hash, listas encadeadas são comumente usadas para lidar com colisões. Cada balde na tabela de hash pode ser uma lista encadeada, e elementos com o mesmo valor de hash são armazenados na lista encadeada correspondente. Tabelas de hash são amplamente usadas em armazenamento de dados, caching e operações baseadas em dicionário.

Exemplos Reais

Aqui estão alguns exemplos do mundo real que ilustram o uso de listas encadeadas

• Lista Encadeada Simples
  • Navegação GPS: Sistemas de navegação GPS utilizam uma lista encadeada para representar dados de mapas. Cada nó na lista representa um local, e a lista encadeada permite uma travessia eficiente do ponto de origem ao destino. O redirecionamento por um GPS é um exemplo de adicionar e remover nós nos dados do mapa, garantindo atualizações em tempo real na navegação.
• Lista Encadeada Dupla:
  • Botão de Próximo e Anterior do Navegador: Navegadores utilizam uma lista encadeada duplamente para implementar a funcionalidade dos botões próximo e anterior. Cada URL visitada é armazenada como um nó, e a lista encadeada duplamente permite uma navegação eficiente pelo histórico de navegação. Os usuários podem facilmente mover-se para frente e para trás pelas páginas web visitadas.

Implementação em Python e Typescript

Para ver uma implementação detalhada de listas encadeadas em Python e TypeScript, você pode acessar o repositório do meu GitHub.

O repositório contém exemplos práticos e código completo para ajudar na compreensão e implementação dessas estruturas de dados.

• Repositório no GitHub

Sinta-se à vontade para explorar, contribuir e adaptar os exemplos para suas necessidades. Se tiver alguma dúvida ou sugestão, não hesite em abrir uma issue no repositório!

Uma lista encadeada suporta várias operações que permitem a manipulação e recuperação de dados dentro da lista. Aqui estão algumas operações comuns realizadas em uma lista encadeada:

Inserção

A inserção envolve adicionar um novo nó à lista encadeada em uma posição especificada. Existem três cenários principais para inserção:

• Prepend – Inserção no Início: Neste caso, um novo nó é inserido no início da lista encadeada, tornando-se o novo cabeça da lista. O ponteiro próximo do novo nó é definido como o atual cabeça, efetivamente empurrando os elementos existentes para baixo na lista.
• Insert – Inserção no Meio: Este cenário envolve inserir um novo nó entre dois nós existentes. O ponteiro próximo do novo nó é definido como o próximo nó da posição desejada, enquanto o ponteiro próximo do nó anterior é atualizado para apontar para o novo nó.
• Append – Inserção no Fim: Aqui, um novo nó é inserido no final da lista encadeada. O ponteiro próximo do último nó é definido como o novo nó, que se torna o novo último nó da lista.

Deleção

A deleção envolve remover um nó da lista encadeada. Semelhante à inserção, existem três cenários principais para deleção:

• Shift / Pop Head – Deleção no Início: Neste caso, o primeiro nó (cabeça) da lista encadeada é removido. O cabeça é atualizado para o próximo nó, descartando efetivamente o atual cabeça.
• Remove – Deleção no Meio: Aqui, um nó é deletado de uma posição dentro da lista encadeada, excluindo o primeiro e o último nó. O ponteiro próximo do nó anterior é atualizado para pular o nó deletado e apontar para o próximo nó.
• Pop – Deleção no Fim: Este cenário envolve remover o último nó da lista encadeada. O ponteiro próximo do penúltimo nó é definido como nulo, designando-o como o novo último nó.

Percurso

Percorrer a lista refere-se ao processo de acessar cada nó na lista encadeada de maneira sequencial. Começando pelo nó cabeça, você pode iterar através da lista seguindo os ponteiros próximos até alcançar o fim da lista. O percurso permite realizar operações em cada nó, como imprimir os valores ou aplicar transformações.

Busca

A busca envolve encontrar um valor ou condição específica dentro da lista encadeada. Começando pelo nó cabeça, você pode iterar pela lista, comparando o valor de cada nó com o valor ou condição desejada. Se uma correspondência for encontrada, você pode retornar o nó ou realizar a operação necessária.

Complexidade de Tempo

Prepend – Inserção no Início: O(1)Inserir um nó no início da lista encadeada envolve atualizar o ponteiro cabeça, o que leva tempo constante.

Insert – Inserção no Meio: O(n)Para inserir um nó em uma posição arbitrária na lista encadeada, você precisa percorrer a lista até chegar à posição desejada. No pior caso, isso requer visitar todos os n nós, resultando em uma complexidade de tempo linear.

Append – Inserção no Fim: O(n) ou O(1) se o ponteiro do final for mantidoSe a lista encadeada mantém um ponteiro para o final, inserir um nó no final pode ser feito em tempo constante atualizando o ponteiro do final. Caso contrário, você precisa percorrer toda a lista para alcançar o último nó, resultando em uma complexidade de tempo linear.

Shift – Deleção no Início: O(1)Deletar o primeiro nó envolve atualizar o ponteiro cabeça, o que pode ser feito em tempo constante.

Remove – Deleção no Meio: O(n)Deletar um nó de uma posição arbitrária requer percorrer a lista para encontrar o nó a ser deletado. No pior caso, pode ser necessário visitar todos os n nós, resultando em uma complexidade de tempo linear.

Pop – Deleção no Fim: O(n) ou O(1) se o ponteiro do final for mantidoSemelhante à inserção, deletar o último nó pode ser feito em tempo constante se o ponteiro do final for mantido. Caso contrário, você precisa percorrer a lista para atualizar o ponteiro do penúltimo nó, resultando em uma complexidade de tempo linear.

Percurso: O(n)Para percorrer uma lista encadeada e visitar cada nó, você precisa iterar por todos os n nós, resultando em uma complexidade de tempo linear.

Busca: O(n)No pior caso, você pode precisar visitar todos os n nós para encontrar um valor ou condição específica na lista encadeada, resultando em uma complexidade de tempo linear.

Complexidade de Espaço

A complexidade de espaço de uma lista encadeada é O(n) porque requer memória adicional para armazenar os nós e seus ponteiros correspondentes. Cada nó na lista encadeada ocupa espaço para o valor/dado e o ponteiro para o próximo (e possivelmente o anterior) nó.

Vale notar que a complexidade de espaço pode ser ainda maior se ponteiros adicionais, como um ponteiro para o final ou ponteiros anteriores em uma lista encadeada duplamente, forem mantidos.

Tenha em mente que essas complexidades de tempo e espaço são diretrizes gerais e podem variar dependendo de implementações ou otimizações específicas.