Data Structures

Q 1: Implement a Linked List. Answer:

class Node:

    def __init__(self, data):
        self.data = data
        self.next_node = None

    def __repr__(self):
        return str(self.data)


class LinkedList:

    def __init__(self):
        # this is the first node of the linked list
        # WE CAN ACCESS THIS NODE EXCLUSIVELY !!!
        self.head = None
        self.num_of_nodes = 0

    # O(1) constant running time
    def insert_start(self, data):
        self.num_of_nodes += 1
        new_node = Node(data)

        # the head is NULL (so the data structure is empty)
        if self.head is None:
            self.head = new_node
        # so this is when the linked list is not empty
        else:
            # we have to update the references
            new_node.next_node = self.head
            self.head = new_node

    # O(N)
    def insert_end(self, data):
        self.num_of_nodes += 1
        new_node = Node(data)

        # check if the linked list is empty
        if self.head is None:
            self.head = new_node
        else:
            # this is when the linked list is not empty
            current_node = self.head

            # this is why it has O(N) linear running time
            while current_node.next_node is not None:
                current_node = current_node.next_node

            # current_node is the last node: so we insert the new_node
            # right after the current_node
            current_node.next_node = new_node

    # O(1) constant running time
    def size_of_list(self):
        return self.num_of_nodes

    # O(N) linear running time
    def traverse(self):

        current_node = self.head

        while current_node is not None:
            print(current_node)
            current_node = current_node.next_node

    # O(N) linear running time
    def remove(self, data):

        # the list is empty
        if self.head is None:
            return

        current_node = self.head
        # we have to track the previous node for future pointer updates
        # this is why doubly linked lists are better - we can get the previous
        # node (here with linked lists it is impossible)
        previous_node = None

        # search for the item we want to remove (data)
        while current_node is not None and current_node.data != data:
            previous_node = current_node
            current_node = current_node.next_node

        # search miss
        if current_node is None:
            return

        # update the references (so we have the data we want to remove)
        # the head node is the one we want to remove
        if previous_node is None:
            self.head = current_node.next_node
        else:
            # remove an internal node by updating the pointers
            # NO NEED TO del THE NODE BECAUSE THE GARBAGE COLLECTOR WILL DO THAT
            previous_node.next_node = current_node.next_node


if __name__ == '__main__':
    linked_list = LinkedList()
    linked_list.insert_end(10)
    linked_list.insert_start(100)
    linked_list.insert_start(1000)
    linked_list.insert_end('Adam')
    linked_list.insert_end(7.5)
    linked_list.traverse()
    print('-------')
    linked_list.remove(1000)
    linked_list.traverse()

Q2: Implement a Doubly Linked List. Ans:

class Node:

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


class DoublyLinkedList:

    def __init__(self):
        self.head = None
        self.tail = None

    # this operation inserts items at the end of the linked list
    # so we have to manipulate the tail node in O(1) running time
    def insert(self, data):

        new_node = Node(data)

        # when the list is empty
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        # there is at least 1 item in the data structure
        # we keep inserting items at the end of the linked list
        else:
            new_node.previous = self.tail
            self.tail.next = new_node
            self.tail = new_node

    # we can traverse a doubly linked list in both directions
    def traverse_forward(self):

        current_node = self.head

        while current_node is not None:
            print("%d" % current_node.data)
            current_node = current_node.next

    def traverse_backward(self):

        current_node = self.tail

        while current_node is not None:
            print("%d" % current_node.data)
            current_node = current_node.previous


if __name__ == '__main__':

    linked_list = DoublyLinkedList()
    linked_list.insert(1)
    linked_list.insert(2)
    linked_list.insert(3)

    # 1 2 3
    linked_list.traverse_forward()

    # 3 2 1
    linked_list.traverse_backward()

Q3: Implement a Queue.

Ans:

class Queue:

    def __init__(self):
        self.queue = []

    # O(1) running time
    def is_empty(self):
        return self.queue == []

    # O(1) running time
    def enqueue(self, data):
        self.queue.append(data)

    # O(N) linear running time but we could use doubly linked list
    # to achieve O(1) for all operations
    def dequeue(self):
        data = self.queue[0]
        del self.queue[0]
        return data

    # O(1) constant running time
    def peek(self):
        return self.queue[0]

    # O(1)
    def size_queue(self):
        return len(self.queue)

Q 4: Ans:

class Stack:

    def __init__(self):
        self.stack = []

    # O(1) running time
    def is_empty(self):
        return self.stack == []

    # O(1) running time
    def push(self, data):
        self.stack.append(data)

    # O(1) because we manipulate the last item
    def pop(self):

        if self.size_stack < 1:
            return None

        data = self.stack[-1]
        del self.stack[-1]
        return data

    # O(1) constant running time
    def peek(self):
        return self.stack[-1]

    # O(1)
    def size_stack(self):
        return len(self.stack)