When does a pointer to a linked list change the actual list?

I have a singly-linked-list, L, and create a pointer to this list P. It seems like sometimes modifying P changes the actual list, while other times modifying P does nothing to the actual list L and only changes what P is pointing to.

Suppose I create a pointer to L, P = L (in python). Doing something like P = P.next leaves L unchanged, but P.next = P.next.next changes L. Similarly, changing the actual data stored in the list by modifying P.data actually changes L.data.

Why does this happen? I feel like I'm missing something fundamental about pointers/references.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

    def addNode(self, val):
        root = self
        while root.next is not None:
            root = root.next
        root.next = Node(val)

    def iterateLL(self):
        root = self
        print
        while root is not None:
            print(str(root.val) + " ", end="")
            root = root.next
        print()

if __name__ =="__main__":
    L = Node(1)
    L.addNode(2)
    L.addNode(3)
    L.addNode(4)

    # iterate through list and print:
    L.iterateLL()

    # changing value of pointer does not affect L
    P = L
    P = P.next
    L.iterateLL() # L is unchanged

    # changing "next" value of pointer does affect L
    P = L 
    P.next = P.next.next
    L.iterateLL() # now we've skipped node 2

    # changing data of pointer does affect L
    P = L
    P.val = 10
    L.iterateLL()

The above code executes with the following output (first line shows the original linked list, second line shows that the list is unchanged following a change to the pointer P, while the third and fourth lines show that the list is changed)

1 2 3 4

1 3 4

10 3 4

What's going on here? Why does changing P not affect L, but changing P.next and P.val do? If all of these actions behaved the same way, wouldn't changing the pointer either always change the linked-list (and so P = P.next should modify L by getting rid of the first node), or never change the linked-list (and thus P.next = P.next.next should leave L unchanged)?

I have a feeling it has something to do with the fact that L.next is a pointer, just like P.next. So modifying P.next ends up modifying what L.next points to (?). But I feel like the rules aren't clear to me.

Solution

In most cases in Python, when you perform an assignment on a variable, P in this case, the value of P changes, but the object that it was originally referring to does not. This is because Python variables are simply references/pointers to objects. Here is an example:

var1 = "test1"
var2 = "test2"
var3 = var1 # var3 = "test1"
var1 = var2 # var1 = "test2"

print(var1) # "test2"
print(var2) # "test2"
print(var3) # "test1"

So what is happening here? Well we are just changing what these variables are pointing to, we are not changing the underlying object.

Now in your case, you do the following:

# changing value of pointer does not affect L
P = L
P = P.next
L.iterateLL() # L is unchanged

When you do P = L and P = P.next, you are simply just changing what the variable P is pointing to. You are not making changes to the underlying object that P points to. Let's visualize it.

Original Configuration:

P = L

P = L.next

However, when you do

P = L
P.next = P.next.next
L.iterateLL() # we've now skipped node two

You are changing an attribute of the object that P is pointing to. You are setting the attribute P.next to point to P.next.next. You are not actually making changes to the underlying object that P.next was originally pointing to. By doing this, the object that P.next was originally pointing to goes out of scope and is cleaned up by the garbage collector.

P.next = P.next.next

Judging by your code, I assume that your intended behavior in this case was to remove L from the LinkedList and end up with a list like so "2 3 4". To accomplish this, it should be sufficient to do L = L.next. This will cause the first node to go out of scope and the garbage collector should clean it up.

As a quick caveat, I mentioned that in most cases, assignment does not make changes to the object that a variable is pointing to. However, properties are a bit different. They override the __set__ magic method which allows you to edit the underlying object using the assignment operator. This is not the case here.