A few general things:
"""Doc strings.""" for documentation not
- Put a space after each comma
- Prefer less indentation. For example, if you have an
if blah: return None, then you don't need an
else after it, because if the function didn't return then
blah must've been false
- PEP8 prefers
snake_case for methods and variables.
setHead should be
set_head, although I'm a bit dubious that you should be exposing this to the user. The head should be a private implementation detail. You should expose methods to allow the user to modify the list instead.
- Additionally, for parity with builtin collection types, I'd take an optional iterable as the first argument to your constructor. If provided, you populate your collection with the values from it.
- I prefer
data again for parity with python builtins
A warning about equality:
cur == self.head. Depending on how equality is implemented for your nodes this may or may not work. In this situation, I think you are lucky to avoid this edge case due to delete removing the first thing, but in general this is dangerous. To test if two things are the exact same object use
== for equality.
(1, 2) == (1, 2) but
(1, 2) is not (1, 2).
Specifically relating to
- I'd rename it to
remove for parity with the method on the builtin list
- I'd have it raise a
ValueError when the value isn't in the list (again for parity with the method on the builtin list)
- Despite what @vnp suggests, I wouldn't return the value deleted again for parity with
remove on the builtin list. It doesn't really make much sense to return the value since you know it already (you passed it into the method). This is what
- Since many operations on the linked list require finding a node with a given value and the previous node (ex.
insert_before), I'd extract find value or
raise ValueError into a helper. This will cut down on the complexity of your delete operation (you now just have to stitch the hole in the list)
- You have some duplicated logic for setting
prev.next. No matter whether
cur.next is None or not you set
cur.next. But, I'd solve this another way:
- One trick commonly employed to make the linked lists a bit less unwieldy is always having an empty node at the head (with no data). This means that you never have to special case patching the head pointer.
Combining this all:
"""Node in SinglyLinkedList."""
def __init__(self, value, next):
self.value = value
self.next = next
def __init__(self, iterable=None):
"""New list initialized from optional iterable's items."""
self._head = Node(None, None)
# Not implemented here, but like list.append,
# should take ...args and append each. In this
# way you can do O(n) appends instead of O(n^2)
def remove(self, value):
"""Removes value from the list or raises ValueError."""
previous_node, matched_node = self._find_value(value)
previous_node.next = matched_node.next
def _find_value(self, value):
previous, current = self._head, self._head.next
while current is not None:
if current.value == value:
return previous, current
previous, current = current, current.next
raise ValueError(f'value not in list')