Search code examples
pythonlinked-listvariable-assignment

Question on object assignment in Python - Linked list node example


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?


Solution

  • 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.