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.