Time_Space_Complexity_Data_Structures-Starter.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Time/Space Complexity - Intro to Data Structures (User Defined)\n",
    "\n",
    "### Topics to discuss today:\n",
    "\n",
    "<ul>\n",
    "    <li>Time and Space Complexity - What is it/How do we measure it</li>\n",
    "    <li>Asymptotic Analysis</li>\n",
    "    <li><strong>Data Structures</strong></li>\n",
    "    <li>Some of the popular sorting algorithms</li>\n",
    "</ul>\n",
    "\n",
    "### Data Structures to discuss:\n",
    "- Arrays\n",
    "- Stacks\n",
    "- Queues\n",
    "- Linked Lists\n",
    "    - Singly Linked Lists\n",
    "    - Traversing A Linked List\n",
    "    - Finding a node in a linked list\n",
    "    - Adding to a linked list\n",
    "- Binary Search Trees\n",
    "    - Construction\n",
    "    - Traversal\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Time and Space Complexity\n",
    "\n",
    "#### What is it?\n",
    "\n",
    "Time and space complexity is the measure of how much time a given action(function) will take to solve a problem. In the same fashion, we determine how much a given data structure will need in terms of memory allocation. A problem can have multiple solutions and finding the optimal solution for the problem needs to be analyzed in time and space.\n",
    "\n",
    "#### How do we measure Time and Space Complexity?\n",
    "\n",
    "In order to measure time and space complexity we use Asymptotic analysis. The reason for this is because we need a way to measure different algorithms (functions) based on the size of their inputs in a mathmatical way. For example, we could have a function that is computed as f(n) and another that is g(n^2). All things around the function staying constant, the only thing that changes is the size of the input. Below is the chart that shows the different Asymptotic analysis formats. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table style=\"text-align:center;\" class=\"table table-bordered\">\n",
    "<tbody><tr>\n",
    "<td>constant</td>\n",
    "<td>−</td>\n",
    "<td>Ο(1)</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>logarithmic</td>\n",
    "<td>−</td>\n",
    "<td>Ο(log n)</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>linear</td>\n",
    "<td>−</td>\n",
    "<td>Ο(n)</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>Linear Logarithmic</td>\n",
    "<td>−</td>\n",
    "<td>Ο(n log n)</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>quadratic</td>\n",
    "<td>−</td>\n",
    "<td>Ο(n<sup>2</sup>)</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>cubic</td>\n",
    "<td>−</td>\n",
    "<td>Ο(n<sup>3</sup>)</td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>polynomial</td>\n",
    "<td>−</td>\n",
    "<td>n<sup>Ο(1)</sup></td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>exponential</td>\n",
    "<td>−</td>\n",
    "<td>2<sup>Ο(n)</sup></td>\n",
    "</tr>\n",
    "</tbody></table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In python we benefit from the dynamic array which means the block of memory will expand as needed for the given input to the array. In traditional arrays (depending on the type of operating system) we will usually store our inputs in 4 or 8 consecutive blocks of memory. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Which in python looks like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's take a look at some of the time and space analysis of arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stacks and Queues (Review)\n",
    "\n",
    "** Stacks ** as the name suggests is a data structure that allows for data to follow the Last In First Out priciple(LIFO). Think of a stack of pancakes for example. To get the first pancake you would  start with the top and go down.\n",
    "\n",
    "##### Searching through a stack will be Linear Time O(n) - Constant Space O(1)\n",
    "##### Selecting the first item will be done in Linear Time O(n) - Constant Space O(1)\n",
    "##### Selecting the last item will be done in Constant Time O(1) - Constant Space O(1)\n",
    "##### Adding to the stack will be done in Constant Time O(1) - Constant Space O(1)\n",
    "\n",
    "** Queues ** are similar but in this case follow the First In First Out principle(FIFO). Think of this as a line in a black friday sale. The first person camped out for the big screen tv is the first to get it.\n",
    "\n",
    "##### Searching through a queue will be Linear Time O(n) - Constant Space O(1)\n",
    "##### Selecting the first item will be done in Constant Time O(1) - Constant Space O(1)\n",
    "##### Selecting the last item will be done in Linear Time O(n) - Constant Space O(1)\n",
    "##### Adding to the queue should take Constant Time O(1) - Constant Space O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked List (Data Structure)\n",
    "\n",
    "A linked list is created by using the node class. We create a Node object and create another class to use this node object. We pass the appropriate values thorugh the node object to point the to the next data elements.\n",
    "\n",
    "There are some advantages and disadvantages with this data structure. **Advantages** Linked Lists can save memory because they can be flexibile with memory management which saves memory. **Disadvantages** Finding or adding to the list requires traversing the entire list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Complete Implementation of Linked List\n",
    "\n",
    "# 2 Classes - Node Class and Linked List Class\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a_linked_list = LinkedList()\n",
    "\n",
    "\n",
    "# Adding a new node the end of the list - O(n) - Linear Time\n",
    "start = time.time()\n",
    "\n",
    "for i in range(1000):\n",
    "    a_linked_list.append(i)\n",
    "\n",
    "end = time.time()\n",
    "\n",
    "print(end - start)\n",
    "\n",
    "# Adding a new node to the beginning of the list - O(1) - Constant Time\n",
    "start = time.time()\n",
    "\n",
    "for i in range(1000):\n",
    "    a_linked_list.push_on(i)\n",
    "\n",
    "end = time.time()\n",
    "\n",
    "print(end - start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Complete Implementation of Linked List\n",
    "​\n",
    "# 2 Classes - Node Class and Linked List Class\n",
    "​\n",
    "class Node:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "        \n",
    "    def __str__(self):\n",
    "        return self.value\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"<Node|{self.value}>\"\n",
    "    \n",
    "    \n",
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        # head attribute point to the first node of the linked list\n",
    "        self.head = None\n",
    "        \n",
    "    # Method that will return a node based on the value or return None if it does not exist\n",
    "    def __get_node(self, value_to_get):\n",
    "        # Start with the first node\n",
    "        node_to_check = self.head\n",
    "        # While the node to check is still a node\n",
    "        while node_to_check is not None:\n",
    "            # if the value of the node to check is equal to the value to get\n",
    "            if node_to_check.value == value_to_get:\n",
    "                return node_to_check\n",
    "            # if not, move on the next node\n",
    "            node_to_check = node_to_check.next\n",
    "        # Once node to check becomes None, we know that value to get is not in the linked list\n",
    "        return None\n",
    "        \n",
    "    # Method to add a new node to the front of the linked list\n",
    "    def push_on(self, new_value):\n",
    "        # Create a new node with the value passed in\n",
    "        new_node = Node(new_value)\n",
    "        # Set the new node's next attribute to be the current head\n",
    "        new_node.next = self.head\n",
    "        # Set the new node to be the front of the list (aka the head)\n",
    "        self.head = new_node\n",
    "        \n",
    "    # Method to print out all the nodes in the linked list\n",
    "    def traverse_list(self):\n",
    "        # Start at the beginning of the list\n",
    "        node = self.head\n",
    "        # While the node is not None, continue to loop\n",
    "        while node is not None:\n",
    "            # Print out the node (which will call the Node __str__ method)\n",
    "            print(node)\n",
    "            # Set the node to the next node in the Linked List\n",
    "            node = node.next\n",
    "            \n",
    "    # Method to add a new node to the end of the linked list\n",
    "    def append(self, new_value):\n",
    "        # Create a new node with the value passed in\n",
    "        new_node = Node(new_value)\n",
    "        # Check if the linked list is empty\n",
    "        if self.head is None:\n",
    "            # Set the head to the new node\n",
    "            self.head = new_node\n",
    "        # if not empty\n",
    "        else:\n",
    "            # traverse to the end of the list (aka the node.next is None)\n",
    "            node = self.head\n",
    "            while node.next is not None:\n",
    "                # move to the next node\n",
    "                node = node.next\n",
    "            # set the last node's next attribute to be the new node\n",
    "            node.next = new_node\n",
    "            \n",
    "    # Method to insert a node the linked list after a certain node (by value)\n",
    "    def insert_after(self, prev_value, new_value):\n",
    "        # Get the previous node by its value\n",
    "        prev_node = self.__get_node(prev_value)\n",
    "        # Check if the previous node exists\n",
    "        if prev_node is None:\n",
    "            print(f\"{prev_value} is not in the linked list\")\n",
    "        else:\n",
    "            # Create a new node with the new value passed in\n",
    "            new_node = Node(new_value)\n",
    "            # point the new node's .next to the previous node's .next\n",
    "            new_node.next = prev_node.next\n",
    "            # point the prev_node's next to the new node\n",
    "            prev_node.next = new_node\n",
    "        \n",
    "        \n",
    "weekdays = LinkedList()\n",
    "weekdays.push_on('Wednesday')\n",
    "weekdays.push_on('Monday')\n",
    "weekdays.append('Thursday')\n",
    "weekdays.append('Friday')\n",
    "weekdays.insert_after('Monday', 'Tuesday')\n",
    "weekdays.traverse_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Search Trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 1: Add a .remove method to the LinkedList\n",
    "\n",
    "Add a method to the LinkedList class to remove a node from the list.\n",
    "\n",
    "The method should take in a string of the value to remove and remove the node with that value from the LinkedList."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sunday\n",
      "Monday\n",
      "Tuesday\n",
      "Thursday\n",
      "Friday\n",
      "Saturday\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "        \n",
    "    def __str__(self):\n",
    "        return self.value\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"<Node|{self.value}>\"\n",
    "    \n",
    "    \n",
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        \n",
    "    def _get_node(self, value_to_get):\n",
    "        check = self.head\n",
    "        while check is not None:\n",
    "            if check.value == value_to_get:\n",
    "                return check\n",
    "            check = check.next\n",
    "        return None\n",
    "        \n",
    "    def push_on(self, new_value):\n",
    "        new_node = Node(new_value)\n",
    "        new_node.next = self.head\n",
    "        self.head = new_node\n",
    "        \n",
    "    def append(self, new_value):\n",
    "        new_node = Node(new_value)\n",
    "        \n",
    "        if self.head is None:\n",
    "            self.head = new_node\n",
    "        else:\n",
    "            node = self.head\n",
    "            while node.next is not None:\n",
    "                node = node.next\n",
    "            node.next = new_node\n",
    "            \n",
    "    def insert_after(self, prev_value, new_value):\n",
    "        prev_node = self._get_node(prev_value)\n",
    "        if prev_node is None:\n",
    "            print(f\"{prev_value} is not in linked list\")\n",
    "            return\n",
    "        \n",
    "        new_node = Node(new_value)\n",
    "        new_node.next = prev_node.next\n",
    "        prev_node.next = new_node\n",
    "        \n",
    "    def traverse_list(self):\n",
    "        node = self.head\n",
    "        while node:\n",
    "            print(node) \n",
    "            node = node.next\n",
    "    \n",
    "    def remove(self, value_to_remove):\n",
    "        node = self.head\n",
    "        \n",
    "        if node is not None and node.value == value_to_remove:\n",
    "            self.head = node.next\n",
    "            node = none\n",
    "            return\n",
    "        \n",
    "        prev_node = None\n",
    "        while node is not None and node.value != value_to_remove:\n",
    "            prev_node = node\n",
    "            node = node.next\n",
    "            \n",
    "        if node is None:\n",
    "            return\n",
    "        \n",
    "        prev_node.next = node.next\n",
    "        node = None\n",
    "            \n",
    "    \n",
    "weekdays = LinkedList()\n",
    "list_of_days = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday']\n",
    "for day in list_of_days:\n",
    "    weekdays.append(day)\n",
    "\n",
    "weekdays.remove('Wednesday')\n",
    "\n",
    "weekdays.traverse_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# please explain\n",
    "\n",
    "#     def remove(self, value_to_remove):\n",
    "#         node = self.head\n",
    "        \n",
    "#         if node is not None and node.value == value_to_remove:\n",
    "#             self.head = node.next\n",
    "#             node = none\n",
    "#             return\n",
    "        \n",
    "#         prev_node = None\n",
    "#         while node is not None and node.value != value_to_remove:\n",
    "#             prev_node = node\n",
    "#             node = node.next\n",
    "            \n",
    "#         if node is None:\n",
    "#             return\n",
    "        \n",
    "#         prev_node.next = node.next\n",
    "#         node = None\n",
    "# This is a Python function called remove that belongs to a linked list class. This function takes a parameter value_to_remove, which is the value that we want to remove from the linked list.\n",
    "\n",
    "# Here's a step-by-step breakdown of how the function works:\n",
    "\n",
    "# The function starts by setting the node variable to the head of the linked list.\n",
    "# If the head node exists and its value is equal to the value_to_remove, then we update the head node to be the next node in the list, and we set the current node to None. This means that we have successfully removed the value from the linked list, and we can return from the function.\n",
    "# If the value to remove is not at the head node, we start traversing the linked list using a while loop. Inside the loop, we keep track of the previous node using the prev_node variable, so that we can update its next attribute later if we need to.\n",
    "# The loop continues until we find a node whose value is equal to the value_to_remove, or until we reach the end of the linked list (i.e., node is None).\n",
    "# If we reach the end of the linked list without finding the value to remove, we simply return from the function.\n",
    "# If we do find the value to remove, we update the next attribute of the previous node to skip over the node we want to remove. Then, we set the current node to None to free up the memory used by the removed node.\n",
    "# Overall, this function effectively removes a node with a given value from the linked list."
   ]
  }
 ],
 "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.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}