5.1_Linked_Lists.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "## Linked Lists #\n",
    "---\n",
    "\n",
    "### What is a \"Linked List\"? ###\n",
    "Linked lists is a data structure that stores information with pointers and nodes!\n",
    "\n",
    "For this homework set, you will consider what we call \"Singly Linked\" Lists.\n",
    "\n",
    "They are usually represented in arrow notation like this:\n",
    "\n",
    "$$ \\mbox{1} \\rightarrow \\mbox{2} \\rightarrow \\mbox {4} \\rightarrow \\mbox{5} $$\n",
    "\n",
    "This means we have a linked list that has a `1` then a `2` then a `4` then a `5`.\n",
    "\n",
    "By notation, we call the first element a \"head\" and the last element a \"tail\".\n",
    "\n",
    "You can go [here](https://visualgo.net/list) for a visualizer. I recommend going over this over before reading my examples.\n",
    "\n",
    "### Why Linked Lists? ###\n",
    "Linked Lists are often shied away from their cousin, the Array. In terms of sequential storage, arrays are much more intuitive and faster to access elements.\n",
    "\n",
    "The intuition is this: let's make a shopping list.\n",
    "\n",
    "So we have two options here: make it on a single page of lined paper that we have, or tape small pieces of paper together.\n",
    "\n",
    "Unfortunately, our single page of binder paper is cheap. We only have 5 lines on the paper.\n",
    "\n",
    "We want to buy a Potato, Lettuce, Orange, Homework 1 Answers for CS 196, and 5 Bitcoins at your local supermarket.\n",
    "\n",
    "Our \"array\" (binder paper) looks like this:\n",
    "\n",
    "| Shopping List (Binder Paper)            |\n",
    "|-------------------------|\n",
    "| Potato                  |\n",
    "| Lettuce                 |\n",
    "| Orange                  |\n",
    "| Homework 1 Answers      |\n",
    "| 5 Bitcoins              |\n",
    "\n",
    "Our \"linked list\" (pieces of small paper taped togther) looks like this:\n",
    "\n",
    "$$\\text{Potato} \\leftrightharpoons \\text{Lettuce} \\leftrightharpoons \\text{Orange} \\leftrightharpoons \\text{Homework 1 Answers} \\leftrightharpoons \\text{5 Bitcoins}$$\n",
    "\n",
    "So we have 2 representations for the same thing.\n",
    "\n",
    "But your roommate just called and said \"Hey we need a new microwave because the one we have right now just broke when I microwaved aluminum\".\n",
    "\n",
    "So we need to add \"microwave\" to our shopping list.\n",
    "\n",
    "Let's say we are adding microwave to the Binder Paper\n",
    "\n",
    "| Shopping List (Binder Paper)              |\n",
    "|-------------------------|\n",
    "| Potato                  |\n",
    "| Lettuce                 |\n",
    "| Orange                  |\n",
    "| Homework 1 Answers      |\n",
    "| 5 Bitcoins              |\n",
    "\n",
    "But wait! We don't have any space. We'll have to buy new, more expensive paper with 6 lines instead of 5 to fit everything. Not only that, we'll have to copy the entire list just to get a new shopping list.\n",
    "\n",
    "| Shopping List (Binder Paper with 6 lines)  |\n",
    "|-------------------------------|\n",
    "| Potato                        |\n",
    "| Lettuce                       |\n",
    "| Orange                        |\n",
    "| Homework 1 Answers            |\n",
    "| 5 Bitcoins                    |\n",
    "| Microwave                     |\n",
    "\n",
    "That was a lot of work just to get microwave on the shopping list.\n",
    "\n",
    "But, look at our taped up shopping list.\n",
    "\n",
    "$$\\text{Potato} \\leftrightharpoons \\text{Lettuce} \\leftrightharpoons \\text{Orange} \\leftrightharpoons \\text{Homework 1 Answers} \\leftrightharpoons \\text{5 Bitcoins}$$\n",
    "\n",
    "We can just write \"microwave\" on a piece of paper, then tape it to the last (or first) one!\n",
    "\n",
    "$$\\text{Microwave} \\leftrightharpoons \\text{Potato} \\leftrightharpoons \\text{Lettuce} \\leftrightharpoons \\text{Orange} \\leftrightharpoons \\text{Homework 1 Answers} \\leftrightharpoons \\text{5 Bitcoins}$$\n",
    "\n",
    "But we could just by 6 lines of binder paper to begin with! Yes, we could've gotten a larger binder paper to begin with, but if we didn't know how many items we had on our list, it's hard to buy the right binder paper.\n",
    "\n",
    "### Practical Examples: Linked List vs Array ###\n",
    "Here is an example of Insertions and Deletions\n",
    "#### Array: Insertion ####\n",
    "$$ \\boxed{1} \\boxed{2} \\boxed{4} \\boxed{5} \\boxed{10} \\boxed{12}$$\n",
    "\n",
    "We want to insert a 1000 in the 3rd element.\n",
    "\n",
    "First, we need to make space for the 3rd parameter to do that we'll need to shift a lot of elements to the right.\n",
    "\n",
    "$$ \\boxed{1} \\boxed{2} \\boxed{4} \\boxed{empty space} \\boxed{5} \\boxed{10} \\boxed{12}$$\n",
    "\n",
    "And we moved 3 elements just to insert a 3rd.\n",
    "\n",
    "$$ \\boxed{1} \\boxed{2} \\boxed{4} \\boxed{1000} \\boxed{5} \\boxed{10} \\boxed{12}$$\n",
    "\n",
    "#### List: Insertion ####\n",
    "$$ 1 \\rightarrow 2 \\rightarrow 4 \\rightarrow 5 \\rightarrow 10 \\rightarrow 12 $$\n",
    "\n",
    "Remember that list is made of references to the next node (formally known as `pointers`)\n",
    "\n",
    "If we want to insert a 1000 in the 3rd element, we can just \"pretend\" we shifted everything by swapping pointers!\n",
    "\n",
    "$$ 1 \\rightarrow 2 \\rightarrow 4 \\rightarrow NEW NODE \\rightarrow 5 \\rightarrow 10 \\rightarrow 12 $$\n",
    "\n",
    "$$ 1 \\rightarrow 2 \\rightarrow 4 \\rightarrow 1000 \\rightarrow 5 \\rightarrow 10 \\rightarrow 12 $$\n",
    "\n",
    "Even though it looks like we moved 3 elements, we actually did not move at all!\n",
    "\n",
    "#### Array: Deletion ####\n",
    "$$ \\boxed{1} \\boxed{2} \\boxed{4} \\boxed{1000} \\boxed{5} \\boxed{10} \\boxed{12}$$\n",
    "\n",
    "Suppose we want to remove the 1000 we just inserted.\n",
    "\n",
    "We work backwards. So we \"delete\" by shifting everything to the left.\n",
    "\n",
    "$$ \\boxed{1} \\boxed{2} \\boxed{4} \\boxed{5} \\boxed{10} \\boxed{12}$$\n",
    "\n",
    "\n",
    "#### List: Insertion ####\n",
    "$$ 1 \\rightarrow 2 \\rightarrow 4 \\rightarrow 1000 \\rightarrow 5 \\rightarrow 10 \\rightarrow 12 $$\n",
    "\n",
    "Suppose we want to remove the 1000 we just inserted.\n",
    "\n",
    "We work backwards. So we just remove the reference, and just \"shift\" by modifying pointers!\n",
    "\n",
    "$$ 1 \\rightarrow 2 \\rightarrow 4 \\rightarrow 5 \\rightarrow 10 \\rightarrow 12 $$\n",
    "\n",
    "### Why Linked Lists? (Formally) ###\n",
    "Someone in lecture, we talk about runtime. More formally, the runtime is represented in big-O notation, saying that the growth rate of the runtime has some special property.\n",
    "\n",
    "So, when we say \"insertion takes O(n)\" (pronounced oh-s of enn) we mean insertion grows linearly with the data elements, when there are `n` data elements. When we say \"insertion takes O(1)\" (pronounced oh-s of one), we mean insertion does not grow (stays constant) with the data, when there are `n` elements. You will learn this formally in CS 173.\n",
    "\n",
    "| Operation | Array         | Linked Lists |\n",
    "|-----------|---------------|--------------|\n",
    "| Insertion | O(n)      | O(1)     |\n",
    "| Deletion  | O(n)      | O(1)     |\n",
    "| Element Access | O(1)      | O(n) worst case  |\n",
    "\n",
    "As you can see, Linked Lists are better when we need to do a lot of write/delete operations!\n",
    "\n",
    "Disclaimer: You will learn in CS225 that is not so true after all.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# Node Class #\n",
    "---\n",
    "\n",
    "You are allowed to modify the class as much as you like, except the `self.data` and `self.next` parameters. Our tests depend on `self.data` containing data, and `self.next` containing the next node, so failure to do so will result in an automatic 0.\n",
    "\n",
    "You can add methods as much as you'd like, for example, it might be helpful to write a function that gets you the nth element in a linked list!\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "autoscroll": "json-false",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, data=None, next_node=None):\n",
    "        \"\"\"\n",
    "        Initializes Node in Linked List.\n",
    "        \"\"\"\n",
    "        self.data = data\n",
    "        self.next = next_node\n",
    "\n",
    "\n",
    "    def __str__(self):\n",
    "        \"\"\"\n",
    "        Converts current linked list to a string.\n",
    "        \"\"\"\n",
    "        node = self\n",
    "        buffer = str(node.data)\n",
    "\n",
    "        node = node.next\n",
    "        while node != None:\n",
    "            buffer += ' -> ' + str(node.data)\n",
    "            node = node.next\n",
    "\n",
    "        return buffer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "We've provided an interface to print your functions. You can use `print(node)` to print out the entire linked list, starting from node. Here are examples (which you can run) to show it off."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "autoscroll": "json-false",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Linked List with only one element\n",
      "1\n",
      "Linked List with two elements\n",
      "1 -> 2\n",
      "Linked List with three elements.\n",
      "1 -> 2 -> 4\n",
      "Printing an intermediary linked list\n",
      "2 -> 4\n",
      "Linked List with many types of elements\n",
      "1 -> 2 -> 4 -> 10 -> ['we', 'can', 'store', 'other', 'objects'] -> Second to last -> last\n"
     ]
    }
   ],
   "source": [
    "print(\"Linked List with only one element\")\n",
    "linked_list = Node(1)\n",
    "print(linked_list)\n",
    "\n",
    "print(\"Linked List with two elements\")\n",
    "next_node = Node(2)\n",
    "linked_list.next = next_node\n",
    "print(linked_list)\n",
    "\n",
    "print(\"Linked List with three elements.\")\n",
    "next_node.next = Node(4) # Notice that linked_list.next.next is the same as next_node.next\n",
    "print(linked_list)\n",
    "\n",
    "print(\"Printing an intermediary linked list\")\n",
    "print(next_node)\n",
    "\n",
    "print(\"Linked List with many types of elements\")\n",
    "linked_list.next.next.next = Node(10)\n",
    "linked_list.next.next.next.next = Node(['we', 'can', 'store', 'other', 'objects'])\n",
    "linked_list.next.next.next.next.next = Node(\"Second to last\")\n",
    "linked_list.next.next.next.next.next.next = Node(\"last\")\n",
    "print(linked_list)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# List to Linked List\n",
    "---\n",
    "Given a normal list, convert it into a linked list, with the first index as the head. RETURN the head node.\n",
    "\n",
    "## Example(s):\n",
    "---\n",
    "* Example 1:\n",
    "    * Input: \n",
    "        * `[1, 2, 5, 7]`:\n",
    "\n",
    "    * Output: \n",
    "        * `(head)1 -> 2 -> 5 -> 7`\n",
    "  \n",
    "* Example 2:\n",
    "    * Input: \n",
    "        * `[3, 4, 0, 9]`\n",
    "\n",
    "    * Output: \n",
    "        * `(head)3 -> 4 -> 0 -> 9`\n",
    "  \n",
    "## Parameters\n",
    "-----------\n",
    "* `list` : `norm`\n",
    "    - The list to be turned into a linked list\n",
    "\n",
    "\n",
    "## Returns\n",
    "-------\n",
    "* `Node`: Head of the resultant linked list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "autoscroll": "json-false",
    "collapsed": false,
    "deletable": true,
    "editable": true,
    "ein.tags": [
     "worksheet-0"
    ],
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def list_to_linked_list(norm):\n",
    "    pass"
   ]
  }
 ],
 "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.0"
  },
  "name": "HOMEWORK.ipynb"
 },
 "nbformat": 4,
 "nbformat_minor": 2
}