Linked Lists.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "61f68876",
   "metadata": {},
   "source": [
    "<center><h1>Linked List</h1><center><br>\n",
    " \n",
    "    \n",
    "A linked list is a sequence of nodes where each node stores its own data and a link to the next node.\n",
    "One node links to another forming what can be thought of as a linked chain.<br>\n",
    "\n",
    "The first node is called the **head**, and it's used as the starting point for any iteration through the list. The last node must have its link pointing to **None** to determine the end of the list.\n",
    "\n",
    "Unlike stacks and queues, you can insert and remove nodes in any position of the linked list (similar to a standard list). <br>\n",
    "\n",
    "**Applications**: <br>\n",
    "Linked lists are useful when your data is linked. For example when you need undo/redo functionality, the nodes can represent the state with links to the previous and next states. Another example would be a playlist of music, where each clip is linked with the next one.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "528a2896",
   "metadata": {},
   "source": [
    "<img src=\"images/linked-list.jpeg\" />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "923210eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    \n",
    "    def __init__(self, data=None, next=None):\n",
    "        self.data = data\n",
    "        self.next = next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "f8343afc",
   "metadata": {},
   "outputs": [],
   "source": [
    "class DoubleNode(Node):\n",
    "    def __init__(self,data=None,next=None,prev=None):\n",
    "        super().__init__(data,next)\n",
    "        self.prev = prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "fdf7bf1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "node1 = DoubleNode(1)\n",
    "node2 = DoubleNode(2,node1)\n",
    "node3 = DoubleNode(3, node1,node2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "357618b5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "node3.prev.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "id": "8d446ae5",
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedList:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "    \n",
    "    def add_at_front(self, data):\n",
    "        ''' insert data at the head of the linked list.'''\n",
    "        \n",
    "        self.head = Node(data, self.head)\n",
    "        \n",
    "    def add_at_end(self, data):\n",
    "        ''' insert data at the last item of the linked list.'''\n",
    "        \n",
    "        if not self.head:\n",
    "            self.head = Node(data, self.head)\n",
    "            return\n",
    "            \n",
    "        c = self.head\n",
    "        while c.next != None:\n",
    "            c = c.next\n",
    "        c.next = Node(data, None)\n",
    "        \n",
    "    def add_at(self, index, data):\n",
    "        '''add data at the given index.'''\n",
    "        \n",
    "        if index > self.length() or index < 0:\n",
    "            raise Exception(\"Invalid Index !\")\n",
    "        \n",
    "        i,curr = 0, self.head\n",
    "        while curr.next:\n",
    "            if i == index-1:\n",
    "                node = Node(data, curr.next)\n",
    "                curr.next = node\n",
    "                break\n",
    "            \n",
    "            curr = curr.next\n",
    "            i += 1\n",
    "        \n",
    "    def remove_at(self, index):\n",
    "        '''remove data from the given index.'''\n",
    "        \n",
    "        if index > self.length() or index < 0:\n",
    "            raise Exception(\"Invalid Index !\")\n",
    "        \n",
    "        if index == 0:\n",
    "            self.head = self.head.next\n",
    "            return\n",
    "            \n",
    "        i,curr = 0, self.head\n",
    "        while curr.next:\n",
    "            if i == index-1 :\n",
    "                curr.next = curr.next.next\n",
    "                break\n",
    "                \n",
    "            curr = curr.next\n",
    "            i += 1\n",
    "        \n",
    "    def print(self):\n",
    "        '''print the linked list items.'''\n",
    "        \n",
    "        if self.head is None:\n",
    "            print(\"Linked List is empty ..\")\n",
    "            return\n",
    "        \n",
    "        n = self.head\n",
    "        while n != None:\n",
    "            print(n.data, end=\" --> \")\n",
    "            n = n.next\n",
    "        print('(',None,')')\n",
    "        \n",
    "    def length(self):\n",
    "        '''get the lenth ofthe linked list'''\n",
    "        \n",
    "        c = 0\n",
    "        n = self.head\n",
    "        while n:\n",
    "            c +=1\n",
    "            n = n.next\n",
    "            \n",
    "        return c\n",
    "    \n",
    "    def insert_after_value(self, data_after, data_inert):\n",
    "        '''insert data after the given value node.'''\n",
    "        \n",
    "        if self.head is None:\n",
    "            print(\"Linked List is empty ..\")\n",
    "            return\n",
    "        \n",
    "        curr = self.head\n",
    "        while curr:\n",
    "            if curr.data == data_after:\n",
    "                node = Node(data_inert, curr.next)\n",
    "                curr.next = node\n",
    "                return\n",
    "            \n",
    "            curr = curr.next\n",
    "            \n",
    "        print(\"Invalid data .. \")\n",
    "        \n",
    "    def remove_by_value(self, value):\n",
    "        '''remove first node that contain given data'''\n",
    "        \n",
    "        if self.head is None:\n",
    "            print(\"Linked List is empty ..\")\n",
    "            return\n",
    "        \n",
    "        if self.head.data == value:\n",
    "            self.head = self.head.next\n",
    "            return\n",
    "            \n",
    "        curr = self.head\n",
    "        while curr.next:\n",
    "            if curr.next.data == value:\n",
    "                curr.next = curr.next.next\n",
    "                return\n",
    "            curr = curr.next\n",
    "            \n",
    "        print(\"Invalid data .. \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "3bc575f1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "data 3 --> data 2 --> data 1 --> ( None )\n"
     ]
    }
   ],
   "source": [
    "my_list = LinkedList()\n",
    "my_list.add_at_front('data 1')\n",
    "my_list.add_at_front('data 2')\n",
    "my_list.add_at_front('data 3')\n",
    "my_list.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "9e5b976a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length: 4\n",
      "data 3 --> data 2 --> data 1 --> data 0 --> ( None )\n"
     ]
    }
   ],
   "source": [
    "my_list.add_at_end('data 0')\n",
    "print('length:',my_list.length())\n",
    "my_list.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "e32eba20",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length: 3\n",
      "data 3 --> data 2 --> data 0 --> ( None )\n"
     ]
    }
   ],
   "source": [
    "my_list.remove_at(2)\n",
    "print('length:',my_list.length())\n",
    "my_list.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "27cf2496",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "data 3 --> data 2 --> data 1 --> data 0 --> ( None )\n"
     ]
    }
   ],
   "source": [
    "my_list.add_at(2,'data 1')\n",
    "my_list.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "53f8f0fc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "data 3 --> data inserted --> data 2 --> data 1 --> data 0 --> ( None )\n"
     ]
    }
   ],
   "source": [
    "my_list.insert_after_value('data 3', 'data inserted')\n",
    "my_list.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "ca34c117",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "data 3 --> data 2 --> data 1 --> data 0 --> ( None )\n"
     ]
    }
   ],
   "source": [
    "my_list.remove_by_value('data inserted')\n",
    "my_list.print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8bd164d5",
   "metadata": {},
   "source": [
    "# Exercice"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31b0e09b",
   "metadata": {},
   "source": [
    "In LinkedList class following two methods,\n",
    "```python\n",
    "        def insert_after_value(self, data_after, data_to_insert):\n",
    "            # Search for first occurance of data_after value in linked list\n",
    "            # Now insert data_to_insert after data_after node\n",
    "\n",
    "        def remove_by_value(self, data):\n",
    "            # Remove first node that contains data\n",
    "```\n",
    "Now make following calls:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "id": "48b47da4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "banana --> mango --> grapes --> orange --> ( None )\n",
      "banana --> mango --> apple --> grapes --> orange --> ( None )\n",
      "banana --> mango --> apple --> grapes --> ( None )\n",
      "Invalid data .. \n",
      "banana --> mango --> apple --> grapes --> ( None )\n",
      "Linked List is empty ..\n"
     ]
    }
   ],
   "source": [
    "ll = LinkedList()\n",
    "for val in [\"banana\",\"mango\",\"grapes\",\"orange\"]:\n",
    "    ll.add_at_end(val)\n",
    "ll.print()\n",
    "ll.insert_after_value(\"mango\",\"apple\") # insert apple after mango\n",
    "ll.print()\n",
    "ll.remove_by_value(\"orange\") # remove orange from linked list\n",
    "ll.print()\n",
    "ll.remove_by_value(\"figs\")\n",
    "ll.print()\n",
    "ll.remove_by_value(\"banana\")\n",
    "ll.remove_by_value(\"mango\")\n",
    "ll.remove_by_value(\"apple\")\n",
    "ll.remove_by_value(\"grapes\")\n",
    "ll.print()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "951f83e3",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}