Linked Lists and Hash Tables

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def add_front(self, data):
        node = Node(data)
        node.next = self.head          # the new node points at the old first node
        self.head = node               # and becomes the new head

    def add_end(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = node

    def insert_sorted(self, data):
        node = Node(data)
        if self.head is None or data < self.head.data:
            node.next = self.head
            self.head = node
            return
        current = self.head
        while current.next is not None and current.next.data < data:
            current = current.next
        node.next = current.next        # point the new node onward first
        current.next = node             # then point the previous node at it

    def delete(self, data):
        if self.head is None:
            return False
        if self.head.data == data:
            self.head = self.head.next
            return True
        current = self.head
        while current.next is not None:
            if current.next.data == data:
                current.next = current.next.next      # bypass the node
                return True
            current = current.next
        return False

    def find(self, data):
        current = self.head
        position = 0
        while current is not None:
            if current.data == data:
                return position
            current = current.next
            position += 1
        return -1

    def to_list(self):
        items = []
        current = self.head
        while current is not None:
            items.append(current.data)
            current = current.next
        return items

numbers = LinkedList()
for value in [30, 10, 20]:
    numbers.insert_sorted(value)
numbers.add_front(5)
numbers.add_end(40)
print(numbers.to_list())            # [5, 10, 20, 30, 40]
numbers.delete(20)
print(numbers.to_list())            # [5, 10, 30, 40]
print(numbers.find(30), numbers.find(99))     # 2 -1

data = [17, None, 9, 23, None, None]
nxt = [3, 4, 0, -1, 5, -1]
head = 2
free = 1

def places(start):
    found = []
    index = start
    while index != -1:
        found.append(index)
        index = nxt[index]
    return found

print([data[i] for i in places(head)])      # [9, 17, 23]
print(places(free))                         # [1, 4, 5]

# insert 20 after 17 (index 0), using the first free place
new = free
free = nxt[free]                    # the free list moves on to the next unused place
data[new] = 20
nxt[new] = nxt[0]                   # 20 points at what 17 pointed at
nxt[0] = new                        # 17 now points at 20
print([data[i] for i in places(head)], free)      # [9, 17, 20, 23] 4

def hash_key(key, size):
    total = 0
    for ch in key:
        total = total + ord(ch)
    return total % size

for name in ["Asha", "Ben", "Chloe", "Dev"]:
    print(name, "goes in slot", hash_key(name, 7))

class ChainedTable:
    def __init__(self, size):
        self.size = size
        self.slots = [[] for _ in range(size)]

    def index(self, key):
        return sum(ord(ch) for ch in key) % self.size

    def put(self, key, value):
        chain = self.slots[self.index(key)]
        for pair in chain:
            if pair[0] == key:
                pair[1] = value
                return
        chain.append([key, value])

    def get(self, key):
        for stored_key, value in self.slots[self.index(key)]:
            if stored_key == key:
                return value
        return None

table = ChainedTable(5)
for name, age in [("Asha", 15), ("Ben", 16), ("Chloe", 15), ("Dev", 17), ("Esme", 16)]:
    table.put(name, age)
print(table.get("Chloe"), table.get("Zoe"))
print([len(chain) for chain in table.slots])

class ProbingTable:
    def __init__(self, size):
        self.keys = [None] * size
        self.values = [None] * size

    def put(self, key, value):
        size = len(self.keys)
        i = key % size
        for step in range(size):
            spot = (i + step) % size
            if self.keys[spot] is None or self.keys[spot] == key:
                self.keys[spot] = key
                self.values[spot] = value
                return spot
        raise OverflowError("the table is full")

    def get(self, key):
        size = len(self.keys)
        i = key % size
        for step in range(size):
            spot = (i + step) % size
            if self.keys[spot] is None:
                return None
            if self.keys[spot] == key:
                return self.values[spot]
        return None

table = ProbingTable(7)
for key in [15, 22, 8, 29]:
    print("key", key, "stored in slot", table.put(key, "record " + str(key)))
print(table.get(8), table.get(36))

# raises: TypeError
lookup = {}
lookup[[1, 2]] = "a list cannot be a key"

words = "the cat sat on the mat and the cat slept".split()

counts = {}
for word in words:
    counts[word] = counts.get(word, 0) + 1
print(counts)                               # {'the': 3, 'cat': 2, ...}
print(max(counts, key=counts.get))          # the

a = {1, 2, 3, 4}
b = {3, 4, 5}
print(a | b, a & b, a - b, a ^ b)     # union, intersection, difference, symmetric difference
print(3 in a, 9 in a)
print(len(set([4, 4, 7, 7, 7])))      # 2, which is a quick way to remove duplicates

import json

record = {"name": "Asha", "year": 12, "subjects": ["Computing", "Maths"], "prefect": True}

text = json.dumps(record)
print(text)

back = json.loads(text)
print(back["subjects"][0], back == record)