I’m learning Singly Linked List in university and I’m quite struggling with this data structure.
Here is my implementation:
from typing import Optional
class Node:
def __init__(self, data):
self.data = data
self.next: Optional[Node] = None
def __getitem__(self):
return self.data
def set_current(self, new_data):
self.data = new_data
def get_next(self):
return self.next
def set_next(self, next_data):
self.next = next_data
class SinglyLinkedList:
# Function to initialize head
def __init__(self):
self.head: Optional[Node] = None
def __len__(self):
head = self.head
count = 0
while head:
count += 1
head = head.next
return count
def __repr__(self):
head = self.head
node = []
while head:
node.append(head.data)
head = head.next
node.append("None")
return " -> ".join(map(str, node))
def __iter__(self):
node = self.head
while node:
yield node
node = node.next
def isempty(self):
return self.head == None
# def append(self, node: Optional[Node]):
def prepend(self, node: Node):
node.next = self.head
self.head = node
def append(self, node: Node):
"""
append is a function to add a new node into the tail of linked list
Time complexity: O(n)
Space complexity: O(1)
"""
head = self.head
if head is None:
head = node
self.head = head
else:
for current_node in self:
head = current_node
head.next = node
def pop_first(self):
if self.head is None:
print("The list is blank")
else:
self.head = self.head.next
def pop_last(self):
if self.head == None:
print("The list is empty")
else:
if self.head.next == None:
self.head = None
else:
head = self.head
while head.next.next is not None:
head = head.next
head.next = None
if __name__ == "__main__":
sllist = SinglyLinkedList()
sllist.prepend(Node(3))
sllist.append(Node(2))
sllist.append(Node(20))
sllist.append(Node(18))
print(f"Original list: {sllist}")
sllist.pop_last()
print(f"After pop_last: {sllist}")
The function pop_last works fine to me but the linter seems to angry about that
The head attribute of a SinglyLinkedList object can be of type None or Node
Similarly the next attribute of a Node object can be of type None or Node
You correctly type-annotated them this way: Optional[Node]
Static type checkers like mypy or pyright are not able to recognize all conditions narrowing the possible type of an expression. In your case it did not eliminate the possibility for head.next to be None.
I would try the following:
Fix the test for None: if self.head.next == None: → if self.head.next is None:
If it does not help, assert the type before the problematic statement: assert head.next is not None
Other notes:
When using type annotation we normally type-annotate attributes right in the class body like this:
class Node:
data: Any
next: Optional[Node]
In this case you refer to the class itself. You can take care of that problem by activating the postponed evaluation of annotations (which will be active in future versions) by adding this at the beginning of the file: from __future__ import annotations
One additional advantage of that is that you will be able to use newer typing features in all older supported Python versions (Python 3.7+) like Node | None instead of Optional[Node].
Instead of printing messages about exceptional situations your methods should probably raise an exception or return a special value.
Should not the pop_* functions return the popped value?
First, I will considered to add the return value for pop_* function.
Second, I prefer the Optional[Node] annotation to Node | None because it’s easier for me to remember like the Option type in Haskell and Rust. Anyway I will try to change my thought and adapt new annotation.
I added assert head.next is not None and it works but still has 1 more error.
You are still using something == None instead of something is None. This was the first step of possible fixing the problem. Maybe this fix alone will make the type narrowing working.
Optional is a shorthand of a special case of Union. Optional[Node] is equivalent to Union[Node, None] which is equivalent to the new syntax Node | None.
AFAIK Union or Optional are not (yet) planned to be deprecated. You can use them if you feel comfortable using them.
def pop_last(self):
if self.head is None:
return None
else:
if self.head.next is None:
self.head = None
else:
head = self.head
assert isinstance(head, Node)
assert isinstance(head.next, Node)
while head.next.next is not None:
assert isinstance(head, Node)
head = head.next
assert isinstance(head, Node)
term = head.next
head.next = None
self.size -= 1
return term
As I wrote you need to narrow the type before the problematic places where the simplistic type checker complains. For loops this means both before the loop and inside the loop (of course before it loops again). Demonstration with a code of a similar logic as your loop:
def counter_operation(counter: int | None) -> int | None:
"""Provide a meaningless operation just to help the demonstration."""
if counter is None:
return 0
if counter > 10:
return None
return counter + 1
counter: int | None = None
counter = counter_operation(counter)
while counter < 5:
counter = counter_operation(counter)
With type narrowing (when you know that the asserts will be True):
counter: int | None = None
counter = counter_operation(counter)
assert counter is not None
while counter < 5:
counter = counter_operation(counter)
assert counter is not None
def pop_last(self):
if self.head is None:
return None
else:
if self.head.next is None:
self.head = None
else:
head = self.head
assert isinstance(head.next, Node)
while head.next.next is not None:
head = head.next
assert isinstance(head.next, Node)
term = head.next
head.next = None
self.size -= 1
return term
