-2

After saving a pointer to a linked list node in a variable 'head', I inserted the 'head' inside a Python list (named 'tail'). Then, even if I traversed the linked list by accessing the 'head' variable in the Python list, I can still access the head of the linked list by accessing 'head'. One can check by comparing the two ids : id(head) != id(tail[0]).

Why is it so?

head = ListNode(0)          # Stored a pointer to a ListNode(0)
tail = [head]               # Assigned a pointer to a Python list having a 'head' as an element
tail[0].next = ListNode(1)  # Attached a ListNode(1)
tail[0] = tail[0].next      # Traversed
id(head) == id(tail[0])     # Gives 'False'; two ids are unequal.

# FYI - ListNode definition
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
RyanC
  • 189
  • 1
  • 9
  • 3
    What did you expect and why? `head` is still `head`, but `tail` only contains `ListNode(1)`. – luk2302 Mar 15 '22 at 15:18
  • 1
    You set `tail[0]` to `tail[0].next`, which is `ListNode(1)`. `head` is still set to `ListNode(0)` because you never assigned it anything else. They are referring to different objects. – khelwood Mar 15 '22 at 15:20
  • 1
    For the same reason that `tail = [1]; tail[0] = 2; tail[0] is 1` is false. You changed what `tail[0]` refers to. – chepner Mar 15 '22 at 15:20
  • 2
    You might do well to read https://nedbatchelder.com/text/names.html – chepner Mar 15 '22 at 15:21
  • 1
    Might be worth reading: [Are Python variables pointers? Or else, what are they?](https://stackoverflow.com/questions/13530998/are-python-variables-pointers-or-else-what-are-they) TLDR: ``head`` is *not* what you think of as a pointer. – MisterMiyagi Mar 15 '22 at 15:24
  • Thanks a lot, folks! I am finally convinced by pythontutor.com visualizer that the head and tail[0] points to different things. – RyanC Mar 16 '22 at 02:14

1 Answers1

1
tail[0].next = ListNode(1)  # Attached a ListNode(1)
tail[0] = tail[0].next      # Traversed

in terms of what happens to the array is just

tail[0] = ListNode(1)

And then you are somehow confused why that is not equal to head?! Because head is still ListNode(0).

What is True is id(head.next) == id(tail[0]).

luk2302
  • 55,258
  • 23
  • 97
  • 137