Data Structures

Trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEndOfWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEndOfWord = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.isEndOfWord

    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Queue

class Queue:
    """Queue using a linked list"""
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def isEmpty(self):
        return self.head is None

    def enqueue(self, val):
        node = Node(val)
        if self.head is None:
            self.head = self.tail = node
            return 
        self.tail.next = node
        self.tail = node

    def dequeue(self):
        if self.isEmpty():
            return None
        node = self.head
        self.head = node.next

        if self.head is None:
            self.tail = None