Implementation of Singly Linked List

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

Note this is an edit from the original post: Linked List implementation in Python

Have made the following edits to the code according to the answer by @AJNeufeld:

1. Made Node class & its attributes private
2. Added __slots__ to save memory
3. Added docstrings for all methods - including one for class that explains the assumed structure and indexing
4. Removed unnecessary attribute self._args
5. Added private helper methods:
   1. _is_head(self, index)
   2. _is_tail(self, index)
   3. _get_values(self)
6. Made __repr__(self) in accordance with Python Standard
7. Added __str__(self) to represent "Linking values"
8. Added iteration protocol
   • I think the way I built it is O(n^2) and wondering if there is a faster implementation?
   • I did not account for the container size changing through iteration? Any hints on this?
   • Also is anything ever put in the __iter__(self) method, or should it just trivially return the object?

Please find below the new implementation

class Linkedlist:
 """A linear container data structure that provides O(1) time insertion/deletion of items
 to/from the head and tail of the sequence of values.
 Utilizes _Node object as underlying data structure
 ----------------------------------------------------
 Structure of class is as follows:
 Index 0: 1st Node <- Head Node
 Index 1: 2nd Node
 Index 2: 3rd Node
 ...
 Index n - 1: Nth Node <- Tail Node
 ----------------------------------------------------
 Methods:
 1). __getitem__(self, index)
 Time Complexity: O(n)
 Space Complexity: O(1)
 2). __delitem__(self, index)
 Time Complexity: O(n)
 Space Complexity: O(1)
 3). __iter__(self)
 Time Complexity: O(n^2)
 Space Complexity: O(1)
 4). __repr__(self)
 Time Complexity: O(n)
 Space Complexity: O(n)
 5). __str__(self)
 Time Complexity: O(n)
 Space Complexity: O(n)
 6). append(self, value)
 Time Complexity: O(1)
 Space Complexity: O(1)
 7). prepend(self, value)
 Time Complexity: O(1)
 Space Complexity: O(1)
 8). insert(self, value, index)
 Time Complexity: O(n)
 Space Complexity: O(n)
 """
 class _Node:
 """Data structure used to implement Linked List - has fields:
 1. Data value
 2. Pointer to next node
 """
 def __init__(self, value=None):
 __slots__ = ('_value', '_next')
 self._value = value
 self._next = None
 def __init__(self, *args):
 self.head = self._Node()
 self.tail = self.head
 self._size = 0
 self._iter_counter = 1
 for val in args:
 self.append(val)
 def __len__(self):
 """Returns number of non-empty nodes in Linked List"""
 return self._size
 def _get_prev_node(self, index):
 """helper method to obtain Node previous to given index in O(n) time
 i.e. if index is 1, will return 1st Node
 i.e. if size of linked list is 6 & index is -3, will return 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 _is_head(self, index):
 """Helper method to determine if given index is head node"""
 if index >= self._size or index < -self._size:
 raise IndexError
 return index == 0 or index == -self._size
 def _is_tail(self, index):
 """Helper method to determine if given index is tail node"""
 if index >= self._size or index < -self._size:
 raise IndexError
 return index == -1 or index == self._size - 1
 def _get_values(self):
 """Helper method to generate string values of all node values"""
 cur_node = self.head
 for _ in range(self._size):
 yield str(cur_node._value)
 cur_node = cur_node._next
 def __getitem__(self, index):
 """Getter method to obtain value of a node at given index in O(1) time - this is considering that finding the node is encapsulated by helper method self._get_prev_node(index)
 """
 if self._is_head(index):
 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):
 """Method to delete value of a node at given index in O(1) time - this is considering that finding the node is encapsulated by helper method self._get_prev_node(index)
 """
 if self._is_head(index):
 self.head = self.head._next
 else:
 prev_node = self._get_prev_node(index)
 prev_node._next = prev_node._next._next
 if self._is_tail(index):
 self.tail = prev_node
 self._size -= 1
 def __iter__(self):
 """Returns iterator object which user can iterate through"""
 return self
 def __next__(self):
 """Loops through iterator returning each Node value"""
 # TODO See if there's a way to improve iteration speed from quadratic to linear
 cur_node = self.head
 if self._iter_counter > self._size:
 self._iter_counter = 1
 raise StopIteration
 prev_node = self._get_prev_node(self._iter_counter)
 self._iter_counter += 1
 return prev_node._value
 def __repr__(self):
 """Provides valid Python expression that can be used to recreate an object with the same value"""
 values = ', '.join(self._get_values())
 cls_name = type(self).__name__
 return f'{cls_name}({values})'
 def __str__(self):
 """Displays printable representation of Linked List"""
 return ' -> '.join(self._get_values())
 def append(self, value):
 """Inserts node with given value to end of Linked List in O(1) time"""
 if self.head._value is None:
 self.head._value = value
 else:
 new_node = self._Node(value)
 self.tail._next = new_node
 self.tail = new_node
 self._size += 1
 def prepend(self, value):
 """Inserts node with given value to front of Linked List in O(1) time"""
 if self.head._value is None:
 self.head._value = value
 else:
 new_node = self._Node(value)
 new_node._next = self.head
 self.head = new_node
 self._size += 1
 def insert(self, value, index):
 """Inserts node with given value at a given index of Linked List in O(n) time.
 If insertion occurs at head or tail of Linked List, operation becomes O(1).
 n := len(self)
 * Index must be in interval [-n, n]
 """
 if abs(index) > self._size:
 raise IndexError
 elif self._is_head(index):
 self.prepend(value)
 elif index == self._size:
 self.append(value)
 else:
 prev_node = self._get_prev_node(index)
 new_node = self._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 1st 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()

Answer 1

I think you’ve misunderstood the purpose of """docstrings""". If someone using your code types help(LinkedList), they will get the contents of the class’s docstring and the public member docstrings, formatted together into one long output string describing (ideally) how to use the class and its member functions. The internal details of how the class works should not be included.

Moreover, the class docstring should not repeat the information given in a member function. For example, you don’t need to document LinkedList.append in the LinkedList docstring, because help(LinkedList) automatically also output the help for help(LinkedList.append).

---

Yes, your __iter__ implementation is \$O(n^2)\$. Instead of returning an iterator Object, you’ve returned the original list, and made the original list implement the iterator protocol. This means you cannot have two iterators going at the same time. Also, you cannot iterate halfway through the list, stop and then start a new iteration from the beginning.

You should either create a new class LinkedList._Iter object (which implements the iterator protocol) and return that from __iter__ or, use the same technique you used in _get_values() and return a generator that yields successive values from the list. In either case, these returned objects/generators would be independent; you could have multiple iterations running separately, and/or abandoned halfway through iteration without messing up future iterations.

---

Edge case:

• start with empty list: head = tail = empty-node
• append one item: head = tail = node-with-value
• delete element 0: head = None; tail = node-with-value
• every subsequent operation (other than len()) will now raise an exception due to referencing an attribute of self.head, which is now None.