LinkedList.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPruFItx4ohRU5TPVx4UcaN",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/pranjal-tiwarigithub/CampusX/blob/main/LinkedList.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "9iCmsZ0r7u_L"
      },
      "outputs": [],
      "source": [
        "class Node:\n",
        "\n",
        "  def __init__(self,value):\n",
        "    self.data = value\n",
        "    self.next = None\n",
        "  "
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "a = Node(1)\n",
        "b = Node(2)\n",
        "c = Node(3)"
      ],
      "metadata": {
        "id": "CTnowvly8GPc"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "print(a.data)\n",
        "print(c.data)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rqgt7c5v8If3",
        "outputId": "11a4a8b1-99d5-4360-a815-03363b56d6fd"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1\n",
            "3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "b"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WxVk-M_y814a",
        "outputId": "65bc0383-02f4-4e32-8b29-135f90266901"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<__main__.Node at 0x7f717d2e6c80>"
            ]
          },
          "metadata": {},
          "execution_count": 29
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "a.next = b\n",
        "b.next =  c"
      ],
      "metadata": {
        "id": "sKjRPit88KSy"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "id(b)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "mkmkWA5p87Zq",
        "outputId": "910066ee-cdad-44a5-bc32-f8a64b788a92"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "140125408226432"
            ]
          },
          "metadata": {},
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "print(a.next)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "KcKjAUOT8jnz",
        "outputId": "cd550890-a669-4e28-945d-83425863992d"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "<__main__.Node object at 0x7f717d2e6c80>\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "int(0x7f717d2e6c80)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "KXm_M-jP856l",
        "outputId": "e3bbb089-d664-4c48-c237-3aba3b2a2588"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "140125408226432"
            ]
          },
          "metadata": {},
          "execution_count": 30
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "e5RsyjWx9CBJ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "print(c.next)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "tMJyejEZ9C5K",
        "outputId": "b1f0c846-6592-481e-d933-4d0612f6713b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "None\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "LL "
      ],
      "metadata": {
        "id": "-9fcH8439uEh"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Node:\n",
        "\n",
        "  def __init__(self,value):\n",
        "    self.data = value\n",
        "    self.next = None\n",
        "  "
      ],
      "metadata": {
        "id": "B9xUHM4y9P8T"
      },
      "execution_count": 17,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "class LinkedList:\n",
        "  def __init__(self):\n",
        "\n",
        "    # create empty linked list -> 0 nodes -> Head is None \n",
        "    # head == None means empty linked list \n",
        "  \n",
        "    self.head = None\n",
        "    self.n = 0 ## no of nodes\n",
        "  \n",
        "  def __len__(self):\n",
        "    return self.n \n",
        "\n",
        "  def insert_head(self,value):\n",
        "\n",
        "    ## new node \n",
        "    new_node = Node(value)\n",
        "\n",
        "    ## create connection\n",
        "    new_node.next = self.head\n",
        "\n",
        "    ## reassign head\n",
        "\n",
        "    self.head = new_node\n",
        "\n",
        "    self.n = self.n + 1\n",
        "\n",
        "  def traverse(self):\n",
        "    curr = self.head\n",
        "\n",
        "    while (curr != None):\n",
        "      print(curr.data)\n",
        "      curr = curr.next \n",
        "\n",
        "  def __str__(self):\n",
        "\n",
        "    curr = self.head\n",
        "    result = ''\n",
        "    while (curr != None):\n",
        "      result = result + str(curr.data) + \"->\"\n",
        "      curr = curr.next\n",
        "    \n",
        "    return result[:-2]\n",
        "\n",
        "  def insert_tail(self , temp):   # append func\n",
        "\n",
        "    next_node = Node(temp)\n",
        "\n",
        "    if self.head == None:\n",
        "      self.head = next_node\n",
        "      self.n = self.n + 1\n",
        "      return   ## so that coming node is not executed \n",
        "\n",
        "    \n",
        "    curr = self.head\n",
        "\n",
        "    while curr.next != None:\n",
        "      curr = curr.next \n",
        "    \n",
        "    # we are at tail\n",
        "    curr.next = next_node # new_node.next = None by default\n",
        "    self.n = self.n + 1\n",
        "\n",
        "  def insert_middle(self , target , item):\n",
        "\n",
        "    new_node = Node(item)\n",
        "\n",
        "    curr =self.head\n",
        "    while curr != None:\n",
        "      if curr.data == target:\n",
        "        break\n",
        "      curr = curr.next\n",
        "    \n",
        "    # case 1 target found \n",
        "\n",
        "    if curr != None:\n",
        "\n",
        "      new_node.next = curr.next\n",
        "      curr.next = new_node\n",
        "\n",
        "      self.n = self.n + 1\n",
        "\n",
        "    else:\n",
        "\n",
        "      return \"item not found\"\n",
        "\n",
        "\n",
        "    # case curr = None , loop over \n",
        "\n",
        "  \n",
        "  def clear(self):\n",
        "    self.head = None\n",
        "    self.n = 0\n",
        "\n",
        "  def delete_head(self):\n",
        "    if self.head == None:\n",
        "      return \"empty Linkedlist\"\n",
        "\n",
        "    self.head = self.head.next \n",
        "    self.n = self.n - 1\n",
        "\n",
        "  def delete_tail(self):  ## pop \n",
        "\n",
        "    # will not work if LL has only 1 item\n",
        "\n",
        "    \n",
        "    curr = self.head\n",
        "\n",
        "    if self.head == None:\n",
        "      return \"empty Linked list\"\n",
        "\n",
        "    if curr.next == None:\n",
        "      ## only I node that is head now \n",
        "      return self.delete_head()\n",
        "\n",
        "    while curr.next.next != None: # stop at second last node \n",
        "      curr = curr.next \n",
        "\n",
        "    curr.next = None\n",
        "    self.n = self.n - 1\n",
        "    \n",
        "\n",
        "  def remove(self, val):\n",
        "\n",
        "    #print(self.head)\n",
        "\n",
        "    # empty list \n",
        "\n",
        "    if self.head == None:\n",
        "      return 'empty Linklist'\n",
        "\n",
        "    if self.head.data == val:  ## corner case \n",
        "      ## you want to remove gead node \n",
        "      return self.delete_head()\n",
        "\n",
        "    curr = self.head\n",
        "\n",
        "    while curr.next != None:   \n",
        "\n",
        "      if curr.next.data == val:\n",
        "        break\n",
        "      \n",
        "      curr = curr.next \n",
        "\n",
        "    ## 2 cases \n",
        "\n",
        "    # val found or not found , not found case we are at tail \n",
        "    if curr.next == None:\n",
        "      #utem not found\n",
        "      return \"item not found\"\n",
        "    else:\n",
        "      curr.next = curr.next.next \n",
        "      self.n = self.n - 1\n",
        "  \n",
        "  def search(self,item):\n",
        " \n",
        "    curr =self.head \n",
        "    pos = 0 \n",
        "\n",
        "    while curr != None:\n",
        "      #print(curr.data)\n",
        "      if curr.data == item:\n",
        "        return pos\n",
        "      \n",
        "      curr = curr.next\n",
        "\n",
        "      pos = pos + 1\n",
        "\n",
        "    return 'item Not Found'\n",
        "  \n",
        "  def  __getitem__ (self,index):  ## index position get value \n",
        "\n",
        "    curr = self.head \n",
        "\n",
        "    pos = 0\n",
        "\n",
        "    while curr != None:\n",
        "      if pos == index:\n",
        "        return curr.data\n",
        "\n",
        "      curr = curr.next\n",
        "      pos = pos + 1 \n",
        "\n",
        "    return 'invalid index'                      \n",
        "    \n"
      ],
      "metadata": {
        "id": "msW8jV2Z9wgB"
      },
      "execution_count": 179,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "L = LinkedList()"
      ],
      "metadata": {
        "id": "9qDxvXO6-Pcj"
      },
      "execution_count": 180,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "print(L.head)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "z7-J83y--SVL",
        "outputId": "e9931710-ebe7-457e-b402-74d25e41f5fd"
      },
      "execution_count": 181,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "None\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "len(L)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Zt0K_Ry7-VsN",
        "outputId": "6ec10f85-73ec-42b8-d6db-573c79afe4a4"
      },
      "execution_count": 182,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0"
            ]
          },
          "metadata": {},
          "execution_count": 182
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "L.insert_head(1)\n",
        "L.insert_head(2)\n",
        "L.insert_head(3)\n",
        "L.insert_head(4)\n",
        "len(L)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "R9l4qzr_RJoS",
        "outputId": "1874e9f3-3603-4c07-99f6-a022cefd1e2b"
      },
      "execution_count": 183,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4"
            ]
          },
          "metadata": {},
          "execution_count": 183
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "L.traverse()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aXUFadlmRckl",
        "outputId": "b95058d3-bfaf-4e50-833e-0da038e9d191"
      },
      "execution_count": 90,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "4\n",
            "3\n",
            "2\n",
            "1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "print(L)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5XmDo9ifTKMY",
        "outputId": "4495a72a-cd53-452d-a682-dfaa96780620"
      },
      "execution_count": 162,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "4->3->2->1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "L.insert_tail(5)\n",
        "print(L)\n",
        "len(L)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Xv2VWfWcVhTr",
        "outputId": "d8a13419-e4d0-464e-976e-d526f5547fb6"
      },
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "4->3->2->1->5\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5"
            ]
          },
          "metadata": {},
          "execution_count": 18
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "L.insert_middle(20,10)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 36
        },
        "id": "q3q7i5LMVmXh",
        "outputId": "0e0f1fd6-af96-4502-a0f6-0039ac2d91c5"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'item not found'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 147
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "L.insert_middle(2,10)\n",
        "print(L)\n",
        "len(L)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rZlWxFhSdqBb",
        "outputId": "e307b656-c276-42ae-c111-127967a99460"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "4->3->2->10->1->5\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5"
            ]
          },
          "metadata": {},
          "execution_count": 155
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "L.insert_middle(5,10)\n",
        "print(L)\n",
        "len(L)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fhGSI-F4d3uM",
        "outputId": "fb9a135f-2f7f-4c17-d994-7b47cb0429ac"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "4->3->2->10->1->5->10\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5"
            ]
          },
          "metadata": {},
          "execution_count": 156
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "L.clear()\n",
        "len(L)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "S9QIwCusLRId",
        "outputId": "4100ce47-6c7d-4e2d-8a93-4629cadb865d"
      },
      "execution_count": 25,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0"
            ]
          },
          "metadata": {},
          "execution_count": 25
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "L.delete_head()\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 36
        },
        "id": "ifx8nKtrL0zi",
        "outputId": "09a979b4-3216-4067-d397-4335e91ad0ff"
      },
      "execution_count": 52,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'empty Linkedlist'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 52
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "print(L)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rKkrEcdhMgKd",
        "outputId": "cb5aaba6-9825-4d85-928f-42eb1eda2183"
      },
      "execution_count": 164,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "4->3->2->1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "print(L.delete_tail())\n",
        "print(L)\n",
        "print(len(L))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_xjTxIWkNVCw",
        "outputId": "0ead9252-ebb0-4e3f-95b4-67b5519fa2e0"
      },
      "execution_count": 84,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "empty Linked list\n",
            "\n",
            "0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "L.remove(1)\n",
        "print(L)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "hbynHGDMxJBS",
        "outputId": "877c7e22-36ce-4e4d-98d5-7fb3f1e1d33e"
      },
      "execution_count": 146,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "### 1_>2->3->4 ,  3 at index 2 "
      ],
      "metadata": {
        "id": "L1lPDwZqyMMT"
      },
      "execution_count": 125,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "L.search(10)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 36
        },
        "id": "PQAuH97_yNcs",
        "outputId": "2306031e-dc79-400e-8070-aaeb50565681"
      },
      "execution_count": 178,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'item Not Found'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 178
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "L[3]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "X3ZVh8wsak79",
        "outputId": "4e4221b4-23fd-44a5-f622-eda6e243f87b"
      },
      "execution_count": 184,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1"
            ]
          },
          "metadata": {},
          "execution_count": 184
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "L[10]"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 36
        },
        "id": "18Cq6_iqarQR",
        "outputId": "cb1d523d-f5b0-4cec-c063-47d5dc772041"
      },
      "execution_count": 185,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'invalid index'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 185
        }
      ]
    }
  ]
}