Given a singly linked list implementation and instantiation:
class ListNode:
def __init__(self, val=0, next=None):
self.next = next
self.val = val
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
After the following operations:
current_node = head
current_node = current_node.next
current_node.next = current_node.next.next
the resulting linked lists are 2->4 for current_node
, and 1->2->4 for head
. The result for current_node
makes sense to me, but I am confused as to why the result of head
is changed at all. After these 3 operations, I had expected head
to be equal to what it was originally (1->2->3->4) as there aren't any operations made directly to head
. However, if the operations were this instead:
current_node = head
current_node.next = current_node.next.next
I do expect head
to be modified as well to 1->3->4, as both current_node
and head
reference the same memory address. In contrast, in the first example, after the second line the reassigned, current_node
no longer references the same memory address as head
. My understanding is that whatever happens to this reassigned current_node
shouldn't be related to head
anymore (which apparently isn't the case). Can someone please explain what is happening with head
in the first example?
Via head
you can reach the other nodes. If one of those nodes get's their next
attribute adapted, this will be "visible" when starting from head
.
It may help to visualise what is happening in the first case. We start out with a linked list that can be pictured as follows:
head
│
┌─┴─────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │ │ val: 2 │ │ val: 3 │ │ val: 4 │
│ next: ────────┤ next: ────────┤ next: ────────┤ next: None│
└───────────┘ └───────────┘ └───────────┘ └───────────┘
Then current_node
is defined with current_node = head
, which results in this state:
head
│
┌─┴─────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │ │ val: 2 │ │ val: 3 │ │ val: 4 │
│ next: ────────┤ next: ────────┤ next: ────────┤ next: None│
└─┬─────────┘ └───────────┘ └───────────┘ └───────────┘
│
current_node
Then current_node = current_node.next
makes it reference the second node:
head
│
┌─┴─────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │ │ val: 2 │ │ val: 3 │ │ val: 4 │
│ next: ────────┤ next: ────────┤ next: ────────┤ next: None│
└───────────┘ └─┬─────────┘ └───────────┘ └───────────┘
│
current_node
Then comes the mutation of the list with current_node.next = current_node.next.next
:
head
│
┌─┴─────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │ │ val: 2 │ │ val: 3 │ │ val: 4 │
│ next: ────────┤ next: ──────┐ │ next: ────────┤ next: None│
└───────────┘ └─┬─────────┘ │ └───────────┘ └─┬─────────┘
│ └───────────────────┘
current_node
As you can see, it doesn't matter whether you access the node with value 2 via head
or via current_node
: that node has one next
attribute and it will always be that one that is followed when traversing the list. Unless you create a new node with value 2, there is no way that this node could somehow say that its successor is the node with 3 when you arrive there starting from head
, while at the same time it would say its successor is the node with 4 when your traverse it from current_node
.