Python Singly Linked List Implementation

Question

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):
 """
 Initializes a List node with payload v and link n
 """
 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):
 """
 Initializes a LinkedList and sets list head to None
 """
 self.head=None
 self.__current=self.head
 def __len__(self):
 """
 Returns the current size of the list. O(n), linear time
 """ 
 current = self.head
 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 
 """
 current = self.head
 found = False
 while current and not found:
 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:
 self.__current=self.head
 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 
 """
 current = self.head
 toPrint = []
 while current:
 toPrint.append(current.value)
 current = current.next
 return str(toPrint) 
 def insert(self, value, position=0):
 """
 Adds an item with payload v to beginning of the list
 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:
 self.node = self.Node(value, self.head)
 self.head = self.node
 self.__current=self.head
 return self.node
 else:
 current = self.head
 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.
 """
 current = self.head
 found = False
 while current and not found:
 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')
 current = self.head
 previous = None
 found = False
 while current and not found:
 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:
 self.head = current.next
 # item from inside of the list is being deleted 
 else:
 previous.next = current.next
 return current

Tests:

import unittest
from lists import LinkedList
class TestLinkedList(unittest.TestCase):
 linked_list=None
 def setUp(self):
 self.linked_list = LinkedList()
 def test_init(self):
 self.assertEqual(self.linked_list.head, None, "Initial HEAD should be None")
 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")
 self.assertEqual(list(self.linked_list),[self.linked_list.Node(1)], "Inserting 1 into empty list should give [1]")
 self.linked_list.insert(3,1)
 self.assertEqual(self.linked_list.head.next, self.linked_list.Node(3, None), "Inserting 3 into pos=1 of [1] should give [1,3]")
 self.linked_list.insert(2,1)
 self.assertEqual(self.linked_list.head.next.value, self.linked_list.Node(2, None).value, "Inserting 2 into pos=1 of [1,3] should give [1,2,3]")
 def test_contains(self):
 self.linked_list.insert(1)
 self.linked_list.insert(2)
 self.linked_list.insert(3)
 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")
 #print(self.linked_list)
 def test_search(self):
 self.linked_list.insert(1)
 self.linked_list.insert(2)
 self.linked_list.insert(3)
 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.linked_list.insert(1)
 self.linked_list.insert(2)
 self.linked_list.insert(3)
 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")
 self.linked_list.delete(3)
 self.assertEqual(self.linked_list.head, self.linked_list.Node(1, None), "Deleting 2 and 3 from [3,2,1] should leave the list as [1]")
if __name__ == '__main__':
 unittest.main()

Answer 1

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):
 """
 Initializes a List node with payload v and link n
 """
 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:

Class LinkedList

def __contains__(self,value):
 """
 Returns True or False depending on whether an item with
 node.value = value is in the list
 """
 current = self.head
 found = False
 while current and not found:
 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
 """
 current = self.head
 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
 self.__current=self.head

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:
 self.__current=self.head
 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.

• MadPhysicist: Much appreciated! All good suggestions :-)
• MadPhysicist: By the way, would you suggest a good way to unit-test the iterator method?
• Alex: @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: @MadPhysicist yes, it will iterate over iterable and store results to list.
• MadPhysicist: 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))