data_structure_and_algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "MUKNnbp5yqnx"
   },
   "source": [
    "# Linked List ⛹\n",
    "\n",
    "---\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WfkqS3XRtjOn"
   },
   "source": [
    "**Insertion at head**\n",
    "###### Time complexity = O(1) As we are always inserting the node to the beginning without any need for traversal.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "b0zZzKHDyiQ3",
    "outputId": "c0819ff6-05c0-4fcf-fbbc-dddb97d62d1a"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 >> 8 >> 7 >> 6 >> 5 >> 4 >> 3 >> 2 >> 1 >> 0\n"
     ]
    }
   ],
   "source": [
    "\n",
    "class Node:\n",
    "  def __init__(self,data):\n",
    "    self.data = data\n",
    "    self.next = None\n",
    "\n",
    "\n",
    "class LinkedList:\n",
    "  def __init__(self):\n",
    "    self.head= None\n",
    "\n",
    "  def insert_at_head(self,data):\n",
    "    temp_node = Node(data)\n",
    "    temp_node.next = self.head\n",
    "    self.head = temp_node\n",
    "    return self.head\n",
    "  \n",
    "  def is_empty(self):\n",
    "    if self.head is None:\n",
    "      return True\n",
    "    return False\n",
    "\n",
    "  def print_list(self):\n",
    "    if self.is_empty():\n",
    "      return False\n",
    "\n",
    "    temp = self.head\n",
    "    while(temp.next is not None):\n",
    "      print(temp.data,end = \" >> \")\n",
    "      temp = temp.next\n",
    "    print(temp.data)\n",
    "\n",
    "\n",
    "lst = LinkedList()\n",
    "lst.print_list()\n",
    "\n",
    "\n",
    "\n",
    "for i in range(10):\n",
    "  lst.insert_at_head(i)\n",
    "\n",
    "lst.print_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "tm5Tz18qtvir"
   },
   "source": [
    "**Insertion at the end of linked list**\n",
    "\n",
    "Time complexity: O(n) as we have to traverse sequentially to the end of linked list.It can be transfored to O(1) by the overhead of having \n",
    "1 more pointer that always points to the last node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "heY7rQjnMY_b",
    "outputId": "f25f6c2e-0cdf-46c3-8731-fc42cc132942"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "0 >> 1 >> 2 >> 3 >> 4 >> 5 >> 6 >> 7 >> 8 >> 9\n"
     ]
    }
   ],
   "source": [
    "\n",
    "class Node:\n",
    "  def __init__(self,data):\n",
    "    self.data = data\n",
    "    self.next = None\n",
    "\n",
    "\n",
    "class LinkedList():\n",
    "  def __init__(self):\n",
    "    self.head = None\n",
    "\n",
    "  def is_empty(self):\n",
    "    if self.head == None:\n",
    "      return True\n",
    "    return False\n",
    "\n",
    "  def insert(self,data):\n",
    "    node =  Node(data)\n",
    "    temp = self.head\n",
    "\n",
    "    if temp == None:\n",
    "      self.head = node\n",
    "      return\n",
    "    \n",
    "    while(temp.next is not None):\n",
    "      temp = temp.next\n",
    "    temp.next = node\n",
    "\n",
    "  def print_list(self):\n",
    "    if self.is_empty():\n",
    "      print(None)\n",
    "      return None\n",
    "    temp = self.head\n",
    "    while(temp.next is not None):\n",
    "      print(temp.data, end=\" >> \")\n",
    "      temp = temp.next\n",
    "    print(temp.data)\n",
    "\n",
    "  \n",
    "lst = LinkedList()\n",
    "lst.print_list()\n",
    "\n",
    "\n",
    "\n",
    "for i in range(10):\n",
    "  lst.insert(i)\n",
    "\n",
    "lst.print_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Searching in a linked list**\n",
    "\n",
    "Time Complexity: O(n) Since, we need to traverse the linked list, In worst case,\n",
    "It might take visiting n nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 >> 8 >> 7 >> 6 >> 5 >> 4 >> 3 >> 2 >> 1 >> 0\n",
      "Data found at 6th node\n",
      "Could not find the data\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self,data):\n",
    "        self.data = data\n",
    "        self.next = None \n",
    "\n",
    "\n",
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def insert(self,data):\n",
    "        temp_node = Node(data)\n",
    "        temp_node.next = self.head\n",
    "        self.head = temp_node\n",
    "        return self.head\n",
    "\n",
    "    def search(self,data):\n",
    "        temp = self.head\n",
    "        count = 0\n",
    "        while(temp.next is not None and temp.data!=data):\n",
    "            # print(temp.data)\n",
    "            count += 1\n",
    "            temp = temp.next\n",
    "        \n",
    "        if temp.data==data:\n",
    "            print(f\"Data found at {count+1}th node\")\n",
    "            return count\n",
    "        print(\"Could not find the data\")\n",
    "        return None\n",
    "\n",
    "    def is_empty(self):\n",
    "        if self.head == None:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def print_list(self):\n",
    "        if self.is_empty():\n",
    "            print(None)\n",
    "            return None\n",
    "        temp = self.head\n",
    "        while(temp.next is not None):\n",
    "            print(temp.data, end=\" >> \")\n",
    "            temp = temp.next\n",
    "        print(temp.data)\n",
    "\n",
    "\n",
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.insert(i)\n",
    "\n",
    "lst.print_list()\n",
    "lst.search(4)\n",
    "lst.search(12)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Recursively searching for an element**\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 >> 8 >> 7 >> 6 >> 5 >> 4 >> 3 >> 2 >> 1 >> 0\n",
      "Node is Node(data=9), address is 0x7fe5785cf610 and address of next node is 0x7fe563f932e0)\n",
      "Node is Node(data=8), address is 0x7fe563f932e0 and address of next node is 0x7fe563f936a0)\n",
      "Node is Node(data=7), address is 0x7fe563f936a0 and address of next node is 0x7fe563fc3310)\n",
      "Node is Node(data=6), address is 0x7fe563fc3310 and address of next node is 0x7fe563fc3eb0)\n",
      "Node is Node(data=5), address is 0x7fe563fc3eb0 and address of next node is 0x7fe563fc38e0)\n",
      "Node is Node(data=4), address is 0x7fe563fc38e0 and address of next node is 0x7fe563fc3e50)\n",
      "True\n",
      "Node is Node(data=9), address is 0x7fe5785cf610 and address of next node is 0x7fe563f932e0)\n",
      "Node is Node(data=8), address is 0x7fe563f932e0 and address of next node is 0x7fe563f936a0)\n",
      "Node is Node(data=7), address is 0x7fe563f936a0 and address of next node is 0x7fe563fc3310)\n",
      "Node is Node(data=6), address is 0x7fe563fc3310 and address of next node is 0x7fe563fc3eb0)\n",
      "Node is Node(data=5), address is 0x7fe563fc3eb0 and address of next node is 0x7fe563fc38e0)\n",
      "Node is Node(data=4), address is 0x7fe563fc38e0 and address of next node is 0x7fe563fc3e50)\n",
      "Node is Node(data=3), address is 0x7fe563fc3e50 and address of next node is 0x7fe563fc37c0)\n",
      "Node is Node(data=2), address is 0x7fe563fc37c0 and address of next node is 0x7fe563fc3a60)\n",
      "Node is Node(data=1), address is 0x7fe563fc3a60 and address of next node is 0x7fe563d78730)\n",
      "Node is Node(data=0), address is 0x7fe563d78730 and address of next node is 0x55b7e67e73e0)\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "from dataclasses import dataclass\n",
    "\n",
    "@dataclass\n",
    "class Node:\n",
    "    data: int\n",
    "    next = None \n",
    "\n",
    "\n",
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def insert(self,data):\n",
    "        temp_node = Node(data)\n",
    "        temp_node.next = self.head\n",
    "        self.head = temp_node\n",
    "        return self.head\n",
    "\n",
    "    def search(self,node,data):\n",
    "        #print(node.data)\n",
    "        print(f\"Node is {node}, address is {hex(id(node))} and address of next node is {hex(id(node.next))})\")\n",
    "\n",
    "        if node.data==data:\n",
    "            return True\n",
    "        if node.next is None:\n",
    "            return False\n",
    "        return self.search(node.next,data)\n",
    "\n",
    "    def is_empty(self):\n",
    "        if self.head == None:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def print_list(self):\n",
    "        if self.is_empty():\n",
    "            print(None)\n",
    "            return None\n",
    "        temp = self.head\n",
    "        while(temp.next is not None):\n",
    "            print(temp.data, end=\" >> \")\n",
    "            temp = temp.next\n",
    "        print(temp.data)\n",
    "\n",
    "\n",
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.insert(i)\n",
    "\n",
    "lst.print_list()\n",
    "print(lst.search(lst.head, 4))\n",
    "print(lst.search(lst.head, 12))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "from diagrams import Cluster, Diagram\n",
    "from diagrams.aws.database import ElastiCache, RDS\n",
    "from diagrams.aws.network import ELB\n",
    "from diagrams.k8s.compute import Pod\n",
    "\n",
    "def visualize_linked_list(head):\n",
    "    with Diagram(\"Linked List\", show=True):\n",
    "        temp = head\n",
    "        head = ELB(f\"head, addr {hex(id(head))}\")\n",
    "        last_node = head\n",
    "        while(temp.next is not None):\n",
    "            with Cluster(\"Node\"):\n",
    "                db_secondary = RDS(f\"{temp.data}\")\n",
    "                db_secondary - [RDS(f\"{temp.next}\")]\n",
    "\n",
    "\n",
    "            temp = temp.next\n",
    "            last_node >> db_secondary\n",
    "            last_node = db_secondary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 >> 8 >> 7 >> 6 >> 5 >> 4 >> 3 >> 2 >> 1 >> 0\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "from dataclasses import dataclass\n",
    "\n",
    "@dataclass\n",
    "class Node:\n",
    "    data: int\n",
    "    next = None \n",
    "\n",
    "\n",
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def insert(self,data):\n",
    "        temp_node = Node(data)\n",
    "        temp_node.next = self.head\n",
    "        self.head = temp_node\n",
    "        return self.head\n",
    "\n",
    "    def search(self,node,data):\n",
    "        #print(node.data)\n",
    "        # print(f\"Node is {node}, address is {hex(id(node))} and address of next node is {hex(id(node.next))})\")\n",
    "\n",
    "        if node.data==data:\n",
    "            return True\n",
    "        if node.next is None:\n",
    "            return False\n",
    "        return self.search(node.next,data)\n",
    "\n",
    "    def is_empty(self):\n",
    "        if self.head == None:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def print_list(self):\n",
    "        if self.is_empty():\n",
    "            print(None)\n",
    "            return None\n",
    "        temp = self.head\n",
    "        while(temp.next is not None):\n",
    "            print(temp.data, end=\" >> \")\n",
    "            temp = temp.next\n",
    "        print(temp.data)\n",
    "\n",
    "\n",
    "lst = LinkedList()\n",
    "for i in range(10):\n",
    "    lst.insert(i)\n",
    "\n",
    "lst.print_list()\n",
    "print(lst.search(lst.head, 4))\n",
    "print(lst.search(lst.head, 12))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n",
      "(eog:7047): Gtk-WARNING **: 23:01:17.307: Could not load a pixbuf from icon theme.\n",
      "This may indicate that pixbuf loaders or the mime database could not be found.\n"
     ]
    }
   ],
   "source": [
    "visualize_linked_list(lst.head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "4JWr5ZyRyoCM"
   },
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyMPNp0BSEJJRj54pcpPilAh",
   "collapsed_sections": [],
   "include_colab_link": true,
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3.10.4 ('env': venv)",
   "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.10.4"
  },
  "vscode": {
   "interpreter": {
    "hash": "1551a4d4462b2ef46c7ecbbc4193c559594ee0848c5060e21a55adfdfe58dc61"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}