CODEWITHSUNDEEP
pythondata-structureslinked-list
Francis
Francis

Reputation: 199

How to understand the data structure of Python Linked List in Leetcode

I am really confused by the Python linked list data structure used in Leetcode. I am not sure if the problem is caused by the specific ListNode structure created by Leetcode, or I have some misunderstanding about Python. For example, the following piece of code is simple and self-explained:

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def main():
    # Instantiate a linked list 1 -> 2 -> 3
    a = ListNode(1)
    b = ListNode(2)
    c = ListNode(3)
    a.next = b
    b.next = c
    print(a) # a is 1 -> 2 -> 3
    b.next = None
    print(a) # a is 1 -> 2
    b = None
    print(a) # a is still 1 -> 2, why changing b doesn't change a, but changing b.next changes a???

Suppose I have a linked list a -> b -> c. When I set b.next = None, a.next.next = None. However, the thing that confuses me is that, when I set b = None, a.next doesn't become None.What's the difference between operating b and b.next, why they have different influence on a?

Upvotes: 1

Views: 1782

Answers (3)

Samwise
Samwise

Reputation: 71574

Drawing diagrams helps. Here's your linked list:

[   ]
  |
  v
[   ]
  |
  V
[   ]
  |
  V
 None

Each arrow leading from a box represents the next attribute of that node.

Here are the three variables a, b, and c:

         [   ] <-- a
           |
           v
         [   ] <-- b
           |
           V
         [   ] <-- c
           |
           V
          None

Each of these variables also points to a particular node.

If you say b.next = None, the next attribute of the node referenced by b is modified, like this:

         [   ] <-- a
           |
           v
None <-- [   ] <-- b


         [   ] <-- c
           |
           V
          None

This modifies the structure of the list. If you just set b itself to a different value, though, this is what happens:

         [   ] <-- a
           |
           v
None <-- [   ]     b --> None


         [   ] <-- c
           |
           V
          None

You changed b, but the node that b used to point to stays right where it was. Note that this is similar to how the c node continued to exist even after you set b.next = None.

Upvotes: 5

chepner
chepner

Reputation: 532538

a is a reference to ListNode(1). There are two references to ListNode(2): the one stored in ListNode(1), referenced as a.next, and one in b.

Think of these references as arrows.

When you make the assignment b = None, you simply removing the arrow from b to ListNode(2) and replacing it with an arrow from b to None. This has no effect on the arrow from ListNode(1) to ListNode(2).

If you were instead to make a change to, say, ListNode(3), then that change would be visible from all three references to it: a.next.next, b.next, and c.

Note that an assignment like b.next = ... is very different from b = .... The latter is a "true" assignment, while the former is special syntax for a function call like setattr(b, 'next', ...). It modifies some object (specifically, the value of once of its attributes) in place, rather than just making a name point to something else.

Upvotes: 1

Dragonborn
Dragonborn

Reputation: 1815

Python doesn't have double pointers e.g. **x

b.next = c
print(a) # a is 1 -> 2 -> 3
b.next = None

E.g. in above, it doesn't mean c is None

When a.next is b, if you change a.next.next you are effectively changing b.next

But if you change a.next to None, it will not set b to None

Edit:

Also when you set b = None but a.next still points ListNode(2)

Upvotes: 1

Related Questions