Skip to content

Instantly share code, notes, and snippets.

@jcasimir
Created October 10, 2023 23:38
Show Gist options
  • Save jcasimir/9c6e75032004f13a15d809adfc0f34a7 to your computer and use it in GitHub Desktop.
Save jcasimir/9c6e75032004f13a15d809adfc0f34a7 to your computer and use it in GitHub Desktop.
(Mostly) Live-Coded Recursive Linked List in Python
# This was the first version where the list does more "head-checking"
# instead of the final version (list.py) where the head uses a null object
class RecursiveList:
def __init__(self):
self.head = None
def count(self):
if self.head:
return self.head.count()
else:
return 0
def add(self, input):
if self.head:
self.head.add(input)
else:
self.head = Node(input)
def insert(self, position, input):
if position == 0:
old_head = self.head
self.head = Node(input)
self.head.link = old_head
else:
self.head.insert(0, position, input)
def delete(self, target):
if target == self.head.value:
self.head = self.head.link
else:
self.head.delete(target)
class Node:
def __init__(self, value):
self.value = value
self.link = None
def count(self):
if self.link is None:
return 1
else:
return 1 + self.link.count()
def add(self, value):
if self.link is None:
self.link = Node(value)
else:
self.link.add(value)
def insert(self, my_position, position, input):
if position == my_position + 1:
new_node = Node(input)
new_node.link = self.link
self.link = new_node
else:
self.link.insert(my_position + 1, position, input)
def delete(self, target):
if target == self.link.value:
self.link = self.link.link
else:
self.link.delete(target)
class RecursiveList:
def __init__(self):
self.head = Node(None)
def count(self):
return self.head.count() - 1
def add(self, input):
self.head.add(input)
def insert(self, position, input):
self.head.insert(-1, position, input)
def delete(self, target):
self.head.delete(target)
def position_of_value(self, target):
return self.head.position_of_value(-1, target)
class Node:
def __init__(self, value):
self.value = value
self.link = None
def count(self):
if self.link is None:
return 1
else:
return 1 + self.link.count()
def add(self, value):
if self.link is None:
self.link = Node(value)
else:
self.link.add(value)
def insert(self, my_position, position, input):
if position == my_position + 1:
new_node = Node(input)
new_node.link = self.link
self.link = new_node
else:
self.link.insert(my_position + 1, position, input)
def delete(self, target):
if target == self.link.value:
self.link = self.link.link
else:
self.link.delete(target)
def position_of_value(self, my_position, target):
if target == self.value:
return my_position
else:
return self.link.position_of_value(my_position+1, target)
import unittest
from list import RecursiveList
class TestList(unittest.TestCase):
def test_list_exists(self):
list = RecursiveList()
self.assertTrue(list);
def test_list_counts(self):
list = RecursiveList()
self.assertEqual(0, list.count())
def test_list_counts_after_one_add(self):
list = RecursiveList()
list.add("A")
self.assertEqual(1, list.count())
def test_list_counts_two_after_two_adds(self):
list = RecursiveList()
list.add("A")
list.add("B")
self.assertEqual(2, list.count())
def test_list_counts_three_after_three_adds(self):
list = RecursiveList()
list.add("A")
list.add("B")
list.add("C")
self.assertEqual(3, list.count())
def test_insert_into_an_empty_list(self):
list = RecursiveList()
list.insert(0, "A")
self.assertEqual(1, list.count())
def test_insert_into_the_head_position_of_an_existing_list(self):
list = RecursiveList()
list.add("B")
list.insert(0, "A")
self.assertEqual(2, list.count())
self.assertEqual(0, list.position_of_value("A"))
def test_insert_into_the_middle_position_of_an_existing_list(self):
list = RecursiveList()
list.add("A")
list.add("C")
list.insert(1, "B")
self.assertEqual(3, list.count())
self.assertEqual(0, list.position_of_value("A"))
self.assertEqual(1, list.position_of_value("B"))
def test_insert_on_to_the_end_position_of_an_existing_list(self):
list = RecursiveList()
list.add("A")
list.add("B")
list.insert(2, "C")
self.assertEqual(3, list.count())
self.assertEqual(0, list.position_of_value("A"))
self.assertEqual(1, list.position_of_value("B"))
def test_delete_from_a_list(self):
list = RecursiveList()
list.add("A")
list.add("B")
list.add("C")
list.delete("A")
self.assertEqual(2, list.count())
list.delete("C")
self.assertEqual(1, list.count())
list.delete("B")
self.assertEqual(0, list.count())
if __name__ == '__main__':
unittest.main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment