Linked List implementation in Python

Question

I'm a data scientist attempting to build stronger CS fundamentals, particularly in Data Structures & Algorithms.

Below is my attempt at implementing a Singly Linked List. Looking for advice regarding:

1. Code style
2. Can space/time complexity of methods be improved?
3. Debugging in case I missed any edge cases
4. Checking for premature optimizations

Demonstrates implementation of a linked list and helper Node class

class Node:
 def __init__(self, value=None):
 self.value = value
 self.next = None
class Linkedlist:
 def __init__(self, *args):
 self.head = Node()
 self.tail = self.head
 self.size = 0
 # Nodes indexes defined from 0, 1, ..., N - 1 (where N = self.size) but are counted as First Node, Second Node, ..., Nth-Node respectively
 self._args = args
 if len(self._args) > 0:
 for val in self._args:
 self.append(val)
 def __len__(self):
 return self.size
 def _get_prev_node(self, index):
 """gets Node previous to given index
 i.e. if index is 1, will return Node 0 (1st Node)
 i.e. if size of linked list is 6 & index is -3, will return Node 3 (4th Node)
 """
 if index < 0:
 index += self.size
 cur_node = self.head
 prev_node_number = 1
 while prev_node_number < index:
 cur_node = cur_node.next
 prev_node_number += 1
 return cur_node
 def __getitem__(self, index):
 if index >= self.size or index < -self.size:
 raise IndexError
 elif index == 0 or index == -self.size:
 return self.head.value
 else:
 prev_node = self._get_prev_node(index)
 cur_node = prev_node.next
 return cur_node.value
 def __delitem__(self, index):
 if index >= self.size or index < -self.size:
 raise IndexError
 elif index == 0 or index == -self.size:
 self.head = self.head.next
 else:
 prev_node = self._get_prev_node(index)
 prev_node.next = prev_node.next.next
 if index == -1 or index == self.size - 1:
 self.tail = prev_node
 self.size -= 1
 def __repr__(self):
 values = []
 cur_node = self.head
 for _ in range(self.size):
 values.append(str(cur_node.value))
 cur_node = cur_node.next
 return ' -> '.join(values)
 def append(self, value):
 if self.head.value is None:
 self.head.value = value
 else:
 new_node = Node(value)
 self.tail.next = new_node
 self.tail = new_node
 self.size += 1
 def prepend(self, value):
 if self.head.value is None:
 self.head.value = value
 else:
 new_node = Node(value)
 new_node.next = self.head
 self.head = new_node
 self.size += 1
 def insert(self, value, index):
 # Inserts node with value before given index
 if abs(index) > self.size:
 raise IndexError
 elif index == 0 or index == -self.size:
 self.prepend(value)
 elif index == self.size:
 self.append(value)
 else:
 prev_node = self._get_prev_node(index)
 new_node = Node(value)
 new_node.next = prev_node.next
 prev_node.next = new_node
 self.size += 1
def main():
 def disp_attributes(lnk_list_obj):
 print(f'Linked List: {lnk_list_obj}')
 print(f'\tSize: {len(lnk_list_obj)}')
 print(f'\tHead node value: {lnk_list_obj.head.value}')
 print(f'\tTail node value: {lnk_list_obj.tail.value}')
 print('<< Instantiate empty Linked List >>')
 lnk = Linkedlist()
 disp_attributes(lnk)
 print('<< Append -3, 1, 0 to Linked List >>')
 values = -3, 1, 0
 for val in values:
 lnk.append(val)
 disp_attributes(lnk)
 print('<< Prepend -12 to Linked List >>')
 lnk.prepend(-12)
 disp_attributes(lnk)
 print(f'Linked List value at first Node: {lnk[0]}')
 print('<< Instantiate Linked List with values 1, -2, -6, 0, 2 >>')
 lnk2 = Linkedlist(1, -2, -6, 0, 2)
 disp_attributes(lnk2)
 print('<< Prepend 6 to Linked List >>')
 lnk2.prepend(6)
 disp_attributes(lnk2)
 print(f'Linked List value at second Node: {lnk2[1]}')
 print('<< Delete First Node >>')
 del lnk2[0]
 disp_attributes(lnk2)
 print('<< Delete Last Node >>')
 del lnk2[-1]
 disp_attributes(lnk2)
 print('<< Append 7 to LinkedList >>')
 lnk2.append(7)
 disp_attributes(lnk2)
 print('<< Delete 3rd Node >>')
 del lnk2[2]
 disp_attributes(lnk2)
 print('<< Insert -10 before 2nd Node >>')
 lnk2.insert(-10, 1)
 disp_attributes(lnk2)
if __name__ == '__main__':
 main()

• AJNeufeld: You are not allowed to significantly change your question post after someone posts an answer. Doing so can invalidate answers. See what should I do when someone answers for ways you can continue a review after incorporating suggested changes.
• Heslacher: I have rolled back your last edit. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .
• Vivek Jha: @AJNeufeld I have made edits according to your above comments and have created a new question here Singly Link List edits

Answer 1

You should add """docstrings"""" for each public class and method, describing what it does and how to use it.

---

class Node

This class has members value and next, which are not for use outside of the linked list implementation. You should rename these member to _value and _next, to indicate they are "private".

Actually, Node itself is an implementation detail of the LinkedList, so you could name it class _Node, and/or encapsulate it within the LinkedList class itself.

class LinkedList:
 """
 A data structure providing O(1)-time insertion/deletion of items
 to/from the head and tail of the list.
 """
 class _Node:
 def __init__(self, value=None):
 self._value = value
 self._next = None
 # ... remainder of LinkedList class ...

Consider using __slots__ to make you Node class faster and consume less memory:

 class _Node:
 __slots__ = ('_value', '_next')
 def __init__(self, value=None):
 self._value = value
 self._next = None

---

class LinkedList

Why are you storing self._args = args in the constructor? It is never used later on, so is just wasted storage. The if statement is unnecessary, if args is an empty list, iterating over it will iterate zero times. Simply use:

 for val in args:
 self.append(val)

---

Your indexing is complex enough for a special comment describing how they work, so they are complex enough to benefit from a common normalization function. Then you wouldn't need to always test for two values (if index == value or index == value - self.size:); just the one normalized value can be used (if index == value:).

---

Iteration

Something that is always done for collections is iterating over all elements. You should define an __iter__(self) method which returns an iterator for the collection.

Since iteration over a collection can be non-deterministic if the collection changes during iteration, you should track the number of times the collection is modified (insert/remove), memorize that value in the iterator when it is first created, and fast-fail the iterator if the value changes.

---

__repr__(self):

Called by the repr() built-in function to compute the "official" string representation of an object. If at all possible, this should look like a valid Python expression that could be used to recreate an object with the same value (given an appropriate environment). If this is not possible, a string of the form <...some useful description...> should be returned.

Your repr method could use values.append(repr(cur_node.value)) and return 'LinkedList(' + ', '.join(values) + ')' to return a more compliant representation.

Or you could rename the method to __str__(self), and leave the body unchanged.

• Vivek Jha: Thank you for your quick response. I agree with all your points, made the edits you suggested, and learned about __slots__, but struggled a bit with the iteration protocol. Is my implementation O(n^2)? If so, is there a simple way to make iteration in linear time that I'm missing? Also, I feel I didn't account for the collection changing during iteration?