# Python Singly Linked List Implementation

This is a follow-up to a question I asked a few days ago. I incorporated many of the suggestions on how to make the code more standardized and Python-like. If you see something else that can be improved, please let me know.

In addition, I also wrote unit tests. Could someone tell me how I am doing with those? Can I improve those somehow? Are they covering most use cases?

class LinkedList(object):
class Node(object):
"""
Inner class of LinkedList. Contains a blueprint for a node of the LinkedList
"""
def __init__(self, value, next=None):
"""
"""
self.value=value
self.next=next

def __eq__(self,other):
"""
Defining comparison between nodes for unit testing
"""
if self.value == other.value and self.next == other.next:
return True
else:
return False

def __init__(self):
"""
"""

def __len__(self):
"""
Returns the current size of the list. O(n), linear time
"""
count = 0
while current:
count += 1
current = current.next
return count

def __contains__(self,value):
"""
Returns True or False depending on whether an item with
node.value = value is in the list
"""
found = False
if current.value == value:
found = True
return True
else:
current = current.next
if not current:
return False

def __bool__(self):
"""
Implements boolean check of the class
"""
if self.__len__() == 0:
return False
else:
return True

def __iter__(self):
"""
Creates an iterator. Returns itself.
"""
return self

def __next__(self):
"""
Provides the next entry to the iterator
"""
if not self.__current:
raise StopIteration
else:
current = self.__current
self.__current=self.__current.next
return current

def __str__(self):
"""
Prints the current list in the form of a Python list
"""
toPrint = []
while current:
toPrint.append(current.value)
current = current.next
return str(toPrint)

def insert(self, value, position=0):
"""
in O(1) time or to position in the list in O(n) time
"""
if value is None:
raise ValueError('Cannot add None item to a list')
if position < 0:
raise ValueError('Cannot add to negative position in the list')
if position == 0:
return self.node
else:
count = 0
while current and ((count+1)<=position):
#found the position to insert into
if count + 1 == position:
self.node = self.Node(value, current.next)
current.next = self.node
return self.node
else:
current = current.next
count += 1
if not current:
return None

def search(self, value):
"""
Searches the list for a node with payload v. Returns the node object or None if not found. Time complexity is O(n) in worst case.
"""
found = False
if current.value == value:
found = True
else:
current = current.next
if not current:
return None
return current

def delete(self, value):
"""
Searches the list for a node with payload v. Returns the node object or None if not found. Time complexity is O(n) in worst case.
"""
if value is None:
raise ValueError('Cannot remove None item from the list')
previous = None
found = False
if current.value == value:
found = True
else:
previous = current
current = current.next
# nothing found, return None
if not current:
return None
# the case where first item is being deleted
if not previous:
# item from inside of the list is being deleted
else:
previous.next = current.next

return current


Tests:

import unittest

def setUp(self):

def test_init(self):
self.assertEqual(len(self.linked_list), 0, "Initial length should be zero")

def test_insert(self):
self.assertEqual(self.linked_list.insert(1), self.linked_list.Node(1, None), "Inserting 1 into list should return node with value=1")

def test_contains(self):
self.assertEqual(1 in self.linked_list, True, "After inserting 1 into the list, we should be able to find it there")
self.assertEqual(4 in self.linked_list, False, "After inserting 1 into the list, we should be able to find it there")

def test_search(self):
self.assertEqual(self.linked_list.search(2).value, self.linked_list.Node(2, None).value, "Searching for 2 in [3,2,1] should return node with value=2")
self.assertEqual(self.linked_list.search(4), None, "Searching for 4 in [3,2,1] should return None")

def test_delete(self):
self.assertEqual(self.linked_list.delete(2).value, self.linked_list.Node(2, None).value, "Deleting 2 from [3,2,1] should return the node with value 2")

if __name__ == '__main__':
unittest.main()


PEP8

While your code follows PEP8 principles there are few missing whitespaces around operators, this is a minor thing, but you should fix it.

Class Node

def __init__(self, value, next=None):
"""
"""
self.value=value
self.next=next


next is not the best name for a parameter since it shadows built-in function next consider using other name, e.g _next. Also, you have missing whitespaces around operator =

def __eq__(self,other):
"""
Defining comparison between nodes for unit testing
"""
if self.value == other.value and self.next == other.next:
return True
else:
return False


Can be simplified to:

def __eq__(self,other):
"""
Defining comparison between nodes for unit testing
"""
return self.value == other.value and self.next == other.next:


def __contains__(self,value):
"""
Returns True or False depending on whether an item with
node.value = value is in the list
"""
found = False
if current.value == value:
found = True
return True
else:
current = current.next
if not current:
return False


can be simplified to:

def __contains__(self,value):
"""
Returns True or False depending on whether an item with
node.value = value is in the list
"""
while current:
if current.value == value:
return True
current = current.next
return False


method __bool__:

def __bool__(self):
"""
Implements boolean check of the class
"""
if self.__len__() == 0:
return False
else:
return True


In this particular case, you don't really have to define it, since if this method is not defined python will call __len__ and checks for a non-zero value, this is basically what your implementation does, so you might want to drop it.

method __next__:

You can actually get rid of this by moving logics to __iter__ and making it a generator. E.G:

def __iter__(self):
while self.__current:
current = self.__current
self.__current = self.__current.next
yield current



But if you want to keep your implementation then you don't need else part of statement

def __next__(self):
"""
Provides the next entry to the iterator
"""
if not self.__current:
raise StopIteration
current = self.__current
self.__current=self.__current.next
return current


method __str__:

rename variable toPrint, python does not use camelcase, but underscode, see PEP8

method search:

you can do pretty much same modification as in __contains__

Other improvements:

1. You can store a length of your list in the object, so whenever you add/remove an item it will increase/decrease a counter. This will make your __len__ O(1) speed and will also improve speed of insert in case if position is out of borders of your list

2. Think about defining a iterator for your object as a separate class, in your current implementation your list stores it's current position. So it might be possible that it will be changed in some other part of your code and your iteration might skip elements because of that.

• Much appreciated! All good suggestions :-) Mar 7, 2017 at 13:41
• By the way, would you suggest a good way to unit-test the iterator method? Mar 14, 2017 at 16:00
• @MadPhysicist as a solution, you can add say 3 Nodes to your list, and then do assert [Node1, Node2, Node3] == list(your_list_object)
– Alex
Mar 14, 2017 at 16:23
• @MadPhysicist yes, it will iterate over iterable and store results to list.
– Alex
Mar 14, 2017 at 16:30
• The following worked: def test_list(self): node1 = self.linked_list.Node(1,None) node2 = self.linked_list.Node(2,node1) node3 = self.linked_list.Node(3,node2) self.linked_list.insert(1) self.linked_list.insert(2) self.linked_list.insert(3) self.assertEqual([node3,node2,node1], list(self.linked_list)) Mar 14, 2017 at 16:38