I follow up a data structures book, and there, we implement a LinkedList class with it's methods, I have a question about the deletion method
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
and specifically about this line current_node.next_node = current_node.next_node.next_node. Maybe I can't count already, but as far as I understand, if I pass in the index 3, at the end of the while loop the current_node should be at the index 2, but in the book, to delete the index 3 we call current_node.next_node which brings us to the 3rd index and then connects it to the 4th which shouldn't do anything we need, but it actually works. So, do I like, count wrong or something or what?
When you want to delete a node from a (singly) linked list, you need to mutate the predecessor node, so that its next attribute no longer references the node to be deleted, but the successor of that node.
At the end of the while loop, the situation can be pictured as follows:
index−1 index index+1
current_node
↓
┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│ data: 10 │ │ data: 20 │ │ data: 30 │
...───►│ next_node: ────────►│ next_node: ────────►│ next_node: ───...
└─────────────┘ └─────────────┘ └─────────────┘
The middle one of these three nodes has the given index and needs to be removed. In order to do that we must change the next_node attribute of its predecessor (i.e. the node pictured at the left), which is why current_node needs to reference that node, and not the one to be deleted.
Then the question becomes: what should be the new value of its next_node reference? It should point to the successor of the node to be deleted, i.e. the node pictured at the right.
Finally, how can we get a reference to the successor node? By following the next_node reference, we get to the middle node, and when we get the next_node reference from that node, we get to the successor node. So two "steps" are needed to get there.
That is why we need to do this:
current_node.next_node = current_node.next_node.next_node
The right hand side of this assignment is a reference to the successor node (note the two steps: first we get to the middle node, then we hop one more step to the right hand side node).
If you wanted to, you could break that assignment into multiple statements, so to better clarify what is happening:
node_to_delete = current_node.next_node
node_after_deleted = node_to_delete.next_node
current_node.next_node = node_after_deleted
The assignment results in this situation:
index−1 index index+1
current_node
↓
┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│ data: 10 │ │ data: 20 │ │ data: 30 │
...───►│ next_node: ────┐ │ next_node: ────────►│ next_node: ───...
└─────────────┘ │ └─────────────┘ ┌──►└─────────────┘
└──────────────────────┘
Once this assignment has been executed (and the node referenced by current_node got mutated), the node to be deleted cannot be reached anymore: there is no reference to it any more. That means the garbage collector (which runs in the background) is now free to deallocate the memory that this object occupies, and so we really have achieved this situation:
index−1 index
current_node
↓
┌─────────────┐ ┌─────────────┐
│ data: 10 │ │ data: 30 │
...───►│ next_node: ──────────────────────────────►│ next_node: ───...
└─────────────┘ └─────────────┘
I hope this clarifies it.