# Linked List implementation in Python

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

def __init__(self, *args):
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
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:
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:
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 = []
for _ in range(self.size):
values.append(str(cur_node.value))
cur_node = cur_node.next
return ' -> '.join(values)

def append(self, value):
else:
new_node = Node(value)
self.tail.next = new_node
self.tail = new_node
self.size += 1

def prepend(self, value):
else:
new_node = Node(value)
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'\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[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()
• 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. Commented Nov 7, 2018 at 6:49
• 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. Commented Nov 7, 2018 at 7:02
• @AJNeufeld I have made edits according to your above comments and have created a new question here Singly Link List edits Commented Nov 8, 2018 at 7:27

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.

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

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.

• 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? Commented Nov 7, 2018 at 6:13