udemy/algorithms-and-data-structures-in-python/data_structures_linked_lists.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Data Structures - Linked Lists\n",
    "\n",
    "### 3.1 Linked List Introduction - Basics\n",
    "\n",
    "#### Structure\n",
    "+ Composed of **nodes** and **references**, *i.e.* pointers indicating from one node to the other\n",
    "    + A single node contains data and reference\n",
    "    + The last reference points to a NULL: `n1 >> n2 >> n3 >> n4 >> NULL`\n",
    "    \n",
    "#### Characteristics\n",
    "+ Does not allow random access \n",
    "+ Requires sequential scanning for many basic operations\n",
    "    \n",
    "#### Advantages\n",
    "+ Supports dynamic structures\n",
    "+ Can allocate the needed memory in run-time\n",
    "+ Can store items with different sizes\n",
    "+ Easy to implement and grow organically\n",
    "    + does not need to know the size when growing\n",
    "\n",
    "#### Disadvantages\n",
    "+ Wastes memory due to the references\n",
    "+ Takes `O(N)` complexity for operations\n",
    "+ Hard to navigate backwards (reverse traversing)\n",
    "+ Solution: doubly linked lists are easier to read, but memory is still wasited in allocating space for a back pointer\n",
    "\n",
    "### 3.2 Linked List Introduction - Operations\n",
    "+ **Insertion**\n",
    "    + Inserting items at the beginning takes `O(1)` complexity\n",
    "        + `linked_list.insert_at_start(item)`\n",
    "    + To insert items at the end, we need to traverse until finding the last node pointing to a NULL, taking `O(N) + O(1) = O(N)` complexity\n",
    "        + `linked_list.insert_at_end(item)`\n",
    "+ **Deletion**\n",
    "    + Removing items at the beginning takes `O(1)` complexity\n",
    "        + `linked_list.remove_start()`\n",
    "    + Removing items at a given point takes `O(N) + O(1) = O(N)` complexity\n",
    "        + `linked_list.remove(item)`\n",
    "        \n",
    "### 3.3 Linked List Theory - Doubly Linked List\n",
    "+ To solve the problem of backward navigation, node class has two references, *i.e.* previous and next\n",
    "\n",
    "### 3.4 Linked List Introduction - Linked Lists vs Arrays\n",
    "\n",
    "#### Search\n",
    "+ ArrayList: takes `O(1)`, using random access with index\n",
    "+ LinkedList: takes `O(N)`, traversing through all the items\n",
    "\n",
    "#### Deletion (removing items from the beginning)\n",
    "+ ArrayList: takes `O(N)` where as removing the last item takes `O(1)`\n",
    "+ LinkedList: takes `O(1)`\n",
    "\n",
    "#### Memory Management\n",
    "+ ArrayList: does not need any extra memory\n",
    "+ LinkedList: needs extra memory for references\n",
    "\n",
    "#### Summary of Operations\n",
    "\n",
    "```python \n",
    "| Operation                  | LinkedList | ArrayList |\n",
    "| -------------------------- |:----------:|:---------:| \n",
    "| Search                     | O(N)       | O(1)      |\n",
    "| Insertion at the beginning | O(1)       | O(N)      |\n",
    "| Insertion at the end       | O(N)       | O(1)      |\n",
    "| Deletion at the beginning  | O(1)       | O(N)      |\n",
    "| Deletion at the end        | O(N)       | O(1)      |\n",
    "| Memory waste               | O(N)       | 0         |\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 3.5 Linked List Implementation - Insertion, Traversal, and Deletion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "class LinkedList(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.size = 0\n",
    "    \n",
    "    # Takes O(1)\n",
    "    def insert_start(self, data):\n",
    "        self.size += 1\n",
    "        node = Node(data)\n",
    "        \n",
    "        if not self.head:\n",
    "            self.head = node\n",
    "        else:\n",
    "            node.next = self.head\n",
    "            self.head = node\n",
    "    \n",
    "    # Takes O(1)\n",
    "    def get_size(self):\n",
    "        return self.size\n",
    "    \n",
    "    #Takes O(N)\n",
    "    '''\n",
    "    def get_size(self):\n",
    "        head = self.head\n",
    "        size = 0\n",
    "        \n",
    "        while head:\n",
    "            length += 1\n",
    "            head = head.next\n",
    "            \n",
    "        return size\n",
    "    '''\n",
    "    \n",
    "    def delete(self, data):\n",
    "        if self.head:\n",
    "            self.size -= 1\n",
    "            \n",
    "            curr = self.head\n",
    "            prev = None\n",
    "            \n",
    "            while curr.data != data:\n",
    "                prev = curr\n",
    "                curr = curr.next\n",
    "            \n",
    "            if prev == None:\n",
    "                self.head = curr.next\n",
    "            else:\n",
    "                prev.next = curr.next        \n",
    "    \n",
    "    #Takes O(N)\n",
    "    def insert_end(self, data):\n",
    "        self.size += 1\n",
    "        node = Node(data)\n",
    "        head = self.head\n",
    "        \n",
    "        while head.next:\n",
    "            head = head.next\n",
    "            \n",
    "        head.next = node\n",
    "        \n",
    "    def traverse(self):\n",
    "        head = self.head\n",
    "        \n",
    "        while head:\n",
    "            print '{}'.format(head.data)\n",
    "            head = head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "None\n",
      "\n",
      "Size of the linked list: 3\n",
      "1\n",
      "3\n",
      "None\n",
      "\n",
      "Size of the linked list: 2\n"
     ]
    }
   ],
   "source": [
    "# Test LinkedLIst\n",
    "\n",
    "# Instatiate LinkedList\n",
    "linked_list = LinkedList()\n",
    "\n",
    "# Insert items\n",
    "linked_list.insert_start(2)\n",
    "linked_list.insert_start(1)\n",
    "linked_list.insert_end(3)\n",
    "\n",
    "print linked_list.traverse()\n",
    "print\n",
    "print 'Size of the linked list: {}'.format(linked_list.get_size())\n",
    "\n",
    "linked_list.delete(2)\n",
    "\n",
    "print linked_list.traverse()\n",
    "print\n",
    "print 'Size of the linked list: {}'.format(linked_list.get_size())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.6 Quiz\n",
    "+ Why do we use linked lists over arrays?\n",
    "    1. Because linked lists are memory friendly, so we should use linked lists in order to save some space\n",
    "    2. Because it is easier to sort a linked list\n",
    "    3. **Because it is faster to insert at the beginning of the list as we do not have to rearrange the array, just update the references accordingly**  \n",
    "    \n",
    "    \n",
    "+ When will we end up with an `O(N)` algorithm as far as arrays are concerned?\n",
    "    1. When we try to sort an array\n",
    "    2. When we insert items at the end of the list\n",
    "    3. **When we insert items at the beginning of the list**  \n",
    "    \n",
    "    \n",
    "+ Which data structure do we choose if we aim to minimize the amount of memory to store data?\n",
    "    1. **Array**\n",
    "    2. Linked list"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}