Skip to content

Instantly share code, notes, and snippets.

@jcasimir
Created October 4, 2023 22:53
Show Gist options
  • Save jcasimir/c72a8dadeb1109573608af6cd9b6024a to your computer and use it in GitHub Desktop.
Save jcasimir/c72a8dadeb1109573608af6cd9b6024a to your computer and use it in GitHub Desktop.
class Node:
def __init__(self, value):
self.value = value
self.link = None
def append(self, value):
if self.link:
self.link.append(value)
else:
self.link = Node(value)
def count(self):
if self.link:
return 1 + self.link.count()
else:
return 0
def find_value_at(self, my_position, target_position):
if my_position == target_position:
return self.value
elif self.link:
return self.link.find_value_at(my_position+1, target_position)
else:
return None
def find_index_of(self, index, target_value):
if self.value == target_value:
return index
elif self.link:
return self.link.find_index_of(index+1, target_value)
else:
return None
def insert_at_position(self, my_position, target_position, target_value):
if my_position + 1 == target_position:
new_node = Node(target_value)
new_node.link = self.link
self.link = new_node
elif self.link:
self.link.insert_at_position(my_position+1, target_position, target_value)
else:
None
def delete_at_position(self, my_position, target_position):
if my_position + 1 == target_position:
self.link = self.link.link
else:
self.link.delete_at_position(my_position+1, target_position)
def delete_value(self, target_value):
if self.link is None:
return None
elif self.link.value == target_value:
self.link = self.link.link
else:
self.link.delete_value(target_value)
class List:
def __init__(self):
self.head = Node(None)
def append(self, value):
self.head.append(value)
def count(self):
return self.head.count()
def find_value_at(self, position):
return self.head.find_value_at(-1, position)
def find_index_of(self, value):
return self.head.find_index_of(-1, value)
def insert_at_position(self, target_position, value):
self.head.insert_at_position(-1, target_position, value)
def delete_at_position(self, position):
self.head.delete_at_position(-1, position)
def delete_value(self, target_value):
self.head.delete_value(target_value)
import unittest
import list
class TestMyLinkedList(unittest.TestCase):
import list
def time_func(func):
def wrapper(*args, **kwargs):
import time
start = time.perf_counter()
result = func(*args, **kwargs)
end = time.perf_counter()
print(f"{func.__name__}: {end - start:.5}s")
return result
return wrapper
#@time_func
def test_inserting_one_value_into_a_list(self):
import list
list = list.List()
self.assertEqual(list.count(), 0)
list.append("one")
self.assertEqual(list.count(), 1)
#@unittest.skipIf(1 < 2, "Set test_level to 2 or greater")
#@time_func
def test_inserting_a_value_at_a_position(self):
import list
list = list.List()
list.append("A")
list.append("C")
list.insert_at_position(1, "B")
self.assertEqual(list.find_index_of("B"), 1)
list.insert_at_position(3, "D")
self.assertEqual(list.find_index_of("D"), 3)
list.insert_at_position(0, "Z")
self.assertEqual(list.find_index_of("Z"), 0)
#@time_func
def test_deleting_a_value_by_position(self):
import list
import tracemalloc
# tracemalloc.start()
# tracemalloc.reset_peak()
list = list.List()
list.append("A")
list.append("B")
list.append("C")
list.append("D")
list.append("E")
list.delete_at_position(0)
self.assertEqual(list.find_index_of("B"), 0)
list.delete_at_position(1)
self.assertEqual(list.find_index_of("B"), 0)
self.assertEqual(list.find_index_of("C"), None)
self.assertEqual(list.find_index_of("D"), 1)
list.delete_at_position(1)
self.assertEqual(list.find_index_of("B"), 0)
self.assertEqual(list.find_index_of("E"), 1)
self.assertEqual(list.count(), 2)
list.delete_at_position(1)
list.delete_at_position(0)
self.assertEqual(list.count(), 0)
first_size, first_peak = tracemalloc.get_traced_memory()
print(f"{first_size=}, {first_peak=}" + "\n")
print("Delta: ")
print(first_peak-first_size)
#@time_func
def test_deleting_to_clear_a_list(self):
import list
import tracemalloc
tracemalloc.start()
tracemalloc.reset_peak()
list = list.List()
list.append("A")
list.append("B")
self.assertEqual(list.count(), 2)
list.delete_at_position(1)
list.delete_at_position(0)
self.assertEqual(list.count(), 0)
first_size, first_peak = tracemalloc.get_traced_memory()
# print(f"{first_size=}, {first_peak=}\n")
# print("Delta: ")
# print(first_peak-first_size)
#@time_func
def test_deleting_by_value(self):
import list
list = list.List()
list.append("A")
list.append("B")
list.append("C")
list.append("D")
list.append("E")
list.delete_value("C")
self.assertEqual(list.find_index_of("D"), 2)
list.delete_value("A")
self.assertEqual(list.find_index_of("B"), 0)
list.delete_value("E")
self.assertEqual(list.count(), 2)
list.delete_value("B")
list.delete_value("D")
self.assertEqual(list.count(), 0)
#@time_func
def test_deleting_by_value_edge_cases(self):
import list
list = list.List()
list.delete_value("A")
list.append("A")
list.append("B")
list.append("A")
self.assertEqual(list.count(), 3)
list.delete_value("A")
self.assertEqual(list.count(), 2)
list.delete_value("C")
self.assertEqual(list.count(), 2)
if __name__ == '__main__':
import sys
sys.argv.append('-v')
unittest.main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment