© BEST-BACKGROUNDS/Shutterstock.com
Existem muitas aplicações para listas vinculadas, como música e processamento de imagem e representação de gráficos, árvores e estruturas de dados mais elaboradas. Mas por que você iria querer inverter uma lista encadeada? Vamos entrar nisso.
O que é uma lista encadeada invertida?
Como você provavelmente pode imaginar, é uma lista encadeada que… foi invertida! Normalmente, cada nó aponta para o próximo nó em uma lista, começando no nó principal e terminando no nó final. Mas, quando você inverte uma lista vinculada, os ponteiros são invertidos, de modo que a cabeça se torna a cauda e a cauda se torna a cabeça. Considere o caso simples de uma lista de 5 nós. Isso normalmente ficaria assim:
cabeça → nó1 → nó2 → nó3 → nó4 → nó5 → cauda
uma vez que invertemos a lista, obtemos:
cauda → node5 → node4 → node3 → node2 → node1 → head
Mesmo que a lista se torne mais longa e envolva mais valores de dados, o princípio permanece o mesmo.
Por que você deseja reverter uma Lista encadeada?
Como uma lista encadeada invertida ainda é uma lista encadeada, em essência, muitos dos aplicativos são semelhantes. Como tal, as listas invertidas ainda são usadas na implementação de outras estruturas de dados, em pilhas e em filas. Porém, existem alguns usos exclusivos que as listas vinculadas inversas trazem para a tabela:
Como os elementos são invertidos, podemos imprimir os elementos e processar a lista na ordem inversa. Isso é útil se você deseja exibir o histórico da Internet de um navegador. Se você deseja excluir alguns elementos próximos ao final da lista, a inversão torna isso muito mais fácil. Isso ocorre porque esses elementos agora estão no início da lista. Isso pode economizar muito tempo, especialmente se a lista for grande. Você não precisa percorrer toda a lista se inverter a lista. Às vezes, queremos executar um algoritmo recursivo em uma lista inteira, executando operações em cada nó. Em alguns desses casos, processá-los na ordem inversa pode fazer mais sentido. Outra razão para usar uma lista encadeada invertida é verificar se a lista é palíndroma – isso significa que a sequência é a mesma para frente ou para trás. Um exemplo disso seria o número 212. Seja como for, a sequência de valores de dados é idêntica.
Como inverter uma lista vinculada
Geralmente, existem duas abordagens para reverter uma lista vinculada – a abordagem iterativa e a abordagem recursiva. Vamos dar uma olhada neles.
A Abordagem Iterativa
Neste método, repetimos a execução do algoritmo até que cada ponteiro tenha sido invertido. Fazemos isso rastreando nossos nós usando os atributos “prev”, “curr” e “next”. Podemos atribuí-los como tal:
while (current !=NULL) { next=current-> next current-> next=prev prev=current current=next } head_ref=prev
A instrução “while” basicamente itera sobre cada nó que não é nulo.
A próxima linha mantém o controle do próximo nó na lista, para que não o percamos quando invertermos os ponteiros.
Em seguida, definimos o atributo “next” do nó atual para o nó anterior, invertendo os ponteiros.
A próxima linha define o atributo “prev” para o nó anterior, acompanhando-o como fizemos o próximo nó.
A penúltima linha diz que o ponteiro “atual” está no próximo nó, então podemos mover iterativamente ao longo da lista.
Por fim, definimos o “head_ref ” ponteiro para o último nó da lista original, que será o primeiro nó da lista invertida. Portanto, definimos isso como o novo nó principal.
Veja como podemos implementar esse processo em Python:
class Node: def __init__(self, data): self.data=data self. next=Nenhum classe LinkedList: def __init__(self): self.head=Nenhum def push(self, new_data): new_node=Node(new_data) new_node.next=self.head self.head=new_node def reverse(self): prev_node=Nenhum current_node=self.head enquanto current_node não é None: next_node=current_node.next current_node.next=prev_node prev_node=current_node current_node=next_node self.head=prev_node def printList(self): current_node=self.head while current_node: print( current_node.data, end=””) current_node=current_node.next my_list=LinkedList() my_list.push(16) my_list.push(2) my_list.push(19) my_list.push(71) print(“Lista vinculada dada”) minha_lista.printList() minha_lista.reverse () print(“\nLista encadeada invertida”) my_list.printList()
Primeiro, definimos as classes “Node” e “LinkedList”. Em seguida, definimos a função “push”, que é usada para adicionar um novo nó ao início da lista, que é designado como nó principal.
Depois, vemos a função “reverse” implementada da mesma maneira descrita anteriormente.
Finalmente, estamos definindo a função “printList” para a classe “LinkedList”, que imprime o valor dos dados em cada nó, que continua até o “current_node ” é igual a “None”, indicando que chegamos ao fim da lista. Veja a captura de tela para saber como isso funciona em Python.
A abordagem iterativa para inverter uma lista vinculada, implementada em Python.
©”TNGD.com
A abordagem recursiva
O outro método para reverter uma lista encadeada é a abordagem recursiva. Enquanto as abordagens iterativas funcionam usando loops ou instruções repetitivas para resolver um problema, as abordagens recursivas executam a mesma função em exemplos cada vez menores do mesmo problema. Uma vez resolvidos esses subproblemas, as soluções são combinadas para dar um resultado geral ao problema inicial. Vamos ver como a recursão funciona para reverter uma lista encadeada:
Primeiro, dividimos a lista em duas partes, o primeiro nó e a lista restante.
Em seguida, chamamos o “ reverse” para a lista restante.
Esta lista invertida é então vinculada ao primeiro nó, e o ponteiro do cabeçalho original é definido como NULL. O novo ponteiro de cabeçalho é definido para o novo nó de cabeçalho e a lista é invertida.
Veja como isso é implementado:
class Node: def__init__(self, data): self. data=dados self.next=Nenhum classe LinkedList: def__init__(self): self.head=Nenhum def push(self, new_data): new_node=Node(new_data) new_node.next=self.head self.head=new_node def reverse_recursive( self, current_node): se current_node for None ou current_node.next for None: return current_node rest=self.reverse_recursive(current_node.next) current_node.next.next=current_node current_node.next=None return rest def reverse(self): self. head=self.reverse_recursive(self.head) def printList(self): current_node=self.head while current_node: print(current_node.data, end=””) current_node=current_node.next print() my_list=LinkedList() my_list. push(16) minha_lista.push(2) minha_lista.push(19) minha _list.push(71) print(“Lista vinculada fornecida”) my_list.printList() my_list.reverse() print(“Lista vinculada reversa (recursiva):”) my_list.printList()
Muito desse código é o mesmo que o processo iterativo. A principal diferença está, sem surpresa, na função reverse utilizada.
Neste caso, definimos a função “reverse_recursive” como uma função do nó atual. Cada nó depois disso é invertido recursivamente chamando a função reversa com o próximo nó como entrada até que o nó atual seja igual a “Nenhum”. Isso acontece quando o final da lista é atingido, ou no caso simples onde há apenas um nó na lista.
Depois, o nó atual é revertido atualizando o atributo “next” do próximo nó ao nó atual e o atributo “next” do nó atual a “None”. O nó atual se torna o final da lista invertida.
A abordagem recursiva para inverter uma lista encadeada, implementada em Python.
©”TNGD.com
Resumo
Quando você precisa inverter uma lista encadeada, você pode escolher entre uma abordagem iterativa e uma abordagem recursiva. Enquanto as abordagens iterativas dependem da repetição das mesmas instruções em um loop “while” para cada nó, as funções recursivas executam sua função em instâncias menores do mesmo problema. Reverter uma lista vinculada pode ser útil para detectar a palindromicidade de uma lista e modificar elementos no final da lista original.
Como reverter uma lista vinculada, com exemplos FAQs (perguntas frequentes)
O que é uma lista vinculada invertida?
Uma lista vinculada inversa é uma lista vinculada que teve a ordem de seus elementos invertida, de modo que o último nó se torne o primeiro nó da nova lista e os ponteiros são invertidos.
Por que você deseja inverter uma lista encadeada?
Inverter uma lista pode ser útil para determinar se uma lista é palíndroma, modificar elementos no final da lista original (como agora estão no início) ou quando você deseja usar determinados algoritmos que são melhores para usar com uma lista invertida.
Como você pode inverter uma lista vinculada?
As formas mais comuns de inverter uma lista vinculada são por meio de funções iterativas ou recursivas. Enquanto a abordagem iterativa funciona percorrendo a lista e alterando os ponteiros de cada nó, a função inversa recursiva funciona invertendo a lista do nó principal e, em seguida, atualizando os ponteiros do nó atual.
Como você reverte listas duplamente vinculadas e listas circulares vinculadas?
Você pode inverter uma lista duplamente vinculada da mesma forma que uma lista vinculada individualmente, mas precisa atualizar o”próximo”e atributos “prev” de cada nó de acordo. Para listas vinculadas circulares, você precisa atualizar o atributo “próximo” do nó final para apontar para o novo nó principal.
Qual é a complexidade de tempo de reverter uma lista vinculada?
A complexidade de tempo é igual a O(n), onde n é o número de nós, porque você deve percorrer a lista para inverter os ponteiros, seja qual for o método usado.
Qual é a complexidade de espaço de inverter uma lista vinculada?
A complexidade de espaço é igual a O(1) em relação à abordagem iterativa, pois as variáveis temporárias necessárias para inverter a lista permanecem constante. Para a abordagem recursiva, a complexidade do espaço é igual a O(n), pois você deve armazenar cada chamada da função recursiva em uma pilha.