1
\$\begingroup\$

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)
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Please fix the indentation in the first code block. \$\endgroup\$ Commented Apr 26, 2020 at 18:40

1 Answer 1

Reset to default
2
\$\begingroup\$

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)
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.