Início / coding / Perguntas / 77772794
Accepted
TEOTU
Asked: 2024-01-07 18:57:05 +0800 CST

uma pergunta sobre o método de exclusão de lista vinculada python

  • 772

Acompanho um livro de estruturas de dados, e lá implementamos uma classe LinkedList com seus métodos, tenho uma dúvida sobre o método de exclusão

    def deletion(self, index):
        current_node = self.first_node
        current_index = 0
        if index == 0:
            self.first_node = self.first_node.next_node
        else:
            while current_index < (index - 1):
                current_node = current_node.next_node
                current_index += 1
            current_node.next_node = current_node.next_node.next_node

e especificamente sobre esta linha current_node.next_node = current_node.next_node.next_node. Talvez eu ainda não saiba contar, mas pelo que entendi, se eu passar no índice 3, no final do loop while o current_node deveria estar no índice 2, mas no livro, para deletar o índice 3 nós chamada current_node.next_nodeque nos leva ao terceiro índice e depois o conecta ao quarto, que não deve fazer nada do que precisamos, mas realmente funciona. Então, eu gosto, conto errado ou algo assim ou o quê?

python

1 respostas

  1. Best Answer

    Quando você deseja excluir um nó de uma lista vinculada (individualmente), você precisa alterar o nó predecessor, para que seu próximo atributo não faça mais referência ao nó a ser excluído, mas ao sucessor desse nó.

    No final do whileciclo, a situação pode ser retratada da seguinte forma:

    
           index−1               index                 index+1

       current_node
          ↓
       ┌─────────────┐       ┌─────────────┐       ┌─────────────┐
       │ data: 10    │       │ data: 20    │       │ data: 30    │
...───►│ next_node: ────────►│ next_node: ────────►│ next_node: ───... 
       └─────────────┘       └─────────────┘       └─────────────┘

    O meio desses três nós possui o índice fornecido e precisa ser removido. Para fazer isso devemos alterar o next_nodeatributo do seu antecessor (ou seja, o nó ilustrado à esquerda), e é por isso que current_nodeprecisamos fazer referência a esse nó, e não àquele a ser excluído.

    Então a questão é: qual deveria ser o novo valor de sua next_nodereferência? Deve apontar para o sucessor do nó a ser excluído, ou seja, o nó ilustrado à direita.

    Finalmente, como podemos obter uma referência ao nó sucessor? Seguindo a next_nodereferência, chegamos ao nó intermediário, e quando obtemos a next_nodereferência desse nó, chegamos ao nó sucessor. Portanto, são necessários dois “passos” para chegar lá.

    É por isso que precisamos fazer isso:

    current_node.next_node = current_node.next_node.next_node

    O lado direito desta atribuição é uma referência ao nó sucessor (observe as duas etapas: primeiro chegamos ao nó do meio, depois saltamos mais uma etapa para o nó do lado direito).

    Se desejar, você pode dividir essa tarefa em várias declarações, para esclarecer melhor o que está acontecendo:

    node_to_delete = current_node.next_node
node_after_deleted = node_to_delete.next_node
current_node.next_node = node_after_deleted

    A atribuição resulta nesta situação:

    
           index−1               index                 index+1

       current_node
          ↓
       ┌─────────────┐       ┌─────────────┐       ┌─────────────┐
       │ data: 10    │       │ data: 20    │       │ data: 30    │
...───►│ next_node: ────┐    │ next_node: ────────►│ next_node: ───... 
       └─────────────┘  │    └─────────────┘   ┌──►└─────────────┘
                        └──────────────────────┘

    Uma vez executada esta atribuição (e o nó referenciado por current_nodesofreu mutação), o nó a ser excluído não pode mais ser alcançado: não há mais referência a ele. Isso significa que o coletor de lixo (que roda em segundo plano) agora está livre para desalocar a memória que este objeto ocupa, e assim realmente alcançamos esta situação:

    
           index−1                                   index

       current_node
          ↓
       ┌─────────────┐                             ┌─────────────┐
       │ data: 10    │                             │ data: 30    │
...───►│ next_node: ──────────────────────────────►│ next_node: ───... 
       └─────────────┘                             └─────────────┘

    Espero que isso esclareça.

    • 1

relate perguntas