Implementation of Singly Linked List

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:
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

"""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._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
prev_node_number = 1
while prev_node_number < index:
cur_node = cur_node._next
prev_node_number += 1
return cur_node

"""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"""
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)
"""
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)
"""
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
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:
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:
else:
new_node = self._Node(value)
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
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'\tSize: {len(lnk_list_obj)}')
print(f'\tTail node value: {lnk_list_obj.tail._value}')

print('<< Instantiate empty Linked List >>')
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}')

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}')

print('<< Delete 1st Node >>')
del lnk2
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
disp_attributes(lnk2)

print('<< Insert -10 before 2nd Node >>')
lnk2.insert(-10, 1)
disp_attributes(lnk2)

if __name__ == '__main__':
main()

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.