sec18-19-DS-single-linked-list.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/learn/lecture/9816152#notes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Section 18: Data Structure Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Section 19: Singly-Linked Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Push"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val;\n",
    "        self.next = None;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "first = Node('Hi!')\n",
    "first.next = Node('there')\n",
    "first.next.next = Node('how')\n",
    "first.next.next.next = Node('are')\n",
    "first.next.next.next.next = Node('you')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create push to points the tail to new node\n",
    "class SinglyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.length = 0\n",
    "        \n",
    "    def push(self, val):\n",
    "        # If no node detected\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        else:\n",
    "            self.tail.next = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        self.length += 1\n",
    "        \n",
    "        return self"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'head': None, 'tail': None, 'length': 0}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Let's see how it works\n",
    "sll = SinglyLinkedList()\n",
    "vars(sll)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'val': 'Hi', 'next': None}\n",
      "{'val': 'Hi', 'next': None}\n"
     ]
    }
   ],
   "source": [
    "sll.push(\"Hi\")\n",
    "print(vars(sll.head))\n",
    "print(vars(sll.tail))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'val': 'Hi', 'next': <__main__.Node object at 0x00000207E59B6E88>}\n",
      "<__main__.Node object at 0x00000207E59B6E88>\n",
      "{'val': 'Batman', 'next': None}\n",
      "{'val': 'Batman', 'next': None}\n"
     ]
    }
   ],
   "source": [
    "sll.push(\"Batman\")\n",
    "print(vars(sll.head))\n",
    "print(sll.tail)\n",
    "print(vars(sll.head.next))\n",
    "print(vars(sll.tail))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'val': 'Hi', 'next': <__main__.Node object at 0x00000207E59B6E88>}\n",
      "\n",
      "At node: <__main__.Node object at 0x00000207E59B6E88>,\n",
      " content: {'val': 'Batman', 'next': <__main__.Node object at 0x00000207E59C5048>}\n",
      "\n",
      "At node: <__main__.Node object at 0x00000207E59C5048>, \n",
      " content: {'val': 'Begins', 'next': None} \n"
     ]
    }
   ],
   "source": [
    "sll.push(\"Begins\")\n",
    "print(f\"{vars(sll.head)}\")\n",
    "print('')\n",
    "print(f\"At node: {sll.head.next},\\n content: {vars(sll.head.next)}\")\n",
    "print('')\n",
    "print(f\"At node: {sll.tail}, \\n content: {vars(sll.tail)} \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Adding traverse method\n",
    "# Create push to points the tail to new node\n",
    "class SinglyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.length = 0\n",
    "        \n",
    "    def push(self, val):\n",
    "        # If no node detected\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        else:\n",
    "            self.tail.next = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    def pop(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        newTail = self.head\n",
    "        \n",
    "        while(current.next):\n",
    "            newTail = current            \n",
    "            current = current.next\n",
    "        \n",
    "        # Update list\n",
    "        self.tail      = newTail\n",
    "        self.tail.next = None\n",
    "        self.length   -= 1\n",
    "        if self.length == 0:\n",
    "            self.head = None\n",
    "            self.tail = None\n",
    "        \n",
    "        return current"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.SinglyLinkedList at 0x207e59c5dc8>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sll = SinglyLinkedList()\n",
    "sll.push(\"Hi\")\n",
    "sll.push(\"Bye\")\n",
    "sll.push(\"Wowza\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'val': 'Wowza', 'next': None}\n",
      "{'head': <__main__.Node object at 0x00000207E59C5CC8>, 'tail': <__main__.Node object at 0x00000207E59C5E08>, 'length': 2}\n"
     ]
    }
   ],
   "source": [
    "c = sll.pop()\n",
    "print(f\"{vars(c)}\")\n",
    "print(f\"{vars(sll)}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'head': <__main__.Node object at 0x00000207E59C5CC8>, 'tail': <__main__.Node object at 0x00000207E59C5E08>, 'length': 2}\n",
      "{'val': 'Hi', 'next': <__main__.Node object at 0x00000207E59C5E08>}\n",
      "{'val': 'Bye', 'next': None}\n"
     ]
    }
   ],
   "source": [
    "# Wowza is removed\n",
    "print(f'{vars(sll)}')\n",
    "print(f'{vars(sll.head)}')\n",
    "print(f'{vars(sll.tail)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shifting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add shifting\n",
    "class SinglyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.length = 0\n",
    "    \n",
    "    # === PUSH ===\n",
    "    def push(self, val):\n",
    "        # If no node detected\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        else:\n",
    "            self.tail.next = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    # === POP ===\n",
    "    def pop(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        newTail = self.head\n",
    "        \n",
    "        while(current.next):\n",
    "            newTail = current            \n",
    "            current = current.next\n",
    "        \n",
    "        # Update list\n",
    "        self.tail      = newTail\n",
    "        self.tail.next = None\n",
    "        self.length   -= 1\n",
    "        if self.length == 0:\n",
    "            self.head = None\n",
    "            self.tail = None\n",
    "        \n",
    "        return current\n",
    "    \n",
    "    # == SHIFT == \n",
    "    def shift(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        remove    = self.head\n",
    "        self.head = self.head.next\n",
    "        \n",
    "        self.length -= 1\n",
    "        \n",
    "        if self.length == 0:\n",
    "            self.tail = None\n",
    "        \n",
    "        return remove"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.SinglyLinkedList at 0x207e59d4908>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sll = SinglyLinkedList()\n",
    "sll.push(\"Hi\")\n",
    "sll.push(\"Bye\")\n",
    "sll.push(\"Wowza\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'val': 'Hi', 'next': <__main__.Node at 0x207e59d4988>}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vars(sll.shift())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'head': <__main__.Node object at 0x00000207E59D4988>, 'tail': <__main__.Node object at 0x00000207E59D4A48>, 'length': 2}\n",
      "Tail: {'val': 'Wowza', 'next': None}\n"
     ]
    }
   ],
   "source": [
    "# First element is removed\n",
    "print(f\"{vars(sll)}\")\n",
    "# print(f\"Head: {vars(sll.head)}\")\n",
    "print(f\"Tail: {vars(sll.tail)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Unshift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add shifting\n",
    "class SinglyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.length = 0\n",
    "    \n",
    "    # === PUSH ===\n",
    "    def push(self, val):\n",
    "        # If no node detected\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        else:\n",
    "            self.tail.next = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    # === POP ===\n",
    "    def pop(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        newTail = self.head\n",
    "        \n",
    "        while(current.next):\n",
    "            newTail = current            \n",
    "            current = current.next\n",
    "        \n",
    "        # Update list\n",
    "        self.tail      = newTail\n",
    "        self.tail.next = None\n",
    "        self.length   -= 1\n",
    "        if self.length == 0:\n",
    "            self.head = None\n",
    "            self.tail = None\n",
    "        \n",
    "        return current\n",
    "    \n",
    "    # == SHIFT == \n",
    "    def shift(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        remove    = self.head\n",
    "        self.head = self.head.next\n",
    "        \n",
    "        self.length -= 1\n",
    "        \n",
    "        if self.length == 0:\n",
    "            self.tail = None\n",
    "        \n",
    "        return remove\n",
    "    \n",
    "    # == UNSHIFT ==\n",
    "    def unshift(self, val):\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        # If no head exists\n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "        else:\n",
    "            # If head exists\n",
    "            newNode.next = self.head\n",
    "            self.head    = newNode \n",
    "        \n",
    "        self.length += 1\n",
    "        \n",
    "        return self"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'val': 5, 'next': None}"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vars(Node(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'head': <__main__.Node object at 0x00000207E59C0788>, 'tail': <__main__.Node object at 0x00000207E59C0788>, 'length': 1}\n",
      "{'val': 100, 'next': None}\n"
     ]
    }
   ],
   "source": [
    "sll = SinglyLinkedList()\n",
    "sll.unshift(100)\n",
    "print(f\"{vars(sll)}\")\n",
    "print(f\"{vars(sll.head)}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'head': <__main__.Node object at 0x00000207E59D1488>, 'tail': <__main__.Node object at 0x00000207E59C0788>, 'length': 2}\n",
      "{'val': 100, 'next': <__main__.Node object at 0x00000207E59C0788>}\n",
      "{'val': 50, 'next': None}\n"
     ]
    }
   ],
   "source": [
    "sll = SinglyLinkedList()\n",
    "sll.push(50)\n",
    "sll.unshift(100)\n",
    "print(f\"{vars(sll)}\")\n",
    "print(f\"{vars(sll.head)}\")\n",
    "print(f\"{vars(sll.head.next)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Get"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add shifting\n",
    "class SinglyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.length = 0\n",
    "    \n",
    "    # === PUSH ===\n",
    "    def push(self, val):\n",
    "        # If no node detected\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        else:\n",
    "            self.tail.next = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    # === POP ===\n",
    "    def pop(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        newTail = self.head\n",
    "        \n",
    "        while(current.next):\n",
    "            newTail = current            \n",
    "            current = current.next\n",
    "        \n",
    "        # Update list\n",
    "        self.tail      = newTail\n",
    "        self.tail.next = None\n",
    "        self.length   -= 1\n",
    "        if self.length == 0:\n",
    "            self.head = None\n",
    "            self.tail = None\n",
    "        \n",
    "        return current\n",
    "    \n",
    "    # == SHIFT == \n",
    "    def shift(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        remove    = self.head\n",
    "        self.head = self.head.next\n",
    "        \n",
    "        self.length -= 1\n",
    "        \n",
    "        if self.length == 0:\n",
    "            self.tail = None\n",
    "        \n",
    "        return remove\n",
    "    \n",
    "    # == UNSHIFT ==\n",
    "    def unshift(self, val):\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        # If no head exists\n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "        else:\n",
    "            # If head exists\n",
    "            newNode.next = self.head\n",
    "            self.head    = newNode \n",
    "        \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    # == GET == \n",
    "    def get(self, idx):\n",
    "        if idx < 0 or idx >= self.length:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        \n",
    "        for i in range(idx):\n",
    "            current = current.next\n",
    "            \n",
    "        return current"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.SinglyLinkedList at 0x207e59d6c48>"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sll = SinglyLinkedList()\n",
    "sll.push('The')\n",
    "sll.push('Cake')\n",
    "sll.push('Is')\n",
    "sll.push('A')\n",
    "sll.push('Lie')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'head': <__main__.Node object at 0x00000207E59D6CC8>, 'tail': <__main__.Node object at 0x00000207E59D4548>, 'length': 5}\n",
      "<__main__.Node object at 0x00000207E59D6CC8>\n"
     ]
    }
   ],
   "source": [
    "print(f\"{vars(sll)}\")\n",
    "print(sll.get(0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add shifting\n",
    "class SinglyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.length = 0\n",
    "    \n",
    "    # === PUSH ===\n",
    "    def push(self, val):\n",
    "        # If no node detected\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        else:\n",
    "            self.tail.next = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    # === POP ===\n",
    "    def pop(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        newTail = self.head\n",
    "        \n",
    "        while(current.next):\n",
    "            newTail = current            \n",
    "            current = current.next\n",
    "        \n",
    "        # Update list\n",
    "        self.tail      = newTail\n",
    "        self.tail.next = None\n",
    "        self.length   -= 1\n",
    "        if self.length == 0:\n",
    "            self.head = None\n",
    "            self.tail = None\n",
    "        \n",
    "        return current\n",
    "    \n",
    "    # == SHIFT == \n",
    "    def shift(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        remove    = self.head\n",
    "        self.head = self.head.next\n",
    "        \n",
    "        self.length -= 1\n",
    "        \n",
    "        if self.length == 0:\n",
    "            self.tail = None\n",
    "        \n",
    "        return remove\n",
    "    \n",
    "    # == UNSHIFT ==\n",
    "    def unshift(self, val):\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        # If no head exists\n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "        else:\n",
    "            # If head exists\n",
    "            newNode.next = self.head\n",
    "            self.head    = newNode \n",
    "        \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    # == GET == \n",
    "    def get(self, idx):\n",
    "        if idx < 0 or idx >= self.length:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        \n",
    "        for i in range(idx):\n",
    "            current = current.next\n",
    "            \n",
    "        return current\n",
    "    \n",
    "    # == SET ==\n",
    "    def set(self, idx, val):\n",
    "        \n",
    "        node = self.get(idx)\n",
    "        \n",
    "        if node:\n",
    "            node.val = val\n",
    "            return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.SinglyLinkedList at 0x207e59da588>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sll = SinglyLinkedList()\n",
    "sll.push('Hi')\n",
    "sll.push('Hello')\n",
    "sll.push('Good')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sll.set(1, 'Thor')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'head': <__main__.Node object at 0x00000207E59DA408>, 'tail': <__main__.Node object at 0x00000207E59DA548>, 'length': 3}\n",
      "{'val': 'Hi', 'next': <__main__.Node object at 0x00000207E59DA708>}\n",
      "{'val': 'Thor', 'next': <__main__.Node object at 0x00000207E59DA548>}\n",
      "{'val': 'Good', 'next': None}\n"
     ]
    }
   ],
   "source": [
    "# Here the 'Hello' is replaced with 'Thor'\n",
    "print(f\"{vars(sll)}\")\n",
    "print(f\"{vars(sll.get(0))}\")\n",
    "print(f\"{vars(sll.get(1))}\")\n",
    "print(f\"{vars(sll.get(2))}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Insert"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add shifting\n",
    "class SinglyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.length = 0\n",
    "    \n",
    "    # === PUSH ===\n",
    "    def push(self, val):\n",
    "        # If no node detected\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        else:\n",
    "            self.tail.next = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    # === POP ===\n",
    "    def pop(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        newTail = self.head\n",
    "        \n",
    "        while(current.next):\n",
    "            newTail = current            \n",
    "            current = current.next\n",
    "        \n",
    "        # Update list\n",
    "        self.tail      = newTail\n",
    "        self.tail.next = None\n",
    "        self.length   -= 1\n",
    "        if self.length == 0:\n",
    "            self.head = None\n",
    "            self.tail = None\n",
    "        \n",
    "        return current\n",
    "    \n",
    "    # == SHIFT == \n",
    "    def shift(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        remove    = self.head\n",
    "        self.head = self.head.next\n",
    "        \n",
    "        self.length -= 1\n",
    "        \n",
    "        if self.length == 0:\n",
    "            self.tail = None\n",
    "        \n",
    "        return remove\n",
    "    \n",
    "    # == UNSHIFT ==\n",
    "    def unshift(self, val):\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        # If no head exists\n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "        else:\n",
    "            # If head exists\n",
    "            newNode.next = self.head\n",
    "            self.head    = newNode \n",
    "        \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    # == GET == \n",
    "    def get(self, idx):\n",
    "        if idx < 0 or idx >= self.length:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        \n",
    "        for i in range(idx):\n",
    "            current = current.next\n",
    "            \n",
    "        return current\n",
    "    \n",
    "    # == SET ==\n",
    "    def set(self, idx, val):\n",
    "        \n",
    "        node = self.get(idx)\n",
    "        \n",
    "        if node:\n",
    "            node.val = val\n",
    "            return True\n",
    "        \n",
    "        return False\n",
    "    \n",
    "    # == INSERT ==\n",
    "    def insert(self, idx, val):\n",
    "        if idx < 0 or idx > self.length:\n",
    "            return False\n",
    "        \n",
    "        if idx == 0:\n",
    "            self.unshift(val)\n",
    "            return True\n",
    "        elif idx == self.length:\n",
    "            self.push(val)\n",
    "            return True\n",
    "        else:\n",
    "            newNode = Node(val)\n",
    "            \n",
    "            preNode      = self.get(idx-1)\n",
    "            nextNode     = self.get(idx)\n",
    "            preNode.next = newNode\n",
    "            newNode.next = nextNode \n",
    "        \n",
    "        self.length += 1\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.SinglyLinkedList at 0x207e59c5f48>"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sll = SinglyLinkedList()\n",
    "sll.push('Hi')\n",
    "sll.push('Hello')\n",
    "sll.push('Bye')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sll.insert(2, 'Cheerio')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'head': <__main__.Node object at 0x00000207E59C5388>, 'tail': <__main__.Node object at 0x00000207E59C5508>, 'length': 4}\n",
      "{'val': 'Hi', 'next': <__main__.Node object at 0x00000207E59C5988>}\n",
      "{'val': 'Hello', 'next': <__main__.Node object at 0x00000207E59D2788>}\n",
      "{'val': 'Cheerio', 'next': <__main__.Node object at 0x00000207E59C5508>}\n",
      "{'val': 'Bye', 'next': None}\n"
     ]
    }
   ],
   "source": [
    "print(vars(sll))\n",
    "print(vars(sll.get(0)))\n",
    "print(vars(sll.get(1)))\n",
    "print(vars(sll.get(2)))\n",
    "print(vars(sll.get(3)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Remove"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add shifting\n",
    "class SinglyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.length = 0\n",
    "    \n",
    "    # === PUSH ===\n",
    "    def push(self, val):\n",
    "        # If no node detected\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        else:\n",
    "            self.tail.next = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    # === POP ===\n",
    "    def pop(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        newTail = self.head\n",
    "        \n",
    "        while(current.next):\n",
    "            newTail = current            \n",
    "            current = current.next\n",
    "        \n",
    "        # Update list\n",
    "        self.tail      = newTail\n",
    "        self.tail.next = None\n",
    "        self.length   -= 1\n",
    "        if self.length == 0:\n",
    "            self.head = None\n",
    "            self.tail = None\n",
    "        \n",
    "        return current\n",
    "    \n",
    "    # == SHIFT == \n",
    "    def shift(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        remove    = self.head\n",
    "        self.head = self.head.next\n",
    "        \n",
    "        self.length -= 1\n",
    "        \n",
    "        if self.length == 0:\n",
    "            self.tail = None\n",
    "        \n",
    "        return remove\n",
    "    \n",
    "    # == UNSHIFT ==\n",
    "    def unshift(self, val):\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        # If no head exists\n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "        else:\n",
    "            # If head exists\n",
    "            newNode.next = self.head\n",
    "            self.head    = newNode \n",
    "        \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    # == GET == \n",
    "    def get(self, idx):\n",
    "        if idx < 0 or idx >= self.length:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        \n",
    "        for i in range(idx):\n",
    "            current = current.next\n",
    "            \n",
    "        return current\n",
    "    \n",
    "    # == SET ==\n",
    "    def set(self, idx, val):\n",
    "        \n",
    "        node = self.get(idx)\n",
    "        \n",
    "        if node:\n",
    "            node.val = val\n",
    "            return True\n",
    "        \n",
    "        return False\n",
    "    \n",
    "    # == INSERT ==\n",
    "    def insert(self, idx, val):\n",
    "        if idx < 0 or idx > self.length:\n",
    "            return False\n",
    "        \n",
    "        if idx == 0:\n",
    "            self.unshift(val)\n",
    "            return True\n",
    "        elif idx == self.length:\n",
    "            self.push(val)\n",
    "            return True\n",
    "        else:\n",
    "            newNode = Node(val)\n",
    "            \n",
    "            preNode      = self.get(idx-1)\n",
    "            nextNode     = self.get(idx)\n",
    "            preNode.next = newNode\n",
    "            newNode.next = nextNode \n",
    "        \n",
    "        self.length += 1\n",
    "        \n",
    "        return True\n",
    "    \n",
    "    # == REMOVE == \n",
    "    def remove(self, idx):\n",
    "        if idx < 0 or idx >= self.length:\n",
    "            return False\n",
    "        \n",
    "        if idx == 0:\n",
    "            self.shift()\n",
    "            return True\n",
    "        elif idx == self.length - 1:\n",
    "            self.pop()\n",
    "            return True\n",
    "        \n",
    "        preNode = self.get(idx - 1)\n",
    "        nextNode= preNode.next.next\n",
    "        preNode.next = nextNode\n",
    "            \n",
    "        self.length -= 1\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.SinglyLinkedList at 0x207e59fc208>"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sll = SinglyLinkedList()\n",
    "sll.push('Hi')\n",
    "sll.push('Hello')\n",
    "sll.push('Yeaa')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sll.remove(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'head': <__main__.Node object at 0x00000207E59FC788>, 'tail': <__main__.Node object at 0x00000207E59FC108>, 'length': 2}\n",
      "{'val': 'Hi', 'next': <__main__.Node object at 0x00000207E59FC108>}\n",
      "{'val': 'Yeaa', 'next': None}\n"
     ]
    }
   ],
   "source": [
    "print(vars(sll))\n",
    "print(vars(sll.get(0)))\n",
    "print(vars(sll.get(1)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reverse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add shifting\n",
    "class SinglyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.length = 0\n",
    "    \n",
    "    # === PUSH ===\n",
    "    def push(self, val):\n",
    "        # If no node detected\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        else:\n",
    "            self.tail.next = newNode\n",
    "            self.tail = newNode\n",
    "            \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    # === POP ===\n",
    "    def pop(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        newTail = self.head\n",
    "        \n",
    "        while(current.next):\n",
    "            newTail = current            \n",
    "            current = current.next\n",
    "        \n",
    "        # Update list\n",
    "        self.tail      = newTail\n",
    "        self.tail.next = None\n",
    "        self.length   -= 1\n",
    "        if self.length == 0:\n",
    "            self.head = None\n",
    "            self.tail = None\n",
    "        \n",
    "        return current\n",
    "    \n",
    "    # == SHIFT == \n",
    "    def shift(self):\n",
    "        if not self.head:\n",
    "            return None\n",
    "        \n",
    "        remove    = self.head\n",
    "        self.head = self.head.next\n",
    "        \n",
    "        self.length -= 1\n",
    "        \n",
    "        if self.length == 0:\n",
    "            self.tail = None\n",
    "        \n",
    "        return remove\n",
    "    \n",
    "    # == UNSHIFT ==\n",
    "    def unshift(self, val):\n",
    "        newNode = Node(val)\n",
    "        \n",
    "        # If no head exists\n",
    "        if not self.head:\n",
    "            self.head = newNode\n",
    "            self.tail = newNode\n",
    "        else:\n",
    "            # If head exists\n",
    "            newNode.next = self.head\n",
    "            self.head    = newNode \n",
    "        \n",
    "        self.length += 1\n",
    "        \n",
    "        return self\n",
    "    \n",
    "    # == GET == \n",
    "    def get(self, idx):\n",
    "        if idx < 0 or idx >= self.length:\n",
    "            return None\n",
    "        \n",
    "        current = self.head\n",
    "        \n",
    "        for i in range(idx):\n",
    "            current = current.next\n",
    "            \n",
    "        return current\n",
    "    \n",
    "    # == SET ==\n",
    "    def set(self, idx, val):\n",
    "        \n",
    "        node = self.get(idx)\n",
    "        \n",
    "        if node:\n",
    "            node.val = val\n",
    "            return True\n",
    "        \n",
    "        return False\n",
    "    \n",
    "    # == INSERT ==\n",
    "    def insert(self, idx, val):\n",
    "        if idx < 0 or idx > self.length:\n",
    "            return False\n",
    "        \n",
    "        if idx == 0:\n",
    "            self.unshift(val)\n",
    "            return True\n",
    "        elif idx == self.length:\n",
    "            self.push(val)\n",
    "            return True\n",
    "        else:\n",
    "            newNode = Node(val)\n",
    "            \n",
    "            preNode      = self.get(idx-1)\n",
    "            nextNode     = self.get(idx)\n",
    "            preNode.next = newNode\n",
    "            newNode.next = nextNode \n",
    "        \n",
    "        self.length += 1\n",
    "        \n",
    "        return True\n",
    "    \n",
    "    # == REMOVE == \n",
    "    def remove(self, idx):\n",
    "        if idx < 0 or idx > self.length:\n",
    "            return False\n",
    "        \n",
    "        if idx == 0:\n",
    "            self.shift()\n",
    "            return True\n",
    "        elif idx == self.length - 1:\n",
    "            self.pop()\n",
    "            return True\n",
    "        else:\n",
    "            preNode = self.get(idx - 1)\n",
    "            nextNode= preNode.next.next\n",
    "            \n",
    "            preNode.next = nextNode\n",
    "            \n",
    "        self.length -= 1\n",
    "            \n",
    "        return True\n",
    "    \n",
    "    # == REMOVE == \n",
    "    def remove(self, idx):\n",
    "        if idx < 0 or idx > self.length:\n",
    "            return False\n",
    "        \n",
    "        if idx == 0:\n",
    "            self.shift()\n",
    "            return True\n",
    "        elif idx == self.length - 1:\n",
    "            self.pop()\n",
    "            return True\n",
    "        else:\n",
    "            preNode = self.get(idx - 1)\n",
    "            nextNode= preNode.next.next\n",
    "            \n",
    "            preNode.next = nextNode\n",
    "            \n",
    "        self.length -= 1\n",
    "            \n",
    "        return True\n",
    "    \n",
    "    # == REVERSE == \n",
    "    def reverse(self):\n",
    "        temp      = self.head\n",
    "        self.head = self.tail\n",
    "        self.tail = temp\n",
    "        \n",
    "        # Initialize current\n",
    "        pre       = None\n",
    "        curr      = self.tail\n",
    "        \n",
    "        for i in range(self.length):\n",
    "            nex       = curr.next    # In the last iteration nex will equal to next of last element which is None so cannot be print\n",
    "            curr.next = pre          # Next time you learn Javascript, try print inside iteration as well \n",
    "            \n",
    "            pre       = curr\n",
    "            curr      = nex\n",
    "            \n",
    "        return self"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.SinglyLinkedList at 0x207e5a0b988>"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sll = SinglyLinkedList()\n",
    "sll.push('Hi')\n",
    "sll.push('Hello')\n",
    "sll.push('Yeaa')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.SinglyLinkedList at 0x207e5a0b988>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sll.reverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'head': <__main__.Node object at 0x00000207E5A0BA88>, 'tail': <__main__.Node object at 0x00000207E5A0BB48>, 'length': 3}\n",
      "{'val': 'Yeaa', 'next': <__main__.Node object at 0x00000207E5A0B7C8>}\n",
      "{'val': 'Hello', 'next': <__main__.Node object at 0x00000207E5A0BB48>}\n",
      "{'val': 'Hi', 'next': None}\n"
     ]
    }
   ],
   "source": [
    "print(vars(sll))\n",
    "print(vars(sll.get(0)))\n",
    "print(vars(sll.get(1)))\n",
    "print(vars(sll.get(2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Big O and Recap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Big O:\n",
    "1. Insertion - O(1)\n",
    "2. Removal   - O(1) or O(n)\n",
    "3. Searching - O(N)\n",
    "4. Access    - O(N)\n",
    "\n",
    "Recap:\n",
    "- Singly Linked Lists are excellent alternative to arrays, when insertaion and deletion at the beginning are frequently required\n",
    "- Arrays containt built in index, whereas Linked List do not\n",
    "- The idea of list data structure that consist of nodes is the foundation for other data structures like Stacks and Queues"
   ]
  }
 ],
 "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.7.9"
  },
  "toc-autonumbering": true,
  "toc-showcode": false,
  "toc-showmarkdowntxt": true
 },
 "nbformat": 4,
 "nbformat_minor": 4
}