Queue implementation in Python. #DataStructure

queue.py

class Node:
    """This Node class has been created for you.
    It contains the necessary properties for the solution, which are:
    - name
    - phone
    - next
    """

    def __init__(self, name, phone):
        self.name = name
        self.phone = phone
        self.__next = None

    def set_next(self, node):
        if isinstance(node, Node) or node is None:
            self.__next = node
        else:
            raise TypeError("The 'next' node must be of type Node or None.")

    def get_next(self):
        return self.__next

    def print_details(self):
        print("{} ({})".format(self.name, self.phone))


class LinkedList:
    """ You should implement the methods of this class which are currently
    raising a NotImplementedError!
    Don't change the name of the class or any of the methods.  """
    def __init__(self):
        self.__root = None

    def get_root(self):
        return self.__root

    def add_start_to_list(self, node):
        """Adds node to the beginning of the list.

        :param node: the node to add at the start
        :return: None"""

        if self.__root:
            # Sets the next node of the new node to be __root of LinkedList
            node.set_next(self.__root)
        self.__root = node

    def remove_end_from_list(self):
        """This method:

            - Iterate over each node
            - Find both the second-to-last node and the last node
            - Set the second-to-last node's next to be None
            - Return the last node
        
        :return: the removed Node."""

        marker = self.get_root()

        if not marker.get_next():
            self.__root = None
            return marker
        
        # Iterate over each Node in this list
        while marker:
            # Get the next node
            following_node = marker.get_next()
            if following_node:
                # If the next Node's next Node is None, it means the current
                # marker is the second-to-last Node (there is only one more
                # after it)
                if not following_node.get_next():
                    # Make the marker's next = None so the very last Node is
                    # removed
                    marker.set_next(None)
                    return following_node
            marker = marker.get_next()

    def print_list(self):
        marker = self.__root
        while marker:
            marker.print_details()
            marker = marker.get_next()

    def find(self, name):
        """Finds a node in the linked list with a given name.

        :param name: the name of the node to find in this list.
        :return: Found Node object, or else raises a LookupError."""

        marker = self.get_root()
        while marker:
            if marker.name == name:
                return marker
            marker = marker.get_next()

        raise LookupError("Name {} not in the linked list.".format(name))

    def size(self):
        """Returns the amount of Nodes in the list.

        :return: the amount of nodes in this list."""

        marker = self.get_root()
        count = 0
        while marker:
            count += 1
            marker = marker.get_next()

        return count


class LinkedQueue:
    """ This class is a queue wrapper around a LinkedList.

    This means that methods like `add_to_list_start` should now be called `push`,
    for example."""

    def __init__(self):
        self.__linked_list = LinkedList()

    def push(self, node):
        """Adds a node to the linked list property.

        :param node: The Node to add"""

        self.__linked_list.add_start_to_list(node)

    def pop(self):
        """Removes a node from the end of the linked list, and return
        the removed node.

        :return: Node, the last node of the linked list after being removed.
        """

        return self.__linked_list.remove_end_from_list()

    def find(self, name):
        return self.__linked_list.find(name)

    def print_details(self):
        self.__linked_list.print_list()

    def __len__(self):
        """ Returns the amount of Nodes in the linked list."""

        return self.__linked_list.size()

# See also: https://gist.github.com/santosh/d175565ec09abdea35c038cd513da6ca

test_queue.py

from unittest import TestCase
from queue import Node, LinkedList, LinkedQueue


class TestLinkedList(TestCase):
    """
    This class tests that your LinkedList class was implemented correctly.
    All you have to do is run this file.
    To do so, right click the class name in your PyCharm project and select the option
    Run 'Unittests in tests'

    If any tests fail, then you are not done yet.
    If all tests pass, good job! You can move on to the next challenge.
    """

    def test_node_creation(self):
        name = "Jose"
        phone = "123-456-7890"

        node = Node(name, phone)

        self.assertEqual(name, node.name)
        self.assertEqual(phone, node.phone)

    def test_list_creation(self):
        linked_list = LinkedList()

        self.assertIsNone(linked_list.get_root())

    def test_add_to_list_start(self):
        name = "Jose"
        phone = "123-456-7890"

        node = Node(name, phone)

        linked_list = LinkedList()

        linked_list.add_start_to_list(node)

        self.assertEqual(linked_list.get_root(), node)

    def test_add_many_to_list_start(self):
        names = ("Jose", "1234-356"), ("Rolf", "2345-1-53563-2"), ("Anna", "345623-16779-3")

        nodes = [Node(name, phone) for name, phone in names]

        linked_list = LinkedList()

        for node in nodes:
            linked_list.add_start_to_list(node)

        marker = linked_list.get_root()
        for i in range(len(nodes)-1, -1, -1):
            self.assertEqual(marker, nodes[i])
            marker = marker.get_next()

    def test_remove_end_from_list(self):
        names = ("Jose", "1234-356"), ("Rolf", "2345-1-53563-2"), ("Anna", "345623-16779-3")

        nodes = [Node(name, phone) for name, phone in names]

        linked_list = LinkedList()

        for node in nodes:
            linked_list.add_start_to_list(node)

        self.assertIsNotNone(linked_list.find("Jose"))

        popped_node = linked_list.remove_end_from_list()

        self.assertEqual(popped_node, nodes[0])

        with self.assertRaises(LookupError):
            linked_list.find("Jose")

    def test_find_in_list(self):
        names = ("Jose", "1234-356"), ("Rolf", "2345-1-53563-2"), ("Anna", "345623-16779-3")

        nodes = [Node(name, phone) for name, phone in names]

        linked_list = LinkedList()

        for node in nodes:
            linked_list.add_start_to_list(node)

        marker = linked_list.get_root()
        for i in range(len(nodes) - 1, -1, -1):
            self.assertEqual(linked_list.find(marker.name), nodes[i])
            marker = marker.get_next()

    def test_find_missing_in_list(self):
        linked_list = LinkedList()

        with self.assertRaises(LookupError):
            linked_list.find("Smith")


class TestQueue(TestCase):
    def test_push_to_queue(self):
        name = "Jose"
        phone = "123-456-7890"

        node = Node(name, phone)
        queue = LinkedQueue()

        queue.push(node)

        self.assertEqual(len(queue), 1)

    def test_pop_from_queue(self):
        name = "Jose"
        phone = "123-456-7890"

        node = Node(name, phone)
        queue = LinkedQueue()

        queue.push(node)

        self.assertEqual(len(queue), 1)

        popped = queue.pop()

        self.assertEqual(popped, node)
        self.assertEqual(len(queue), 0)

    def test_find_in_queue(self):
        name = "Jose"
        phone = "123-456-7890"

        node = Node(name, phone)
        queue = LinkedQueue()

        queue.push(node)

        self.assertEqual(queue.find(name), node)