Linked Lists

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
import sys
import unittest
from dataclasses import dataclass
from typing import *
sys.setrecursionlimit(10**6)

## linked lists are an example of mixed compound data:

LinkedList = Union['LLNode',None]

@dataclass(frozen=True)
class LLNode:
    first : Any
    rest : LinkedList

# examples of data
l1 = None
l2 = LLNode(3, None)
l3 = LLNode("banana", LLNode(14, None))
l4 = LLNode(None, LLNode("whisper", LLNode(143, None)))


# return the length of the linked list
def ll_len(ll : LinkedList) -> int:
    match ll:
        case None:
            return 0
        case LLNode(f,r):
            return 1 + ll_len(r)


# does the list contain the string "banana" ?
def contains_banana(ll : LinkedList) -> bool:
    match ll:
        case None:
            return False
        case LLNode(f,r):
            return (f == "banana") or contains_banana(r)


# what's the reverse of the list?
def ll_reverse(ll : LinkedList) -> LinkedList:
    return ll_reverse_helper(ll,None)

def ll_reverse_helper(ll : LinkedList, accum : LinkedList) -> LinkedList:
    match ll:
        case None:
            return accum
        case LLNode(f,r):
            return ll_reverse_helper(r,LLNode(f,accum))


def ll_append(ll1 : LinkedList, ll2 : LinkedList) -> LinkedList:
    match ll1:
        case None:
            return ll2
        case LLNode(f,r):
            return LLNode(f,ll_append(r,ll2))

class MyTests(unittest.TestCase):

    def test_len(self):
        self.assertEqual(0,ll_len(l1))
        self.assertEqual(1,ll_len(l2))
        self.assertEqual(2,ll_len(l3))
        self.assertEqual(3,ll_len(l4))

    def test_contains_banana(self):
        self.assertEqual(False,contains_banana(l1))
        self.assertEqual(True,contains_banana(l3))
        self.assertEqual(False,contains_banana(l4))

    def test_reverse(self):
        self.assertEqual(l1,ll_reverse(l1))
        self.assertEqual(l2,ll_reverse(l2))
        self.assertEqual(LLNode(14,LLNode("banana",None)),ll_reverse(l3))
        self.assertEqual(LLNode(143,LLNode("whisper",LLNode(None,None))),
                         ll_reverse(l4))

    def test_append(self):
        self.assertEqual(l1,ll_append(l1,l1))
        self.assertEqual(l2,ll_append(l2,l1))
        self.assertEqual(LLNode("banana",LLNode(14,LLNode(3,None))),
                         ll_append(l3,l2))