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

Question

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

Furfur

There are no pointers in python – Strohben

If I'm pointing my finger at you, and I start pointing at Joe instead, that doesn't affect you or Joe. If I go up to you and point your finger at whoever Joe was pointing their finger at, that does affect you. – Karolynkaron

@SamuelMuldoon Almost everything in Python is a pointer, Python just hides them pretty well. Most people don't even think about the fact that the variables they're working with are just pointers. – Lichee

Answer 1

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.

Lichee

Ok that makes a lot of sense. Thank you for the thoughtful response. This also explains why setting P.val = newVal also changes L.val to newVal. (In this case I didn't have an intended use for the code, I was just trying to figure out what happens with these pointers in linked lists) – Furfur

Answer 2

You wrote,

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

However, you did not change the next value. You read from P.next. P.next was on the right-hand-side of the assignment. In order to change P.next, P.next would have to be on the left-hand-side of the assignment operator (=)

Then you write:

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

This time P.next is on the left-hand-side of the assignment operator (=). Therefore, you actually changed it.

write_to = read_from

Strohben

I agree that I’m not changing P.next, and so I agree that the comment is misleading. But by setting P=P.next, P is now 2->3->4, while L is still 1->2->3->4. So if I had instead written in the comment “changing value of pointer”, I think the question still stands – Furfur

@mcc: If you have to think in terms of pointers, then think about it like this. P = whatever is assigning one pointer to another pointer. This doesn't affect anything the pointers are pointing to. P.next = whatever is also assigning one pointer to another pointer, which doesn't affect anything the pointers are pointing to... but the pointer you're assigning to is a member of another object, and that member is now pointing somewhere new. – Karolynkaron

Answer 3

One key understanding here is -

Every variable in python is a reference (act as pointer) to an object i.e. a class instance

For example, lets look at Student() class

S1 = Student()  # Creates a new instance of the Student class and assigns it's reference to S1
S2 = S1         # Assigns the reference to the same instance to S2

Here, S1 and S2 both reference the same instance of the Student() class. In Python, when you do S2=S1, S2 refers to the same object S1 is referring to. It does not create a new object, and it's not a pointer to S1.

Now, coming to your problem,

1. P = L ==> you assign the reference to the same instance which is assigned to L, to P
2. P = P.next ==> you reassign P to the next node of P leaving the original object unchanged and hence L is unchanged.
3. If you do P.next = P.next.next instead ==> you are assigning the next node of P.next to P.next. There is a change in the actual data stored. Since the object's reference is also assigned to L, L.data will also change.

However, if you just want to create a new independent copy of the object, you can do a shallow copy like this

import copy

S1 = Student()
S2 = copy.copy(S1)

Here, modifications to one won't affect the other.

Orangeism