02_collections.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1bd033e2-38eb-4d9d-83b5-3fe493446ae3",
   "metadata": {},
   "source": [
    "# Intro to Data Structures and Algorithms "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8678bae-32c2-4dfd-b915-f6c6b22b9e26",
   "metadata": {
    "tags": []
   },
   "source": [
    "[course link](https://learn.udacity.com/courses/ud513)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ec91368-53c8-4317-bf12-e21995bfec83",
   "metadata": {},
   "source": [
    "## Lesson 2. List-Based Collections"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0bf9b8d2-b9fa-41d3-a755-1783fb823734",
   "metadata": {},
   "source": [
    "### Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0185a6e-881c-4444-98c7-ba549f7e4e0d",
   "metadata": {},
   "source": [
    "Lists have all properties of collections and they have an order. Lists do not have a fixed length, they are mutable and can hold items of different data types. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "960e8e14-afd7-462e-8cb3-65f02c6d24e7",
   "metadata": {},
   "source": [
    "### Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cab35e8e-69c7-4e5d-b6fe-c01f2171333e",
   "metadata": {},
   "source": [
    "Array is the most common implementation of lists in programming languages. Arrays have indexes and you can use them to access items inside an array. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "844f93c1-15fb-4fa2-8391-50c37e1a6587",
   "metadata": {},
   "source": [
    "### Python Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a7816eb-b5ba-4a49-9a0c-4f4887077dc2",
   "metadata": {},
   "source": [
    "Behind the scenes a Python list is built as an array. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5e499b3-d680-481e-8151-9ec39fe6721d",
   "metadata": {},
   "source": [
    "Inserting into a Python list is O(n), while operations that search for an element at a particular spot are O(1).  \n",
    "You can see the runtime of other list operations [here](https://wiki.python.org/moin/TimeComplexity). "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03567d44-8912-4416-942a-3cbf74bb3eb7",
   "metadata": {},
   "source": [
    "### Linked Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e552220a-2572-49c8-94f4-ce919fdb8530",
   "metadata": {},
   "source": [
    "A linked list is not an array. \n",
    "It has order but doesn't have indices, instead it has links to the next element of a linked list.  \n",
    "And an advantage of a linked list is that you can easily add or remove an element to it. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dcaebc69-b5c7-4489-ade2-0b43e1e50f0a",
   "metadata": {},
   "source": [
    "Insertion takes constant time for linked lists O(1), because you are just shifting around pointers (links, references) instead of iterating over every element in the list (what you do in arrays and python lists).  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "500ccf41-cb25-4d6d-b032-889b70ee1024",
   "metadata": {},
   "source": [
    "There are also a double-linked lists where you have pointers to the next element and the previous element. The advantage is that you can traverse a double-linked lists in both directions. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "927bb4c8-6fcb-4926-b818-ce1bb6c4ef00",
   "metadata": {},
   "source": [
    "#### Task 1. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c1878575-2aec-45d0-a326-61b7598c117e",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "3\n",
      "4\n",
      "2\n",
      "4\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "\"\"\"The LinkedList code from before is provided below.\n",
    "Add three functions to the LinkedList.\n",
    "\"get_position\" returns the element at a certain position.\n",
    "The \"insert\" function will add an element to a particular\n",
    "spot in the list.\n",
    "\"delete\" will delete the first element with that\n",
    "particular value.\n",
    "Then, use \"Test Run\" and \"Submit\" to run the test cases\n",
    "at the bottom.\"\"\"\n",
    "\n",
    "class Element(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "        \n",
    "        \n",
    "class LinkedList(object):\n",
    "    def __init__(self, head=None):\n",
    "        self.head = head\n",
    "        \n",
    "        \n",
    "    def append(self, new_element):\n",
    "        current = self.head\n",
    "        if self.head:\n",
    "            while current.next:\n",
    "                current = current.next\n",
    "            current.next = new_element\n",
    "        else:\n",
    "            self.head = new_element\n",
    "            \n",
    "            \n",
    "    def get_position(self, position):\n",
    "        \"\"\"Get an element from a particular position.\n",
    "        Assume the first position is \"1\".\n",
    "        Return \"None\" if position is not in the list.\"\"\"\n",
    "        if position < 1:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        for i in range(1, position):\n",
    "            if current.next is None:\n",
    "                return None\n",
    "            current = current.next\n",
    "        \n",
    "        return current\n",
    "\n",
    "    \n",
    "    def insert(self, new_element, position):\n",
    "        \"\"\"Insert a new node at the given position.\n",
    "        Assume the first position is \"1\".\n",
    "        Inserting at position 3 means between\n",
    "        the 2nd and 3rd elements.\"\"\"\n",
    "        if position == 1:\n",
    "            new_element.next = self.head\n",
    "            self.head = new_element\n",
    "            return\n",
    "        \n",
    "        current = self.head\n",
    "        for i in range(1, position-1):\n",
    "            if current.next is None:\n",
    "                return\n",
    "            current = current.next\n",
    "        \n",
    "        new_element.next = current.next\n",
    "        current.next = new_element\n",
    "\n",
    "        \n",
    "    def delete(self, value):\n",
    "        \"\"\"Delete the first node with a given value.\"\"\"\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        \n",
    "        while current is not None:\n",
    "            if current.value == value:\n",
    "                if previous is not None:\n",
    "                    previous.next = current.next\n",
    "                else:\n",
    "                    self.head = current.next\n",
    "                return\n",
    "            previous = current\n",
    "            current = current.next\n",
    "\n",
    "            \n",
    "# Test cases\n",
    "# Set up some Elements\n",
    "e1 = Element(1)\n",
    "e2 = Element(2)\n",
    "e3 = Element(3)\n",
    "e4 = Element(4)\n",
    "\n",
    "# Start setting up a LinkedList\n",
    "ll = LinkedList(e1)\n",
    "ll.append(e2)\n",
    "ll.append(e3)\n",
    "\n",
    "# Test get_position\n",
    "# Should print 3\n",
    "print(ll.head.next.next.value)\n",
    "# Should also print 3\n",
    "print(ll.get_position(3).value)\n",
    "\n",
    "# Test insert\n",
    "ll.insert(e4, 3)\n",
    "# Should print 4 now\n",
    "print(ll.get_position(3).value)\n",
    "\n",
    "# Test delete\n",
    "ll.delete(1)\n",
    "# Should print 2 now\n",
    "print(ll.get_position(1).value)\n",
    "# Should print 4 now\n",
    "print(ll.get_position(2).value)\n",
    "# Should print 3 now\n",
    "print(ll.get_position(3).value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b5ae682-71ee-4173-bfbd-ea34565b31e7",
   "metadata": {},
   "source": [
    "### Stacks"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d131512-1c9f-415f-991a-5022a6791080",
   "metadata": {},
   "source": [
    "A stack is like a stack of objects in real life. You can put objects one on another and have an easy access to the object you've added to the stack recently.\n",
    "\n",
    "Last In - First Out (LI-FO)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae59bcc3-e992-4435-9540-bc0349696ff1",
   "metadata": {},
   "source": [
    "push - add an element to the stack.  \n",
    "pop - to remove the last added element from the stack.  \n",
    "\n",
    "Time complexity is O(1) for both of the operations. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cbeb6e3d-bbe5-4e70-9641-3a43bad8daca",
   "metadata": {},
   "source": [
    "A stack can be realised using a linked list data structure. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d94e54c9-24b7-415a-bea7-42165ef93ecd",
   "metadata": {},
   "source": [
    "#### Task 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "16543405-964e-4faa-8769-8766d767957c",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "2\n",
      "1\n",
      "None\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "\"\"\"Add a couple methods to our LinkedList class,\n",
    "and use that to implement a Stack.\n",
    "You have 4 functions below to fill in:\n",
    "insert_first, delete_first, push, and pop.\n",
    "Think about this while you're implementing:\n",
    "why is it easier to add an \"insert_first\"\n",
    "function than just use \"append\"?\"\"\"\n",
    "\n",
    "class Element(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "        \n",
    "class LinkedList(object):\n",
    "    def __init__(self, head=None):\n",
    "        self.head = head\n",
    "        \n",
    "    def append(self, new_element):\n",
    "        current = self.head\n",
    "        if self.head:\n",
    "            while current.next:\n",
    "                current = current.next\n",
    "            current.next = new_element\n",
    "        else:\n",
    "            self.head = new_element\n",
    "            \n",
    "    def insert_first(self, new_element):\n",
    "        \"Insert new element as the head of the LinkedList\"\n",
    "        new_element.next = self.head\n",
    "        self.head = new_element\n",
    "\n",
    "    def delete_first(self):\n",
    "        \"Delete the first (head) element in the LinkedList as return it\"\n",
    "        if self.head:\n",
    "            deleted_element = self.head\n",
    "            self.head = deleted_element.next\n",
    "            return deleted_element\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "        \n",
    "class Stack:\n",
    "    def __init__(self, top=None):\n",
    "        self.ll = LinkedList(top)\n",
    "\n",
    "    def push(self, new_element):\n",
    "        \"Push (add) a new element onto the top of the stack\"\n",
    "        self.ll.insert_first(new_element)\n",
    "\n",
    "    def pop(self):\n",
    "        \"Pop (remove) the first element off the top of the stack and return it\"\n",
    "        return self.ll.delete_first()\n",
    "    \n",
    "    \n",
    "# Test cases\n",
    "# Set up some Elements\n",
    "e1 = Element(1)\n",
    "e2 = Element(2)\n",
    "e3 = Element(3)\n",
    "e4 = Element(4)\n",
    "\n",
    "# Start setting up a Stack\n",
    "stack = Stack(e1)\n",
    "\n",
    "# Test stack functionality\n",
    "stack.push(e2)\n",
    "stack.push(e3)\n",
    "print(stack.pop().value)\n",
    "print(stack.pop().value)\n",
    "print(stack.pop().value)\n",
    "print(stack.pop())\n",
    "stack.push(e4)\n",
    "print(stack.pop().value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "719c110b-0a59-430d-a64d-1b89beb251f2",
   "metadata": {},
   "source": [
    "### Queues"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73f22133-decc-4d2d-bbca-d2709496fa04",
   "metadata": {},
   "source": [
    "Queue - is a first in, first out (FI-FO) data structure. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e0c6f1c-aee8-464b-8627-a6713c86c188",
   "metadata": {},
   "source": [
    "The first element of a queue or the oldest element of the queue is called Head.   \n",
    "The last element of a queue or the newest element of the queue is called Tail.   \n",
    "\n",
    "enqueue - adding an element to the tail of the queue.  \n",
    "dequeue - removing a head element of the queue.   \n",
    "peak - to look at the head element of the queue but do not remove it. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15e86cd6-be67-457b-9f57-c814a1d13169",
   "metadata": {},
   "source": [
    "Deque - is a special type of queue that goes both ways (you can enqueue and dequeue from either end). "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fad4ea1c-8352-46d4-ba2e-a139d2e305a3",
   "metadata": {},
   "source": [
    "Both a queue and deque can be realised using a linked list data structure. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ff28d3d-1c76-4e78-b277-15ce40be48f9",
   "metadata": {},
   "source": [
    "Priority queue - you assign each element a numerical priority when you insert it into a queue. When you dequeue you remove the element with the highest priority. And if all the elements are having the same priority - the oldest element is the one that gets dequeued first.  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0fb84f19-114d-4ccf-9732-4462e16424eb",
   "metadata": {},
   "source": [
    "#### Task 3. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "39a06040-fa25-45a7-b596-34ce3e9b0327",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "\"\"\"Make a Queue class using a list!\n",
    "Hint: You can use any Python list method\n",
    "you'd like! Try to write each one in as \n",
    "few lines as possible.\n",
    "Make sure you pass the test cases too!\"\"\"\n",
    "\n",
    "class Queue:\n",
    "    def __init__(self, head=None):\n",
    "        self.storage = [head]\n",
    "\n",
    "    def enqueue(self, new_element):\n",
    "        self.storage.append(new_element)\n",
    "\n",
    "    def peek(self):\n",
    "        return self.storage[0]\n",
    "\n",
    "    def dequeue(self):\n",
    "        return self.storage.pop(0)\n",
    "    \n",
    "    \n",
    "# Setup\n",
    "q = Queue(1)\n",
    "q.enqueue(2)\n",
    "q.enqueue(3)\n",
    "\n",
    "# Test peek\n",
    "# Should be 1\n",
    "print(q.peek())\n",
    "\n",
    "# Test dequeue\n",
    "# Should be 1\n",
    "print(q.dequeue())\n",
    "\n",
    "# Test enqueue\n",
    "q.enqueue(4)\n",
    "# Should be 2\n",
    "print(q.dequeue())\n",
    "# Should be 3\n",
    "print(q.dequeue())\n",
    "# Should be 4\n",
    "print(q.dequeue())\n",
    "q.enqueue(5)\n",
    "# Should be 5\n",
    "print(q.peek())"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}