Skip to content

Instantly share code, notes, and snippets.

@santosh
Created June 1, 2019 05:05
Show Gist options
  • Save santosh/0c3f4d6c7d9382edaae7094048d71819 to your computer and use it in GitHub Desktop.
Save santosh/0c3f4d6c7d9382edaae7094048d71819 to your computer and use it in GitHub Desktop.
Queue implementation in Python. #DataStructure
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
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment