Python LinkedList implementation and tests

Question

I'm implementing some basic data structures in Python. How does my LinkedList look like? My experience in testing is quite low and I would really appreciate a review.

Implementation:

class LinkedList:
 class Node:
 def __init__(self, value, next_node=None):
 self.value = value
 self.next = next_node
 def __eq__(self, other):
 return self.value == other.value and self.next == other.next
 EMPTY_LIST_ERROR_MSG = 'List is empty!'
 def __init__(self):
 self.__head = None
 def add_first(self, value):
 """ A -> B -> C -> D -> None
 E -> A -> B -> C -> D -> None"""
 new_node = self.Node(value=value)
 if self.__head:
 new_node.next = self.__head
 self.__head = new_node
 def add_last(self, value):
 """ A -> B -> C -> D -> None
 A -> B -> C -> D -> E -> None"""
 new_node = self.Node(value)
 last_node = None
 for node in self.__node_iter():
 last_node = node
 if last_node:
 last_node.next = new_node
 else:
 self.__head = new_node
 def insert_after(self, item, value):
 """Inserting F after C:
 A -> B -> C -> D -> None
 A -> B -> C -> F -> D -> None"""
 if not self.__head:
 raise IndexError(self.EMPTY_LIST_ERROR_MSG)
 node = self.__head
 while node and node.value != item:
 node = node.next
 if node:
 node_next = node.next
 node.next = self.Node(value, node_next)
 else:
 raise ValueError(f'No such item {item}')
 def remove(self, value):
 """ Removing C:
 A -> B -> C -> D -> None
 A -> B -> D -> None"""
 if not self.__head:
 raise IndexError(self.EMPTY_LIST_ERROR_MSG)
 if self.__head.value == value:
 self.remove_first()
 else:
 previous = self.__head
 node = self.__head.next
 while node and node.value != value:
 previous = node
 node = node.next
 if node:
 previous.next = node.next
 else:
 raise ValueError(f'No such value: {value}')
 def remove_first(self):
 """ A -> B -> C -> D -> None
 B -> C -> D -> None"""
 if not self.__head:
 raise IndexError(self.EMPTY_LIST_ERROR_MSG)
 self.__head = self.__head.next
 def remove_last(self):
 """ A -> B -> C -> D -> None
 A -> B -> C -> None"""
 if not self.__head:
 raise IndexError(self.EMPTY_LIST_ERROR_MSG)
 previous = None
 node = self.__head
 while node.next:
 previous = node
 node = node.next
 if previous:
 previous.next = None
 else:
 self.__head = None
 def reverse(self):
 """ A -> B -> C -> D -> None
 D -> C -> B -> A -> None"""
 previous = None
 node = self.__head
 while node:
 node_next = node.next
 node.next = previous
 previous = node
 node = node_next
 self.__head = previous
 def __node_iter(self):
 node = self.__head
 while node:
 yield node
 node = node.next
 def __contains__(self, item):
 for value in self:
 if item == value:
 return True
 return False
 def __len__(self):
 count = 0
 for _ in self:
 count += 1
 return count
 def __str__(self):
 return "[{}]".format(", ".join(map(str, self)))
 def __iter__(self):
 """:returns values iterator"""
 return iter(map(lambda node: node.value, self.__node_iter()))

Tests:

