© Profit_Image/Shutterstock.com
Você pode ter entendido as matrizes, mas há muitas estruturas de dados que você pode usar na programação. De certa forma, uma lista encadeada é semelhante a uma matriz, mas existem algumas diferenças importantes. Descubra o que é uma lista vinculada, explore os diferentes tipos de listas vinculadas e descubra como usar uma com este artigo.
O que é uma lista vinculada?
Como uma matriz, uma lista linear é uma estrutura de dados que é linear. Mas a diferença está na forma como armazenam e acessam os dados. Enquanto uma matriz armazena elementos em um bloco contíguo de memória, uma lista encadeada contém elementos como nós, com cada nó apontando para o próximo elemento na lista. Dessa forma, eles não são armazenados de forma contígua e os elementos não são acessados usando um índice. Em vez disso, os ponteiros são atribuídos a cada nó, que determinam o próximo nó na sequência. Assim como em uma matriz dinâmica, as listas vinculadas podem ser modificadas adicionando ou removendo nós conforme necessário.
Quais são os benefícios?
Agora que abordamos exatamente o que é uma lista encadeada, você deve estar se perguntando por que quer usar um. Aqui estão algumas vantagens:
A menos que você esteja usando uma matriz dinâmica, o tamanho da matriz tende a ser fixo, enquanto as listas vinculadas podem ser aumentadas ou diminuídas conforme apropriado.Inserir ou excluir elementos requer tempo constante, ao contrário das matrizes onde outros elementos precisarão ser deslocados. Listas vinculadas tendem a ser mais fáceis em suas restrições de memória, particularmente com grandes volumes de dados. Isso ocorre porque a memória é usada apenas para os nós necessários, mas a natureza contígua dos arrays significa que você pode estar suportando alguns dados desnecessários para suas operações. É mais fácil manter a persistência de dados com listas vinculadas, pois os dados podem ser serializado mais facilmente do que em arrays. Isso simplifica a transmissão de dados entre vários programas ou após o término dos programas. Onde você tiver dados esparsos, ou seja, com elementos vazios, uma matriz ainda os armazenará. Uma lista vinculada, no entanto, armazena apenas valores que não estão vazios.
Quais são os diferentes tipos de listas vinculadas?
Existem alguns tipos diferentes de listas vinculadas que você pode usar, cada uma com suas próprias qualidades. Faremos um breve resumo aqui e como implementá-los em Python.
Lista vinculada simples
Como você poderia esperar, este é o tipo mais simples de lista encadeada, onde você só pode percorrer a lista em uma direção. Cada ponteiro aponta para o próximo nó, com o nó final apontando para nada, ou NULL. Isso também é conhecido como uma lista encadeada individualmente. O código para implementar uma lista encadeada simples em Python é o seguinte:
class Node: def __init__(self, data): self.data=data self.next=None class LinkedList: def __init__(self): self. head=None def add(self, data): new_node=Node(data) se self.head for None: self.head=new_Node else: current_node=self.head enquanto current_node.next não for None: current_node=current_node.next current_node.next=new_node def remove(self, data): se self.head for None: retornar se self.head.data==dados: self.head=self.head.next retornar current_node=self.head enquanto current_node.next for não Nenhum: se current_node.next.data==data: current_node.next=current_node.next.next return def display(self): current_node=self.head while cur rent_node não é nenhum: print(current_node.data) current_node=current_node.next my_list=LinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display() my_list.remove(2) my_list.display
Explicação
Este é um bloco de código bastante extenso, mas não muito difícil de entender.
Primeiro, estamos definindo o “Nó” e a “LinkedList”Aulas. A classe “Node” representa um nó na lista, cada um com um ponteiro (indicado por “self.next”). A lista é representada por “LinkedList”, e implementamos um nó de cabeçalho, que facilita a inserção ou exclusão de elementos.
A função “add” indica que um novo nó deve ser adicionado à o fim da lista. Se a lista estiver vazia, o nó do cabeçalho será definido para o novo nó criado. Se não estiver vazio, a lista é percorrida até o último nó e aponta para o novo nó.
A função “remover” funciona removendo o primeiro nó da lista. Se este for o nó de cabeçalho, o próximo nó se tornará o nó de cabeçalho. Se o nó principal não tiver os dados fornecidos, a lista será percorrida para encontrá-los. Depois de encontrar o nó com os dados fornecidos, seu atributo “próximo” é definido para o nó seguinte, o que remove esse nó da lista.
“Display” percorre a lista e imprime os dados encontrados em cada nó.
Os dados dentro da lista são definidos com a classe “LinkedList” no final, com nós de valores de dados 1, 2 e 3. O nó 2 foi removido para mostrar o processo de remoção, e ambas as listas são impressas para a saída. Confira a captura de tela para saber como isso funciona.
Os dados dentro da lista são definidos com a classe “LinkedList” no final, com nós de valores de dados 1, 2 e 3.
©”TNGD”.com
Duplamente Lista vinculada
Isso é semelhante a uma lista simples, exceto que a travessia pode ocorrer em ambas as direções, para frente e para trás. Para implementar isso, podemos usar o seguinte código:
class Node: def __init__(self, data): self.data=data self.prev=None self.next=None class DoubleLinkedList: def __init__(self): self.head=Nenhum self.tail=Nenhum def add(self,data): new_node=Node(data) se self.head for None: self.head=new_node self.tail=new_node else: new_node.prev=self.tail self.tail.next=new_node self.tail=new_node def remove(self, data): current_node=self.head enquanto current_node não for None: se current_node.data==data: se current_node.prev não for None: current_node.prev.next=current_node.next else: self.head=current_node.next se current_node.next não for None: current_node.next.prev=current_node.prev else: self.tail=current_node.prev return current_node=current_node.next def display(self): current_node=self.head enquanto current_node não é None: print(current_node.data) current_node=current_node.next my_list=DoubleLinkedList() my_list. add(1) my_list.add(2) my_list.add(3) my_list.display() my_list.remove(3) my_list.display()
Explicação
Muito do código neste O exemplo é semelhante, mas há algumas diferenças.
Definimos a classe “Node” de maneira semelhante, mas há referências ao nó anterior, bem como ao próximo nó desta vez. Da mesma forma, a classe ”DoublyLinkedList” representa a lista, mas tem instâncias funcionando tanto como início quanto fim da lista.
Como antes, a função “add” adiciona um novo nó ao final da lista. Mas se a lista estiver vazia, tanto a cabeça quanto a cauda serão definidas para esse novo nó. Quando a lista não está vazia, o atributo “prev” do novo nó é definido para a cauda atual e o atributo “próximo” da cauda atual para o novo nó, e a cauda é alterada para o novo nó.
A função “remover” remove o primeiro nó da lista com os dados fornecidos. Os atributos “prev” e “next” dos nós adjacentes são atualizados para evitar o nó atual, removendo-o efetivamente da lista. Se o nó em questão for a cabeça ou a cauda, esse atributo também será atualizado para refletir isso.
Por fim, as funções “display” e “my_list” são basicamente as mesmas, mas desta vez temos removeu o nó com valor de dados 3. As capturas de tela ilustram a execução do código.
A função “adicionar” adiciona um novo nó ao final da lista.
©”TNGD.com
As funções “display” e “my_list” são basicamente as mesmas, mas desta vez’removi o nó com valor de dados 3.
©”TNGD.com
Listas vinculadas circulares
Outro tipo de lista vinculada é uma lista circular. Como o nome sugere, esta é uma lista onde não há “fim”. O nó final é conectado de volta ao nó inicial. Um exemplo é visto com o seguinte código:
class Node: def __init__(self, data): self.data=data self.next=None class CircularLinkedList: def __init__(self): self.head=None def add (self, data): new_node=Node(data) se self.head for None: self.head=new_node new_node.next=self.head else: current_node=self.head enquanto current_node.next não for self.head: current_node=current_node.next current_node.next=new_node new_node.next=self.head def remove(self,data): se self.head for None: retornar se self.head.data==dados: current_node=self.head while current_node.next não é self.head: current_node=current_node.next current_node.next=self.head.next self.head=self.head.next else: current_node=self.head enquanto current_node.next não é self.head: se current_node.next.data==dados: current_node.next=current_node.next.next return current_node=current_node.next def display(self): se self.head é None: return current_node=self.head while True: print(current_node.data) current_node=current_node.next se current_node for self.head: break my_list=CircularLinkedList() my_list.add(1) my_list.add(2) my_list.add (3) my_list.display()
Explicação
Existem algumas diferenças importantes aqui. O “new_node.next=self.head” significa que o novo nó adicionado é o último nó da lista e aponta para o início da lista, que é o primeiro nó.
O “ enquanto current_node.next não é self.head” a linha é usada para percorrer a lista encadeada e adicionar elementos. Como não há fim verdadeiro, como na lista encadeada individualmente, temos que verificar se o nó atual é o nó principal, em vez de ser simplesmente diferente de zero. Isso evita a alteração do nó principal.
O código “new_node.next=self.head” garante que o nó adicionado à lista esteja conectado com o nó principal.
O A função “remover” funciona de forma semelhante, se os dados fornecidos estiverem contidos no primeiro nó, eles serão removidos e o próximo nó se tornará o novo nó principal. Se o nó principal não contiver os dados fornecidos, a lista é percorrida como antes, até que os dados sejam encontrados. O atributo “próximo” é então atribuído ao nó após este, que pula este nó. No geral, a função é a mesma, mas a implementação é um pouco mais elaborada devido à natureza circular da lista.
A função “display” também é praticamente a mesma, exceto que devemos verificar se estamos começando no nó principal e interrompemos a travessia assim que atingirmos esse ponto novamente.
O código’new_node.next=self.head’garante que o nó adicionado à lista esteja conectado com o nó principal.
©”TNGD”.com
A “exibição” A função também é quase a mesma, mas devemos começar no nó principal e interromper a travessia assim que chegarmos a esse ponto novamente.
©”TNGD.com
Listas duplas circulares vinculadas
Como examinamos listas encadeadas simples, duplas e circulares, isso só faz sentido e para terminar com uma lista encadeada circular dupla. Bastante bocado, mas não totalmente indescritível. Como esperado, isso se refere a uma lista vinculada circular que podemos percorrer nas direções para frente e para trás. A implementação deste tipo de lista pode ser ilustrada da seguinte forma:
class Node: def __init__(self, data): self.data=data self.next=Nenhum self.prev=Nenhum class DoubleCircularLinkedList: def__init__(self): self.head=None def add(self, data): new_node=Node(data) se self.head for None: new_node.next=new_node new_node.prev=new_node self.head=new_node else: last_node=self.head. prev last_node.next=new_node new_node.prev=last_node new_node.next=self.head self.head.prev=new_node def remove(self,data): se self.head for None: return current_node=self.head while current_node.data !=dados: current_node=current_node.next se current_node==self.head: retornar se current_node==self.head: se lf.head=current_node.next current_node.prev.next=current_node.next current_node.next.prev=current_node.prev def display(self): se self.head for None: return current_node=self.head while True: print(current_node.data) current_node=current_node.next if current_node==self.head: break my_list=DoubleCircularLinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display()
Explicação
A principal diferença entre uma lista encadeada circular dupla e uma lista encadeada circular padrão é que, como antes com a lista encadeada não circular, a lista dupla aponta cada nó para o nó anterior, bem como para o próximo nó. Isso é obtido atualizando os atributos “prev” e “next” do último nó e o novo nó ao adicionar um nó. Ao remover um nó, esses atributos do nó removido e dos nós adjacentes precisam ser atualizados. Se você estiver removendo o nó principal, os ponteiros do último nó precisam ser atualizados para refletir isso.
A lista dupla aponta cada nó para o nó anterior, bem como para o próximo nó.
©”TNGD.com
Se você estiver removendo o nó principal , então os ponteiros do último nó precisam ser atualizados para refletir isso.
©”TNGD”.com
Resumo
Muitos tipos de listas vinculadas podem ser usados como uma alternativa para arrays, como quando você precisa inserir e excluir elementos regularmente ou tem restrições de memória. Embora os arrays tenham um desempenho mais rápido quando se trata de determinadas operações, as listas vinculadas têm seus benefícios exclusivos, por isso é útil entender como elas funcionam.
A seguir…
A lista vinculada Perguntas frequentes sobre estrutura de dados e como usá-la (perguntas frequentes)
O que é uma lista vinculada?
Uma lista vinculada é uma estrutura de dados em que os dados é armazenado em “nós” e não de forma contígua, como em um array. Eles podem ser simples ou circulares, onde o último envolve o último nó apontando para o nó principal. Você também pode implementar listas duplamente vinculadas, onde a travessia pode ocorrer para frente e para trás na lista.
Quais são as vantagens e desvantagens das listas vinculadas?
As listas encadeadas podem ser melhores do que as matrizes quando você precisa inserir e excluir dados com frequência ou tem restrições de memória. No entanto, uma matriz pode ser melhor quando você precisa usar a pesquisa binária e, por serem contíguas, são mais compatíveis com o cache. Embora a inserção de elementos seja mais rápida, o acesso a um determinado elemento pode ser mais lento porque você deve percorrer toda a lista.
Quais são os diferentes tipos de listas encadeadas?
Os tipos de listas vinculadas incluem listas vinculadas simples e duplamente vinculadas e listas vinculadas circulares e duplamente circulares.
Como você insere ou exclui um nó de uma lista vinculada?
Para inserir um nó, deve-se criar o novo nó e apontar o atributo “next” deste nó para o próximo nó da lista, bem como apontar o atributo “next” do nó anterior para este novo nó. Para excluir um nó, você deve percorrer a lista para encontrar os dados fornecidos. Em seguida, você precisa apontar o atributo “próximo” do nó anterior para o nó à frente do nó que deseja excluir, para que seja ignorado na lista.
Como você percorre um lista encadeada?
Para percorrer a lista, comece com o nó principal e vá para cada nó na sequência até chegar ao nó final.
Qual é a complexidade de tempo das operações de lista encadeada?
Cada operação tem sua própria complexidade de tempo. As operações com uma complexidade de tempo de O(1) incluem a inserção de um elemento no início e a exclusão de um elemento no início. A maioria das outras operações tem uma complexidade de O(n). Isso inclui acessar um elemento, inserir ou excluir um elemento no final, inserir ou excluir um elemento em um índice específico e pesquisar um elemento específico. Isso ocorre porque a lista deve ser percorrida, portanto, a complexidade depende do tamanho da lista.
Quais são algumas alternativas para listas encadeadas?
Em vez disso de uma lista vinculada, você pode usar uma matriz, onde os dados são armazenados em um bloco contíguo. Tabelas de hash são usadas para mapear chaves para índices em uma matriz, portanto, elas podem ser usadas em conjunto umas com as outras. Ou você pode usar uma árvore, onde os nós são conectados em um formato hierárquico. Heaps são um tipo de árvore binária e são outra opção. Por fim, pilhas e filas podem ser usadas com arrays ou listas encadeadas e, embora não sejam tão flexíveis quanto algumas opções, oferecem modificação eficiente de elementos.
Quais são algumas aplicações de listas encadeadas?
As listas encadeadas são úteis quando você não sabe o tamanho da lista, deseja implementar outras estruturas de dados, no processamento de imagem e música e para representar gráficos e árvores.