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

Question

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?

You don't really have a linked list data structure. You have a ListNode class whose instances can be used to build a linked list, but no class that encapsulates the idea of a linked list and provides methods like append, insert, find, remove, etc. — chepner
– chepner, Commented May 27, 2021 at 19:45
As for your actual question, read nedbatchelder.com/text/names.html. Assignments never change existing values, only the name being assigned to. — chepner
– chepner, Commented May 27, 2021 at 19:46
Yeah, so maybe the question is about the ListNode structure? I just don't understand why changing b and b.next has different influence a — Francis
– Francis, Commented May 27, 2021 at 19:47
Because assigning to b has no effect on other references to the same object. — chepner
– chepner, Commented May 27, 2021 at 19:48
The way to read the first binding a.next = b is "make a.next point at the same thing b is pointing at currently", and then the second binding b = None should be read as "make b point to nothing now". Read this way, it makes it a bit more clear that the second binding has no influence on a.next. — Paul M.
– Paul M., Commented May 27, 2021 at 19:53

Samwise · Accepted Answer · 2021-05-27 21:27:49Z

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.

Dragonborn · Accepted Answer · 2021-05-27 19:48:22Z

1

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)

answered May 27, 2021 at 19:48

Dragonborn

1,8151 gold badge18 silver badges37 bronze badges

Comments

chepner · Accepted Answer · 2021-05-27 19:55:02Z

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.

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related