import pytest
from linear.linked_list import LinkedList
class TestLinkedList:
 def setup_method(self):
 """[12, 8, 2, 5]"""
 self.prepared_linked_list = LinkedList()
 self.prepared_linked_list.add_first(5)
 self.prepared_linked_list.add_first(2)
 self.prepared_linked_list.add_first(8)
 self.prepared_linked_list.add_first(12)
 assert list(self.prepared_linked_list) == [12, 8, 2, 5]
 def test_add_first(self):
 linked_list = LinkedList()
 linked_list.add_first(1)
 assert list(linked_list) == [1]
 linked_list.add_first(3)
 assert list(linked_list) == [3, 1]
 linked_list.add_first(5)
 assert list(linked_list) == [5, 3, 1]
 linked_list.add_first(4)
 assert list(linked_list) == [4, 5, 3, 1]
 def test_add_last(self):
 linked_list = LinkedList()
 linked_list.add_last(1)
 assert list(linked_list) == [1]
 linked_list.add_last(3)
 assert list(linked_list) == [1, 3]
 linked_list.add_last(5)
 assert list(linked_list) == [1, 3, 5]
 linked_list.add_last(4)
 assert list(linked_list) == [1, 3, 5, 4]
 def test_insert_after(self):
 self.prepared_linked_list.insert_after(2, 4)
 assert list(self.prepared_linked_list) == [12, 8, 2, 4, 5]
 self.prepared_linked_list.insert_after(2, 3)
 assert list(self.prepared_linked_list) == [12, 8, 2, 3, 4, 5]
 self.prepared_linked_list.insert_after(12, 1)
 assert list(self.prepared_linked_list) == [12, 1, 8, 2, 3, 4, 5]
 self.prepared_linked_list.insert_after(5, 50)
 assert list(self.prepared_linked_list) == [12, 1, 8, 2, 3, 4, 5, 50]
 with pytest.raises(ValueError):
 self.prepared_linked_list.insert_after(16, 40)
 linked_list = LinkedList()
 with pytest.raises(IndexError):
 linked_list.insert_after(5, 12)
 linked_list.add_first(3)
 linked_list.insert_after(3, 4)
 assert list(linked_list) == [3, 4]
 def test_remove_first(self):
 self.prepared_linked_list.remove_first()
 assert list(self.prepared_linked_list) == [8, 2, 5]
 self.prepared_linked_list.remove_first()
 assert list(self.prepared_linked_list) == [2, 5]
 self.prepared_linked_list.remove_first()
 assert list(self.prepared_linked_list) == [5]
 self.prepared_linked_list.remove_first()
 assert list(self.prepared_linked_list) == []
 with pytest.raises(IndexError):
 self.prepared_linked_list.remove_first()
 def test_remove_last(self):
 self.prepared_linked_list.remove_last()
 assert list(self.prepared_linked_list) == [12, 8, 2]
 self.prepared_linked_list.remove_last()
 assert list(self.prepared_linked_list) == [12, 8]
 self.prepared_linked_list.remove_last()
 assert list(self.prepared_linked_list) == [12]
 self.prepared_linked_list.remove_last()
 assert list(self.prepared_linked_list) == []
 with pytest.raises(IndexError):
 self.prepared_linked_list.remove_last()
 def test_remove(self):
 self.prepared_linked_list.remove(2)
 assert list(self.prepared_linked_list) == [12, 8, 5]
 self.prepared_linked_list.remove(12)
 assert list(self.prepared_linked_list) == [8, 5]
 with pytest.raises(ValueError):
 self.prepared_linked_list.remove(12)
 assert list(self.prepared_linked_list) == [8, 5]
 self.prepared_linked_list.remove(5)
 assert list(self.prepared_linked_list) == [8]
 self.prepared_linked_list.remove(8)
 assert list(self.prepared_linked_list) == []
 with pytest.raises(IndexError):
 self.prepared_linked_list.remove(8)
 def test_reverse(self):
 self.prepared_linked_list.reverse()
 assert list(self.prepared_linked_list) == [5, 2, 8, 12]
 linked_list = LinkedList()
 linked_list.reverse()
 assert list(linked_list) == []
 linked_list.add_first(5)
 linked_list.reverse()
 assert list(linked_list) == [5]
 def test_contains(self):
 assert 12 in self.prepared_linked_list
 assert 2 in self.prepared_linked_list
 assert 5 in self.prepared_linked_list
 assert 8 in self.prepared_linked_list
 assert 11 not in self.prepared_linked_list
 assert 28 not in self.prepared_linked_list
 linked_list = LinkedList()
 assert 5 not in linked_list
 linked_list.add_first(5)
 assert 5 in linked_list
 def test_len(self):
 assert len(self.prepared_linked_list) == 4
 self.prepared_linked_list.remove_last()
 assert len(self.prepared_linked_list) == 3
 self.prepared_linked_list.remove_first()
 assert len(self.prepared_linked_list) == 2
 self.prepared_linked_list.remove_first()
 assert len(self.prepared_linked_list) == 1
 self.prepared_linked_list.remove_last()
 assert len(self.prepared_linked_list) == 0
 def test_iter(self):
 assert next(iter(self.prepared_linked_list)) == 12
 iterator = iter(self.prepared_linked_list)
 assert next(iterator) == 12
 assert next(iterator) == 8
 assert next(iterator) == 2
 assert next(iterator) == 5
 with pytest.raises(StopIteration):
 next(iterator)

• Peilonrayz: Please fix the indentation in the first code block.

Answer 1

Error constants

There's less value in doing this:

EMPTY_LIST_ERROR_MSG = 'List is empty!'

and passing it like

 raise IndexError(self.EMPTY_LIST_ERROR_MSG)

into a built-in exception. There's more value in making an exception type of your own, maybe derived from IndexError. I don't think it's really worth externalizing such strings into constants unless

1. the string constant is very long;
2. the string constant's purpose cannot be understood by looking at its contents alone; or
3. you care about i18n.

Cascading comparison

Are you sure that this:

 def __eq__(self, other):
 return self.value == other.value and self.next == other.next

does what you want? I believe that, as written, due to the reference to next it will cascade to comparing every single value in the list after the current one. This is not likely what you want. If all you want to do is check whether next is the same reference without a cascaded equality comparison, then use is instead of ==.

Private variables

Use self._head instead of self.__head, which has a different meaning.

Method names

Consider attempting to match Python's built-in collection terminology, i.e. pop instead of remove_last. A more useful interface would do what pop does and return the removed item as well.

Predicate generators

 for value in self:
 if item == value:
 return True
 return False

can be

return any(item == value for value in self)

Also,

 count = 0
 for _ in self:
 count += 1
 return count

can be

return sum(1 for _ in self)