assignment3.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Problem 1 ###\n",
    "class LinkedList:\n",
    "    \"\"\"\n",
    "    A singly linked list with both head and tail\n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        self.head = self.tail = None\n",
    "        self.size = 0\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "\n",
    "    def is_empty(self):\n",
    "        \"\"\"\n",
    "        Checks if the LinkedList is empty or not\n",
    "        :return: bool\n",
    "        \"\"\"\n",
    "        if self.head == self.tail is None:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def insert_at_end(self, data):\n",
    "        \"\"\"\n",
    "        Adds a new node at the end of the LinkedList\n",
    "        Time Complexity: O(1)\n",
    "        :param data: value you want to add at the end\n",
    "        :return: None\n",
    "        \"\"\"\n",
    "        if self.is_empty():\n",
    "            self.head = self.tail = Node(data)\n",
    "        else:\n",
    "            last_node = self.tail\n",
    "            last_node.next = Node(data)\n",
    "            self.tail = last_node.next\n",
    "        self.size += 1\n",
    "\n",
    "    def remove_from_beg(self):\n",
    "        \"\"\"\n",
    "        Removes node which is at the beginning of LinkedList\n",
    "        Time Complexity: O(1)\n",
    "        :return: self.head.data\n",
    "        \"\"\"\n",
    "        if self.is_empty():\n",
    "            raise Exception(\"Data Structure is empty\")\n",
    "        else:\n",
    "            head_node = self.head\n",
    "            self.head = head_node.next\n",
    "            # when the only node is removed\n",
    "            if self.head is None:\n",
    "                self.tail = None\n",
    "        self.size -= 1\n",
    "        return head_node.data\n",
    "\n",
    "    def traverse(self):\n",
    "        \"\"\"\n",
    "        Traverses the Nodes and prints values on STDOUT\n",
    "        Time Complexity: O(n)\n",
    "        :return: None\n",
    "        \"\"\"\n",
    "        if self.is_empty():\n",
    "            raise Exception(\"Data Structure is empty\")\n",
    "        cur_node = self.head\n",
    "        while cur_node:\n",
    "            print(cur_node.data, end=' ')\n",
    "            cur_node = cur_node.next\n",
    "        print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    A singly linked list with both head and tail\n",
      "    \n",
      "Size of LinkedList: 4\n",
      "5 14 22 -17 \n",
      "Size of LinkedList: 3\n",
      "14 22 -17 \n"
     ]
    }
   ],
   "source": [
    "### Problem 1 demo ###\n",
    "L = LinkedList()\n",
    "print(L.__doc__)\n",
    "\n",
    "L.insert_at_end(5)\n",
    "L.insert_at_end(14)\n",
    "L.insert_at_end(22)\n",
    "L.insert_at_end(-17)\n",
    "print(f'Size of LinkedList: {len(L)}')\n",
    "L.traverse()\n",
    "\n",
    "L.remove_from_beg()\n",
    "print(f'Size of LinkedList: {len(L)}')\n",
    "L.traverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Problem 3 ###\n",
    "class Queue(LinkedList):\n",
    "    \"\"\"\n",
    "    Queue (FIFO) data structure implementation using singly LinkedList\n",
    "    \"\"\"\n",
    "    def enqueue(self, data):\n",
    "        return self.insert_at_end(data)\n",
    "\n",
    "    def dequeue(self):\n",
    "        return self.remove_from_beg()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    Queue (FIFO) data structure implementation using singly LinkedList\n",
      "    \n",
      "Size of Queue: 3\n",
      "10 -10 100 \n",
      "Size of Queue: 1\n",
      "100 \n"
     ]
    }
   ],
   "source": [
    "### Problem 3 demo ###\n",
    "\n",
    "Q = Queue()\n",
    "print(Q.__doc__)\n",
    "\n",
    "Q.enqueue(10)\n",
    "Q.enqueue(-10)\n",
    "Q.enqueue(100)\n",
    "print(f'Size of Queue: {len(Q)}')\n",
    "Q.traverse()\n",
    "\n",
    "Q.dequeue()\n",
    "Q.dequeue()\n",
    "print(f'Size of Queue: {len(Q)}')\n",
    "Q.traverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Problem 2 ###\n",
    "class Stack(Queue):\n",
    "    \"\"\"\n",
    "    Stack (LIFO) data structure implementation using a Queue\n",
    "    \"\"\"\n",
    "    def push(self, data):\n",
    "        return self.enqueue(data)\n",
    "\n",
    "    def pop(self):\n",
    "        for _ in range(self.size-1):\n",
    "            temp = self.dequeue()\n",
    "            self.enqueue(temp)\n",
    "        return self.dequeue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    Stack (LIFO) data structure implementation using a Queue\n",
      "    \n",
      "Size of Stack: 4\n",
      "10 69 99 9 \n",
      "Size of Stack: 1\n",
      "10 \n"
     ]
    }
   ],
   "source": [
    "### Problem 2 demo ###\n",
    "S = Stack()\n",
    "print(S.__doc__)\n",
    "\n",
    "S.push(10)\n",
    "S.push(69)\n",
    "S.push(99)\n",
    "S.push(9)\n",
    "print(f'Size of Stack: {len(S)}')\n",
    "S.traverse()\n",
    "\n",
    "S.pop()\n",
    "S.pop()\n",
    "S.pop()\n",
    "print(f'Size of Stack: {len(S)}')\n",
    "S.traverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Problem 4 ###\n",
    "def bubble_sort(arr):\n",
    "    size = len(arr)\n",
    "    for i in range(size - 1):\n",
    "        swapped = False\n",
    "        for j in range(size - 1 - i):\n",
    "            if arr[j] > arr[j + 1]:\n",
    "                swapped = True\n",
    "                arr[j], arr[j + 1] = arr[j + 1], arr[j]\n",
    "        if not swapped:\n",
    "            break\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[40, 50, 60, 70, 80, 90]\n"
     ]
    }
   ],
   "source": [
    "### Problem 4 demo ###\n",
    "list1 = [80,70,90,40,60,50]\n",
    "print(bubble_sort(list1.copy()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Problem 5 ###\n",
    "def selection_sort(arr):\n",
    "    size = len(arr)\n",
    "    for i in range(size-1):\n",
    "        min_idx = i\n",
    "        for j in range(i+1, size):\n",
    "            if arr[j] < arr[min_idx]:\n",
    "                min_idx = j\n",
    "        arr[min_idx], arr[i] = arr[i], arr[min_idx]\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[40, 50, 60, 70, 80, 90]\n"
     ]
    }
   ],
   "source": [
    "### Problem 5 demo ###\n",
    "list1 = [80,70,90,40,60,50]\n",
    "print(selection_sort(list1.copy()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Note1: Queue and Stack implementation use Inheritance to reduce redundancy and complexity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Note2: Please mention everything clearly in the assignments instead of wasting your and our time"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}