The short answer to this is that, Python is a pass-by-object-reference language, not pass-by-reference as implied in the question. It means that:
resultandresult_tailare two variables that happen to point at the same value- Mutation / Changing of the underlying value (
result_tail.next = ListNode(1)) will affect the value shown byresult - However, assigning / pointing the variable
result_tailto another value will NOT affect the value ofresult result_tail = result_tail.nextis assigning the next node of the node that is currently assigned by the variable
The following is an visualization of the values that are assigned to the variables (r = result, rt = result_tail):
result = ListNode(0)
#r
#0 -> None
result_tail = result
#r
#0 -> None
#rt
result_tail.next = ListNode(1)
#r
#0 -> 1 -> None
#rt
result_tail = result_tail.next
#r
#0 -> 1 -> None
# rt
result_tail.next = ListNode(2)
#r
#0 -> 1 -> 2 -> None
# rt
result_tail = result_tail.next
#r
#0 -> 1 -> 2 -> None
# rt
References for additional reading:
- An article explaining the Python pass-by-object reference style in detail https://robertheaton.com/2014/02/09/pythons-pass-by-object-reference-as-explained-by-philip-k-dick/
- An answer explaining Python's pass-by-object reference style https://stackoverflow.com/a/33066581/12295149
- Question asking on Python's object reference style Understanding Python's call-by-object style of passing function arguments
The short answer to this is that, Python is a pass-by-object-reference language, not pass-by-reference as implied in the question. It means that:
resultandresult_tailare two variables that happen to point at the same value- Mutation / Changing of the underlying value (
result_tail.next = ListNode(1)) will affect the value shown byresult - However, assigning / pointing the variable
result_tailto another value will NOT affect the value ofresult result_tail = result_tail.nextis assigning the next node of the node that is currently assigned by the variable
The following is an visualization of the values that are assigned to the variables (r = result, rt = result_tail):
result = ListNode(0)
#r
#0 -> None
result_tail = result
#r
#0 -> None
#rt
result_tail.next = ListNode(1)
#r
#0 -> 1 -> None
#rt
result_tail = result_tail.next
#r
#0 -> 1 -> None
# rt
result_tail.next = ListNode(2)
#r
#0 -> 1 -> 2 -> None
# rt
result_tail = result_tail.next
#r
#0 -> 1 -> 2 -> None
# rt
References for additional reading:
- An article explaining the Python pass-by-object reference style in detail https://robertheaton.com/2014/02/09/pythons-pass-by-object-reference-as-explained-by-philip-k-dick/
- An answer explaining Python's pass-by-object reference style https://stackoverflow.com/a/33066581/12295149
- Question asking on Python's object reference style Understanding Python's call-by-object style of passing function arguments
For those reading this in the future: I wanted to debug linked list problems on a local environment so here is what I did.
- Modified the Leetcode code for ListNode by including the dunder "repr" method. This is for when you want to print a ListNode to see what its value and next node(s).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __repr__(self):
return "ListNode(val=" + str(self.val) + ", next={" + str(self.next) + "})"
- Next, I made a recursive function that makes a nested ListNode when you pass in a list. This is so you can test your methods by passing in lists (instead of having to manually make a confusing looking ListNode yourself.
def list_to_LL(arr):
if len(arr) < 1:
return None
if len(arr) == 1:
return ListNode(arr[0])
return ListNode(arr[0], next=list_to_LL(arr[1:]))
- Here is an example that tests my answer for the "reverseList" problem:
def reverseList(head: ListNode) -> ListNode:
prev = None
while head:
next_node = head.next
head.next = prev
prev = head
head = next_node
return prev
# test cases
t1 = list_to_LL([1, 2, 3, 4, 5]) #ListNode(val=1, next={ListNode(val=2, next={ListNode(val=3, next={ListNode(val=4, next={ListNode(val=5, next={None})})})})})
t2 = list_to_LL([1, 2]) #ListNode(val=1, next={ListNode(val=2, next={None})})
t3 = list_to_LL([])
# answers
print(reverseList(t1))
print(reverseList(t2))
print(reverseList(t3))
Hello all, I completed my 12th this may( high school graduate ) going to attend Engineering classes from next month. So I decided to start LeetCode question. Till now I have completed about 13 questions which includes 9 easy ones, 3 medium ones and 1 hard question( in python language ) with whatever was thought to me in my school, but recently I see many questions in from ***ListNode***, but searching in youtube doesn't shows anything about ListNode but only about Linked list. So kindly suggest me or provide the resources to learn more about it.
Thank you!
Summary
I won't dwell on what has already been cited by users toolic and J_H, so I just have a few comments:
Type Hinting
I would suggest that you include type hinting, especially if your functions do not contain docstrings that describe the type of arguments being passed to functions (J_H has suggested this, so pardon if this is too repetitive).
Be More Tolerant of Errors in User Input
If the user does not enter a valid integer in function run_and_add, you essentially quit. You should instead put out the prompt again and give the user as many chances needed to enter valid input. The user can always terminate by entering Ctrl-C if they get stuck.
Strive for Encapsulation and Reusability
I can't stress too strongly that your code is crying out for you to create a LinkedList abstract data type that abstracts the notion of a linked list while encapsulating the actual implementation. To that end, I would use attribute names that begin with '_' where appropriate to suggest that they are "private" and not to be either updated nor depended on existing in the future (such as the next instance attribute of the ListNode class.
The following classes are just one possibility. Note:
- There is no
printmethod implemented since printing the entire list is trivial given that the class implements the iterator protocol. Besides, what if you wanted to print to a file? Then aprintmethod would require one or more additional arguments. - The client never explicitly creates
ListNodeinstances. - The linked list keeps explicit track of the final (last) node in the list to provide efficient appending of a node or an entire linked list to the end.
I can envision your using this as a starting point and potentially adding other methods (for example, __eq__ methods to compare nodes and linked lists).
"""A module for creating and manipulating linked lists."""
from abc import ABC, abstractmethod
from typing import TypeVar, Any
LinkedListInstance = TypeVar('LinedListInstance', bound='LinkedList')
class NodeType(ABC):
@property
@abstractmethod
def val(self):
pass
@val.setter
@abstractmethod
def val(self, val):
pass
class LinkedList:
class _ListNode(NodeType):
"""Initialize a new node with some value, val."""
def __init__(self, val):
self._val = val
self._next = None
@property
def val(self):
return self._val
@val.setter
def val(self, val):
self._val = val
def __repr__(self):
return f'_ListNode({repr(self._val)})'
def __str__(self):
return str(self._val)
def __init__(self):
"""Create a new, empty linked list."""
self._head = None
self._tail = None
def append_node(self, val: Any) -> LinkedListInstance:
"""Append a new node to the list initialized with val."""
new_node = LinkedList._ListNode(val)
if self._head is None:
self._head = new_node
else:
self._tail._next = new_node
self._tail = new_node
return self
def insert_node(self, at_node: NodeType, val: Any) -> LinkedListInstance:
"""Create and insert a new node after the specified at_node node initialized
with val."""
if at_node is self._tail: # special case
return self.append_node(val)
node_to_insert = LinkedList._ListNode(val)
node_to_insert._next = at_node._next
at_node._next = node_to_insert
return self
def append_list(self, linked_list: LinkedListInstance) -> LinkedListInstance:
"""Append a linked list to the current list."""
if self._head is None:
self._head = linked_list._head
else:
self._tail._next = self._head
self._tail = linked_list._tail
return self
def __iter__(self) -> NodeType:
"""Iterate the list."""
current = self._head
while current is not None:
yield current
current = current._next
if __name__ == '__main__':
def insert_node_at_position(linked_list: LinkedList, position: int) -> None:
for counter, current_node in enumerate(linked_list, start=1):
print(f"Node at position {counter}: {current_node}")
if counter == position:
while True:
try:
number = int(input("Please insert an Integer: "))
except ValueError:
print("Not an Integer")
else:
break
linked_list.insert_node(current_node, number)
print("Node added at position:", position)
print("Updated linked list:")
for node in linked_list:
print(node)
linked_list = LinkedList().append_node(1).append_node(2).append_node(3)
insert_node_at_position(linked_list, 2)
names
class ListNode:
This is a perfectly fine identifier, as-is.
There's no adjacent code that uses other node types.
Consider shortening to just Node.
design of Public API
OO
def print_linked_list(head):
...
def add_node(prev_node, node_to_add):
...
These are somewhat unexpected signatures,
the sort of thing I might expect in Fortran code.
ListNode turned out to be just a very brief
@dataclass,
with no OO
aspect to it.
Given a ListNode, we find no methods to call on it for list operations.
This works, but makes it a little harder for developers
and maintenance engineers to discover your API.
For example if I hit a breakpoint() I cannot p dir(node)
to find plausible things I might do with a node -- I instead
have to scour the codebase for such operations.
Also, your signatures lack ListNode type annotations,
so I can't just grep for that or use type-aware IDE features
to narrow my search.
I propose some more natural implementations.
def print_linked_list(self):
head = self
while head:
print(head.val)
head = head.next
def add_node(self, node_to_add):
assert node_to_add.next is None
node_to_add.next = self.next
self.next = node_to_add
Consider renaming these to simply .print() and .insert().
interactive input vs parameter
(I am paraphrasing, renaming the vague number to new_val.)
def run_and_add(head, position):
...
new_val = int(input("Please insert an Integer: "))
Prefer to place calls of input() further up in the call stack,
such as within def main():, and pass in such a value as a parameter:
def run_and_add(head, position, new_val):
main guard
On which topic, you don't have a main() function,
and you really need one.
Why?
So you or some maintenance engineer can safely import linkedlist
when exercising your functions in a
test suite.
Also, it's convenient to ensure that local variables like first
(which are not part of your exported Public API)
will disappear when they go out of scope.
That way such identifiers won't pollute the module namespace.
def main():
first = ListNode(1)
first.next = ListNode(2)
first.next.next = ListNode(3)
run_and_add(first, 2)
if __name__ == '__main__':
main()
single responsibility
run_and_add() is an awkward identifier, suggesting that instead of
one
we're doing two things.
Also I find "run" less than clear.
Consider making caller responsible for passing in an already-created node,
and then this could be a simple insert_at_position(head, position, new_node) function.