Modify linked list node "in place" in Python

Question

I came across my question while practicing an (admittedly simple) LeetCode problem. However, my real question is about Python, not the answer to the problem itself. You'll see the full problem statement below, after which I explain my approach, contrast it with the actual solution, and then (finally) ask my question.

---

LeetCode Problem: Delete Node in Linked List

Problem:

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list -- head = [4,5,1,9], which looks like following:

img

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Note:

• The linked list will have at least two elements.
• All of the nodes' values will be unique.
• The given node will not be the tail and it will always be a valid node of the linked list.
• Do not return anything from your function.

---

My Approach:

I fired off a quick answer (which was sub optimal at O(n), but that's not the point) where I reassign the values of the deleted node and all nodes to it's right by shifting them all one unit to the left. In this example, a bracketed node will be reassigned next:

1. 4->[5]->1->9->None becomes
2. 4->1->[1]->9->None, then
3. 4->1->9->[9]->None, and finally
4. 4->1->9->None.

Or at least, that's what I expected from the code I wrote below.

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
 def deleteNode(self, node):
 while node != None:
 node = node.next

what surprised me about this answer was that the input linked list was exactly the same as the output linked list. Here's a screenshot of the output:

LeetCode Output for incorrect deleteNode function

---

The Actual Solution:

The solution , with a complexity of O(1), is shown below with corresponding (correct) output.

class Solution:
 def deleteNode(self, node):
 node.val = node.next.val
 node.next = node.next.next

LeetCode Output for correct deleteNode function

---

My Question:

Why is it that node.val = node.next.val and node.next = node.next.next modifiy the node of the linked list "in place", while reassigning node in node = node.next has no effect on the object node references?

Answer 1

node = node.next just reassigns the parameter of deleteNode, which doesn't effect anything outside of the function.

Think of it like this: would you expect this to modify x?

x = 1
def f(a):
 a = 2
f(x)

It won't. a here is just a local reference inside of f. All reassigning it does is change what object a is pointing to.

Compare that to:

x = []
def f(a):
 a.append(2)
f(x)

This will change x. Here, you aren't reassigning the local reference, you're mutating the object that the local reference points to. With your second code, node.val = node.next.val alters a field inside of node. It changes the object.

That's the difference between your two pieces of code. The first piece of code just alters the reference to the object. The second piece of code alters the object itself.

• David: I understand your answer, but I think there's something more general about python that I'm not getting. Let's say we have a real node object real and an identifier to that object ident. my question is if ident is just an identifier for real, why isn't ident.val also an identifier for real.val? In other words, if changing ident has no effect on real why is it that ident.val = ident.next.val alters a field inside of real (it changes the object), rather than merely changing what ident.val references?
• David: Put another way, is there a good explanation for why this is true:" node.val = node.next.val alters a field inside of node. It changes the object." in terms of identifier,object bindings?
• Carcigenicate: @David This isn't specific to Python. There would be similar behavior in Java as well. Let me see if I can figure out an written explanation that makes sense. If we had a whiteboard in front of us I could explain it, as that's how I learned it and how I visualize it in my head to this day. I'm much more of a visual person.
• David: Actually, I took your idea & found a whiteboard to see if I could explain it myself. Here's my best shot: identifiers don't have attributes, only objects do. When ident becomes an identifier for real, that doesn't mean it becomes some kind of "identifier object" with attributes that are identifiers for all the attributes of real like ident.val->real.val and ident.next->real.next. ident is just a single identifier (a single arrow) bound to real. Through ident, we can access the attributes of real, which is what happens when we write ident.val and ident.next
• Carcigenicate: @Dave That is actually roughly what I was going for. I visualize this typically by writing the name of the object (node), then an arrow pointing from it to some object (usually a circle for visualization). The name and the object are separate entities. When you do use a name like someVar.append() in your program, it finds what object the someVar name is associated with, and calls append on it. someVar is not some other list object with its own state. I think of it as a label pointing to the object.