Estrutura de dados e algoritmos - lista vinculada

Uma lista vinculada é uma sequência de estruturas de dados, que são conectadas por meio de links.

Lista vinculada é uma sequência de links que contém itens. Cada link contém uma conexão com outro link. A lista vinculada é a segunda estrutura de dados mais usada depois da matriz. A seguir estão os termos importantes para entender o conceito de Lista Vinculada.

  • Link - Cada link de uma lista vinculada pode armazenar dados chamados de elemento.

  • Next - Cada link de uma lista vinculada contém um link para o próximo link chamado Avançar.

  • LinkedList - Uma lista vinculada contém o link de conexão para o primeiro link denominado Primeiro.

Representação de lista vinculada

A lista vinculada pode ser visualizada como uma cadeia de nós, onde cada nó aponta para o próximo nó.

Conforme a ilustração acima, a seguir estão os pontos importantes a serem considerados.

  • A lista vinculada contém um elemento de link chamado primeiro.

  • Cada link carrega um campo (s) de dados e um campo de link chamado next.

  • Cada link está vinculado ao seu próximo link usando o próximo link.

  • O último link carrega um link como nulo para marcar o final da lista.

Tipos de lista vinculada

A seguir estão os vários tipos de lista vinculada.

  • Simple Linked List - A navegação do item é apenas para frente.

  • Doubly Linked List - Os itens podem ser navegados para frente e para trás.

  • Circular Linked List - O último item contém o link do primeiro elemento como próximo e o primeiro elemento contém um link para o último elemento como anterior.

Operações básicas

A seguir estão as operações básicas suportadas por uma lista.

  • Insertion - Adiciona um elemento no início da lista.

  • Deletion - Exclui um elemento do início da lista.

  • Display - Exibe a lista completa.

  • Search - Pesquisa um elemento usando a chave fornecida.

  • Delete - Exclui um elemento usando a chave fornecida.

Operação de Inserção

Adicionar um novo nó à lista vinculada é uma atividade de mais de uma etapa. Devemos aprender isso com diagramas aqui. Primeiro, crie um nó usando a mesma estrutura e encontre o local onde ele deve ser inserido.

Imagine que estamos inserindo um nó B (NewNode), entre A (LeftNode) e C(RightNode). Em seguida, aponte B. ao lado de C -

NewNode.next −> RightNode;

Deve ser assim -

Agora, o próximo nó à esquerda deve apontar para o novo nó.

LeftNode.next −> NewNode;

Isso colocará o novo nó no meio dos dois. A nova lista deve ser semelhante a esta -

Etapas semelhantes devem ser tomadas se o nó estiver sendo inserido no início da lista. Ao inseri-lo no final, o penúltimo nó da lista deve apontar para o novo nó e o novo nó apontará para NULL.

Operação de Exclusão

A exclusão também é um processo de mais de uma etapa. Vamos aprender com a representação pictórica. Primeiro, localize o nó de destino a ser removido, usando algoritmos de pesquisa.

O nó esquerdo (anterior) do nó de destino agora deve apontar para o próximo nó do nó de destino -

LeftNode.next −> TargetNode.next;

Isso removerá o link que estava apontando para o nó de destino. Agora, usando o código a seguir, removeremos o que o nó de destino está apontando.

TargetNode.next −> NULL;

Precisamos usar o nó excluído. Podemos manter isso na memória, caso contrário, podemos simplesmente desalocar a memória e limpar o nó de destino completamente.

Operação reversa

Esta operação é completa. Precisamos fazer o último nó a ser apontado pelo nó principal e reverter toda a lista vinculada.

Primeiro, vamos até o final da lista. Deve estar apontando para NULL. Agora, faremos com que ele aponte para seu nó anterior -

Temos que ter certeza de que o último nó não é o último nó. Portanto, teremos algum nó temporário, que se parece com o nó principal apontando para o último nó. Agora, faremos todos os nós do lado esquerdo apontarem para seus nós anteriores, um por um.

Exceto o nó (primeiro nó) apontado pelo nó principal, todos os nós devem apontar para seu predecessor, tornando-os seu novo sucessor. O primeiro nó apontará para NULL.

Faremos o nó principal apontar para o novo primeiro nó usando o nó temporário.

A lista vinculada agora está invertida. Para ver a implementação da lista vinculada na linguagem de programação C, clique aqui .