01-LinkedList.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linked Lists\n",
    "\n",
    "## Contents:\n",
    "\n",
    "1. [Introduction](#introduction)\n",
    "2. [Types of Linked Lists](#types-of-linked-lists)\n",
    "    - [**Singly Linked List**: Each node contains only one reference to the next node.](#singly-linked-list)\n",
    "        - [Implementation](#implementation)\n",
    "        - [Operations](#operations)\n",
    "        - [Applications](#applications)\n",
    "        - [Problems](#problems)\n",
    "    - [**Doubly Linked List**: Each node contains two references, one to the next node and another to the previous node.](#doubly-linked-list)\n",
    "        - [Implementation](#implementation-1)\n",
    "        - [Operations](#operations-1)\n",
    "        - [Applications](#applications-1)\n",
    "        - [Problems](#problems-1)\n",
    "    - [**Circular Linked List**: Last node of the list contains a reference to the first node of the list.](#circular-linked-list)\n",
    "        - [Implementation](#implementation-2)\n",
    "        - [Operations](#operations-2)\n",
    "        - [Applications](#applications-2)\n",
    "        - [Problems](#problems-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "A linked list is a linear data structure where each element is a separate object. Each element (we will call it a node) of a list is comprising of two items - the data and a reference to the next/previous node. The entry point into a linked list is called the head of the list. It should be noted that the head is not a separate node, but the reference to the first node.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Singly Linked List\n",
    "\n",
    "A singly linked list is a collection of nodes where each node has two parts: data and a reference to the next node. The first node is called the head and the last node is called the tail. The last node has a reference to `None`. If the list is empty then the head is a `None` reference. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedList:\n",
    "    def __init__(self, data) -> None:\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return f\"LL({self.data})\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Operations\n",
    "\n",
    "1. **Traversal**:\n",
    "    - Traverse the list, print all the elements.\n",
    "2. **Insertion**:\n",
    "    - Insert at the beginning of the list.\n",
    "    - Insert at the end of the list.\n",
    "    - Insert at the given position.\n",
    "3. **Deletion**:\n",
    "    - Delete the first node.\n",
    "    - Delete the last node.\n",
    "    - Delete the node at the given position.\n",
    "4. **Search**:\n",
    "    - Search for a given element in the list.\n",
    "5. **Length**:\n",
    "    - Find the length of the list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1. Traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Utility function to print linked list\n",
    "%matplotlib inline\n",
    "from graphviz import Digraph\n",
    "\n",
    "# print linked list inline in notebook using graphviz\n",
    "def print_linked_list(head):\n",
    "    dot = Digraph(format='svg', graph_attr={'rankdir':'LR'})\n",
    "    node = head\n",
    "    i = 0\n",
    "    while node:\n",
    "        dot.node(name=str(i), label= \"{data %.2f | next %s}\" % (node.data, node.next), shape='record')\n",
    "        if node.next:\n",
    "            dot.edge(f'{i}', f'{i+1}')\n",
    "        i += 1\n",
    "        node = node.next\n",
    "\n",
    "    display(dot)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 3 4 "
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"812pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 812.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 808,-41 808,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 174,-36.5 174,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"42\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"84,-0.5 84,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"129\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"210,-0.5 210,-36.5 384,-36.5 384,-0.5 210,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"252\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"294,-0.5 294,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"339\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(3)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.1,-18.5C182.62,-18.5 191.3,-18.5 199.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"199.96,-22 209.96,-18.5 199.96,-15 199.96,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"420,-0.5 420,-36.5 594,-36.5 594,-0.5 420,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"462\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"504,-0.5 504,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"549\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(4)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M384.1,-18.5C392.62,-18.5 401.3,-18.5 409.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"409.96,-22 419.96,-18.5 409.96,-15 409.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"630,-0.5 630,-36.5 804,-36.5 804,-0.5 630,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"672\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"714,-0.5 714,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"759\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M594.1,-18.5C602.62,-18.5 611.3,-18.5 619.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"619.96,-22 629.96,-18.5 619.96,-15 619.96,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0324591ed0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = LinkedList(1)\n",
    "cur = head\n",
    "for i in range(2, 5):\n",
    "    cur.next = LinkedList(i)\n",
    "    cur = cur.next\n",
    "    print(cur.data, end=\" \")\n",
    "print_linked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Insertion\n",
    "\n",
    "#### 2.1 Insertion at the beginning"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_at_start(head, data) -> LinkedList:\n",
    "    new_node = LinkedList(data)\n",
    "    new_node.next = head\n",
    "    head = new_node\n",
    "    return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1022pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1022.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1018,-41 1018,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 174,-36.5 174,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"42\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 0.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"84,-0.5 84,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"129\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(1)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"210,-0.5 210,-36.5 384,-36.5 384,-0.5 210,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"252\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"294,-0.5 294,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"339\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(2)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.1,-18.5C182.62,-18.5 191.3,-18.5 199.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"199.96,-22 209.96,-18.5 199.96,-15 199.96,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"420,-0.5 420,-36.5 594,-36.5 594,-0.5 420,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"462\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"504,-0.5 504,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"549\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(3)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M384.1,-18.5C392.62,-18.5 401.3,-18.5 409.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"409.96,-22 419.96,-18.5 409.96,-15 409.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"630,-0.5 630,-36.5 804,-36.5 804,-0.5 630,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"672\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"714,-0.5 714,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"759\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(4)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M594.1,-18.5C602.62,-18.5 611.3,-18.5 619.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"619.96,-22 629.96,-18.5 619.96,-15 619.96,-22\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"840,-0.5 840,-36.5 1014,-36.5 1014,-0.5 840,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"882\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"924,-0.5 924,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"969\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M804.1,-18.5C812.62,-18.5 821.3,-18.5 829.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"829.96,-22 839.96,-18.5 829.96,-15 829.96,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a03244d2290>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = insert_at_start(head, 0)\n",
    "print_linked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.2 Insertion at the end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_at_end(head, data) -> LinkedList:\n",
    "    new_node = LinkedList(data)\n",
    "    if head is None:\n",
    "        return new_node\n",
    "    cur = head\n",
    "    while cur.next:\n",
    "        cur = cur.next\n",
    "    cur.next = new_node\n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1232pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1232.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1228,-41 1228,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 174,-36.5 174,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"42\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 0.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"84,-0.5 84,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"129\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(1)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"210,-0.5 210,-36.5 384,-36.5 384,-0.5 210,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"252\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"294,-0.5 294,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"339\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(2)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.1,-18.5C182.62,-18.5 191.3,-18.5 199.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"199.96,-22 209.96,-18.5 199.96,-15 199.96,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"420,-0.5 420,-36.5 594,-36.5 594,-0.5 420,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"462\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"504,-0.5 504,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"549\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(3)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M384.1,-18.5C392.62,-18.5 401.3,-18.5 409.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"409.96,-22 419.96,-18.5 409.96,-15 409.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"630,-0.5 630,-36.5 804,-36.5 804,-0.5 630,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"672\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"714,-0.5 714,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"759\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(4)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M594.1,-18.5C602.62,-18.5 611.3,-18.5 619.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"619.96,-22 629.96,-18.5 619.96,-15 619.96,-22\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"840,-0.5 840,-36.5 1014,-36.5 1014,-0.5 840,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"882\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"924,-0.5 924,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"969\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(6)</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M804.1,-18.5C812.62,-18.5 821.3,-18.5 829.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"829.96,-22 839.96,-18.5 829.96,-15 829.96,-22\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1050,-0.5 1050,-36.5 1224,-36.5 1224,-0.5 1050,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1092\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 6.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1134,-0.5 1134,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1179\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1014.1,-18.5C1022.62,-18.5 1031.3,-18.5 1039.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1039.96,-22 1049.96,-18.5 1039.96,-15 1039.96,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a03244bfca0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = insert_at_end(head, 6)\n",
    "print_linked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.3 Insertion at the given position"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_at_idx(head, idx, data) -> LinkedList:\n",
    "    if idx < 1:\n",
    "        print(f\"Invalid index {idx}.\")\n",
    "    cur = head\n",
    "    pos = 1\n",
    "    while cur.next.next:\n",
    "        # print(cur)\n",
    "        cur = cur.next\n",
    "        pos += 1\n",
    "        if pos == idx -1:\n",
    "            break\n",
    "    print(pos, cur, idx)\n",
    "    if pos < idx - 1:\n",
    "        print(f\"Index {idx} out of range for list size {pos}.\")\n",
    "        return head\n",
    "    \n",
    "    new_node = LinkedList(data)\n",
    "    new_node.next = cur.next\n",
    "    cur.next = new_node\n",
    "\n",
    "    \n",
    "    return head\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 LL(4) 6\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1442pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1442.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1438,-41 1438,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 174,-36.5 174,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"42\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 0.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"84,-0.5 84,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"129\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(1)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"210,-0.5 210,-36.5 384,-36.5 384,-0.5 210,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"252\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"294,-0.5 294,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"339\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(2)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.1,-18.5C182.62,-18.5 191.3,-18.5 199.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"199.96,-22 209.96,-18.5 199.96,-15 199.96,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"420,-0.5 420,-36.5 594,-36.5 594,-0.5 420,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"462\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"504,-0.5 504,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"549\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(3)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M384.1,-18.5C392.62,-18.5 401.3,-18.5 409.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"409.96,-22 419.96,-18.5 409.96,-15 409.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"630,-0.5 630,-36.5 804,-36.5 804,-0.5 630,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"672\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"714,-0.5 714,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"759\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(4)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M594.1,-18.5C602.62,-18.5 611.3,-18.5 619.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"619.96,-22 629.96,-18.5 619.96,-15 619.96,-22\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"840,-0.5 840,-36.5 1014,-36.5 1014,-0.5 840,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"882\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"924,-0.5 924,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"969\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(5)</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M804.1,-18.5C812.62,-18.5 821.3,-18.5 829.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"829.96,-22 839.96,-18.5 829.96,-15 829.96,-22\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1050,-0.5 1050,-36.5 1224,-36.5 1224,-0.5 1050,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1092\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 5.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1134,-0.5 1134,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1179\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(6)</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1014.1,-18.5C1022.62,-18.5 1031.3,-18.5 1039.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1039.96,-22 1049.96,-18.5 1039.96,-15 1039.96,-22\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1260,-0.5 1260,-36.5 1434,-36.5 1434,-0.5 1260,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1302\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 6.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1344,-0.5 1344,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1389\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1224.1,-18.5C1232.62,-18.5 1241.3,-18.5 1249.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1249.96,-22 1259.96,-18.5 1249.96,-15 1249.96,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a03244bc280>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = insert_at_idx(head, 6, 5)\n",
    "print_linked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Deletion\n",
    "\n",
    "#### 3.1 Delete the first node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delete_first_node(head):\n",
    "    new_head = head.next\n",
    "    del head\n",
    "    return new_head\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1232pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1232.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1228,-41 1228,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 174,-36.5 174,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"42\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"84,-0.5 84,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"129\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"210,-0.5 210,-36.5 384,-36.5 384,-0.5 210,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"252\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"294,-0.5 294,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"339\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(3)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.1,-18.5C182.62,-18.5 191.3,-18.5 199.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"199.96,-22 209.96,-18.5 199.96,-15 199.96,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"420,-0.5 420,-36.5 594,-36.5 594,-0.5 420,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"462\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"504,-0.5 504,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"549\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(4)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M384.1,-18.5C392.62,-18.5 401.3,-18.5 409.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"409.96,-22 419.96,-18.5 409.96,-15 409.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"630,-0.5 630,-36.5 804,-36.5 804,-0.5 630,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"672\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"714,-0.5 714,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"759\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(5)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M594.1,-18.5C602.62,-18.5 611.3,-18.5 619.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"619.96,-22 629.96,-18.5 619.96,-15 619.96,-22\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"840,-0.5 840,-36.5 1014,-36.5 1014,-0.5 840,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"882\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 5.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"924,-0.5 924,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"969\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(6)</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M804.1,-18.5C812.62,-18.5 821.3,-18.5 829.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"829.96,-22 839.96,-18.5 829.96,-15 829.96,-22\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1050,-0.5 1050,-36.5 1224,-36.5 1224,-0.5 1050,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1092\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 6.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1134,-0.5 1134,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1179\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1014.1,-18.5C1022.62,-18.5 1031.3,-18.5 1039.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1039.96,-22 1049.96,-18.5 1039.96,-15 1039.96,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a03245bfdf0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = delete_first_node(head)\n",
    "print_linked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.2 Delete the last node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delete_last_node(head):\n",
    "    cur = head\n",
    "    while cur.next.next:\n",
    "        cur = cur.next\n",
    "    del cur.next\n",
    "    cur.next = None\n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1022pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1022.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1018,-41 1018,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 174,-36.5 174,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"42\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"84,-0.5 84,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"129\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"210,-0.5 210,-36.5 384,-36.5 384,-0.5 210,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"252\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"294,-0.5 294,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"339\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(3)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.1,-18.5C182.62,-18.5 191.3,-18.5 199.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"199.96,-22 209.96,-18.5 199.96,-15 199.96,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"420,-0.5 420,-36.5 594,-36.5 594,-0.5 420,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"462\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"504,-0.5 504,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"549\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(4)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M384.1,-18.5C392.62,-18.5 401.3,-18.5 409.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"409.96,-22 419.96,-18.5 409.96,-15 409.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"630,-0.5 630,-36.5 804,-36.5 804,-0.5 630,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"672\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"714,-0.5 714,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"759\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(5)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M594.1,-18.5C602.62,-18.5 611.3,-18.5 619.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"619.96,-22 629.96,-18.5 619.96,-15 619.96,-22\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"840,-0.5 840,-36.5 1014,-36.5 1014,-0.5 840,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"882\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 5.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"924,-0.5 924,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"969\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M804.1,-18.5C812.62,-18.5 821.3,-18.5 829.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"829.96,-22 839.96,-18.5 829.96,-15 829.96,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a03244790f0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = delete_last_node(head)\n",
    "print_linked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.3 Delete the node at the given position"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delete_idx_node(head, idx):\n",
    "    if idx < 1:\n",
    "        print(f\"Invalid index {idx}.\")\n",
    "    if head.next == None:\n",
    "        del head\n",
    "        return None\n",
    "    if idx == 1:\n",
    "        return delete_first_node(head)\n",
    "    cur = head\n",
    "    pos = 1\n",
    "    while cur.next.next:\n",
    "        if pos >= idx -1:\n",
    "            break\n",
    "        cur = cur.next\n",
    "        pos += 1\n",
    "    print(pos, cur, idx)\n",
    "    if pos < idx - 1:\n",
    "        print(f\"Index {idx} out of range for list size {pos}.\")\n",
    "        return head\n",
    "    \n",
    "    cur.next = cur.next.next\n",
    "    \n",
    "    return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 3 4 "
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"812pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 812.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 808,-41 808,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 174,-36.5 174,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"42\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"84,-0.5 84,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"129\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"210,-0.5 210,-36.5 384,-36.5 384,-0.5 210,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"252\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"294,-0.5 294,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"339\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(3)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.1,-18.5C182.62,-18.5 191.3,-18.5 199.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"199.96,-22 209.96,-18.5 199.96,-15 199.96,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"420,-0.5 420,-36.5 594,-36.5 594,-0.5 420,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"462\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"504,-0.5 504,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"549\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(4)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M384.1,-18.5C392.62,-18.5 401.3,-18.5 409.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"409.96,-22 419.96,-18.5 409.96,-15 409.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"630,-0.5 630,-36.5 804,-36.5 804,-0.5 630,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"672\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"714,-0.5 714,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"759\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M594.1,-18.5C602.62,-18.5 611.3,-18.5 619.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"619.96,-22 629.96,-18.5 619.96,-15 619.96,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0324461c00>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = LinkedList(1)\n",
    "cur = head\n",
    "for i in range(2, 5):\n",
    "    cur.next = LinkedList(i)\n",
    "    cur = cur.next\n",
    "    print(cur.data, end=\" \")\n",
    "print_linked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 LL(3) 4\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"602pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 602.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 598,-41 598,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 174,-36.5 174,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"42\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"84,-0.5 84,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"129\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"210,-0.5 210,-36.5 384,-36.5 384,-0.5 210,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"252\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"294,-0.5 294,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"339\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(3)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.1,-18.5C182.62,-18.5 191.3,-18.5 199.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"199.96,-22 209.96,-18.5 199.96,-15 199.96,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"420,-0.5 420,-36.5 594,-36.5 594,-0.5 420,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"462\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"504,-0.5 504,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"549\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M384.1,-18.5C392.62,-18.5 401.3,-18.5 409.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"409.96,-22 419.96,-18.5 409.96,-15 409.96,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a03245a9630>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = delete_idx_node(head, 4)\n",
    "print_linked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search_list(head, target) -> bool:\n",
    "    while head:\n",
    "        if head.data == target:\n",
    "            return True\n",
    "        head = head.next\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 6 8 "
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"812pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 812.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 808,-41 808,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 174,-36.5 174,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"42\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"84,-0.5 84,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"129\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(4)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"210,-0.5 210,-36.5 384,-36.5 384,-0.5 210,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"252\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"294,-0.5 294,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"339\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(6)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.1,-18.5C182.62,-18.5 191.3,-18.5 199.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"199.96,-22 209.96,-18.5 199.96,-15 199.96,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"420,-0.5 420,-36.5 594,-36.5 594,-0.5 420,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"462\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 6.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"504,-0.5 504,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"549\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(8)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M384.1,-18.5C392.62,-18.5 401.3,-18.5 409.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"409.96,-22 419.96,-18.5 409.96,-15 409.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"630,-0.5 630,-36.5 804,-36.5 804,-0.5 630,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"672\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 8.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"714,-0.5 714,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"759\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M594.1,-18.5C602.62,-18.5 611.3,-18.5 619.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"619.96,-22 629.96,-18.5 619.96,-15 619.96,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0324590ac0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 Not Found In the Given List.\n",
      "8 Found In the Given List.\n"
     ]
    }
   ],
   "source": [
    "head = LinkedList(1)\n",
    "cur = head\n",
    "for i in range(2, 5):\n",
    "    cur.next = LinkedList(i*2)\n",
    "    cur = cur.next\n",
    "    print(cur.data, end=\" \")\n",
    "print_linked_list(head)\n",
    "print(f\"{3} {'Found' if search_list(head, 3) else 'Not Found'} In the Given List.\")\n",
    "print(f\"{8} {'Found' if search_list(head, 4) else 'Not Found'} In the Given List.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. Length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def list_len(head) -> int:\n",
    "    length = 0\n",
    "    while head:\n",
    "        head = head.next\n",
    "        length += 1\n",
    "    return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 3 "
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"602pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 602.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 598,-41 598,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 174,-36.5 174,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"42\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"84,-0.5 84,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"129\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"210,-0.5 210,-36.5 384,-36.5 384,-0.5 210,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"252\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"294,-0.5 294,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"339\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next LL(3)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M174.1,-18.5C182.62,-18.5 191.3,-18.5 199.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"199.96,-22 209.96,-18.5 199.96,-15 199.96,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"420,-0.5 420,-36.5 594,-36.5 594,-0.5 420,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"462\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"504,-0.5 504,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"549\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M384.1,-18.5C392.62,-18.5 401.3,-18.5 409.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"409.96,-22 419.96,-18.5 409.96,-15 409.96,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0311b472e0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length of the list is: 3\n",
      "Length of the list is: 0\n"
     ]
    }
   ],
   "source": [
    "head = LinkedList(1)\n",
    "cur = head\n",
    "for i in range(2, 4):\n",
    "    cur.next = LinkedList(i)\n",
    "    cur = cur.next\n",
    "    print(cur.data, end=\" \")\n",
    "print_linked_list(head)\n",
    "print(f\"Length of the list is: {list_len(head)}\")\n",
    "print(f\"Length of the list is: {list_len(None)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Applications\n",
    "\n",
    "1. **Dynamic Memory Allocation**: The dynamic memory allocation is easier in linked list as the memory can be allocated or deallocated at runtime.\n",
    "2. **Implementation of Stacks and Queues**: Linked list can be used to implement stacks and queues.\n",
    "3. **Undo Functionality**: Undo functionality in Photoshop or Word can be implemented using linked list.\n",
    "4. **Music Player**: Songs in a music player can be stored using linked list.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problems\n",
    "\n",
    "1. [Reverse a linked list](https://leetcode.com/problems/reverse-linked-list/)\n",
    "2. [Detect a cycle in a linked list](https://leetcode.com/problems/linked-list-cycle/)\n",
    "3. [Merge two sorted linked lists](https://leetcode.com/problems/merge-two-sorted-lists/)\n",
    "4. [Remove Nth node from the end of a linked list](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)\n",
    "5. [Rotate a linked list](https://leetcode.com/problems/rotate-list/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Doubly Linked List\n",
    "\n",
    "A doubly linked list is a collection of nodes where each node has two parts: data and two references. The first reference points to the previous node and the second reference points to the next node. The first node is called the head and the last node is called the tail. The head has a reference to `None` in the previous part and the tail has a reference to `None` in the next part. If the list is empty then the head is a `None` reference."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DLinkedList:\n",
    "    def __init__(self, data) -> None:\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "        self.prev = None\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return f\"DLL({self.data})\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "# print doubly linked list inline in notebook using graphviz\n",
    "def print_forward_dlinked_list(head):\n",
    "    dot = Digraph(format='svg', graph_attr={'rankdir':'LR'})\n",
    "    node = head\n",
    "    i = 0\n",
    "    while node:\n",
    "        dot.node(name=str(i), label= \"{ prev %s | data %.2f | next %s}\" % (node.prev, node.data, node.next), shape='record')\n",
    "        if node.next:\n",
    "            dot.edge(f'{i}', f'{i+1}')\n",
    "        i += 1\n",
    "        node = node.next\n",
    "\n",
    "    display(dot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "# print doubly linked list inline in notebook using graphviz\n",
    "def print_bacward_dlinked_list(tail):\n",
    "    dot = Digraph(format='svg', graph_attr={'rankdir':'LR'})\n",
    "    node = tail\n",
    "    i = 0\n",
    "    while node:\n",
    "        dot.node(name=str(i), label= \"{ prev %s | data %.2f | next %s}\" % (node.prev, node.data, node.next), shape='record')\n",
    "        if node.prev:\n",
    "            dot.edge(f'{i}', f'{i+1}')\n",
    "        i += 1\n",
    "        node = node.prev\n",
    "\n",
    "    display(dot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"273pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 273.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 269,-41 269,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 265,-36.5 265,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"220\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0311b46860>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = DLinkedList(2)\n",
    "print_forward_dlinked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Operations\n",
    "\n",
    "1. **Traversal**:\n",
    "    - **Forward Traversal**: Traverse the list from the head to the tail.\n",
    "    - **Backward Traversal**: Traverse the list from the tail to the head.\n",
    "2. **Insertion**:\n",
    "    - Insert at the beginning of the list.\n",
    "    - Insert at the end of the list.\n",
    "    - Insert at the given position.\n",
    "3. **Deletion**:\n",
    "    - Delete the first node.\n",
    "    - Delete the last node.\n",
    "    - Delete the node at the given position.\n",
    "4. **Search**:\n",
    "    - Search for a given element in the list.\n",
    "5. **Length**:\n",
    "    - Find the length of the list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1. Traversal\n",
    "\n",
    "1.1. **Forward Traversal**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1242pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1242.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1238,-41 1238,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(1)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 922,-36.5 922,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"871.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.16,-18.5C607.71,-18.5 616.32,-18.5 624.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.96,-22 634.96,-18.5 624.96,-15 624.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"958,-0.5 958,-36.5 1234,-36.5 1234,-0.5 958,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1009\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(3)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1060,-0.5 1060,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1102\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1144,-0.5 1144,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1189\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M922.02,-18.5C930.59,-18.5 939.22,-18.5 947.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"947.86,-22 957.86,-18.5 947.86,-15 947.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0311b45150>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = DLinkedList(1)\n",
    "N = 5\n",
    "cur = head\n",
    "tail = None\n",
    "for i in range(head.data + 1, N):\n",
    "    new_node = DLinkedList(i)\n",
    "    new_node.prev = cur\n",
    "    cur.next = new_node\n",
    "    cur = cur.next\n",
    "    if i == N-1:\n",
    "        tail = cur\n",
    "\n",
    "print_forward_dlinked_list(head) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.2. Backward Traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1242pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1242.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1238,-41 1238,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"51\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(3)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"102,-0.5 102,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"144\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"186,-0.5 186,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"231\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 922,-36.5 922,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(1)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"871.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.16,-18.5C607.71,-18.5 616.32,-18.5 624.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.96,-22 634.96,-18.5 624.96,-15 624.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"958,-0.5 958,-36.5 1234,-36.5 1234,-0.5 958,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1003.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1049,-0.5 1049,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1091\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1133,-0.5 1133,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1183.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(2)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M922.02,-18.5C930.59,-18.5 939.22,-18.5 947.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"947.86,-22 957.86,-18.5 947.86,-15 947.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0311b45030>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "print_bacward_dlinked_list(tail)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Insertion\n",
    "\n",
    "#### 2.1 Insertion at the beginning"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_dll_at_start(head, data):\n",
    "    if head is None:\n",
    "        return DLinkedList(data)\n",
    "    \n",
    "    new_node = DLinkedList(data)\n",
    "    new_node.next = head\n",
    "    head.prev = new_node\n",
    "    head = new_node\n",
    "\n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1565pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1565.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1561,-41 1561,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 0.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(1)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(0)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(2)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 922,-36.5 922,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(1)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"871.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.16,-18.5C607.71,-18.5 616.32,-18.5 624.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.96,-22 634.96,-18.5 624.96,-15 624.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"958,-0.5 958,-36.5 1245,-36.5 1245,-0.5 958,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1009\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1060,-0.5 1060,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1102\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1144,-0.5 1144,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1194.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M922.16,-18.5C930.71,-18.5 939.32,-18.5 947.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"947.96,-22 957.96,-18.5 947.96,-15 947.96,-22\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1281,-0.5 1281,-36.5 1557,-36.5 1557,-0.5 1281,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1332\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(3)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1383,-0.5 1383,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1425\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1467,-0.5 1467,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1512\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1245.02,-18.5C1253.59,-18.5 1262.22,-18.5 1270.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1270.86,-22 1280.86,-18.5 1270.86,-15 1270.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0311b46110>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = DLinkedList(1)\n",
    "N = 5\n",
    "cur = head\n",
    "tail = None\n",
    "for i in range(head.data + 1, N):\n",
    "    new_node = DLinkedList(i)\n",
    "    new_node.prev = cur\n",
    "    cur.next = new_node\n",
    "    cur = cur.next\n",
    "    if i == N-1:\n",
    "        tail = cur\n",
    "head = insert_dll_at_start(head, 0)\n",
    "print_forward_dlinked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.2 Insertion at the end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_dll_at_end(head, data):\n",
    "    if head is None:\n",
    "        return DLinkedList(data)\n",
    "\n",
    "    cur = head\n",
    "    while cur.next:\n",
    "        cur = cur.next\n",
    "    \n",
    "    new_node = DLinkedList(data)\n",
    "    cur.next = new_node\n",
    "    new_node.prev = cur\n",
    "\n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1888pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1888.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1884,-41 1884,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 0.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(1)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(0)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(2)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 922,-36.5 922,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(1)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"871.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.16,-18.5C607.71,-18.5 616.32,-18.5 624.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.96,-22 634.96,-18.5 624.96,-15 624.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"958,-0.5 958,-36.5 1245,-36.5 1245,-0.5 958,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1009\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1060,-0.5 1060,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1102\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1144,-0.5 1144,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1194.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M922.16,-18.5C930.71,-18.5 939.32,-18.5 947.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"947.96,-22 957.96,-18.5 947.96,-15 947.96,-22\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1281,-0.5 1281,-36.5 1568,-36.5 1568,-0.5 1281,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1332\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(3)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1383,-0.5 1383,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1425\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1467,-0.5 1467,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1517.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(6)</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1245.16,-18.5C1253.71,-18.5 1262.32,-18.5 1270.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1270.96,-22 1280.96,-18.5 1270.96,-15 1270.96,-22\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1604,-0.5 1604,-36.5 1880,-36.5 1880,-0.5 1604,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1655\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(4)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1706,-0.5 1706,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1748\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 6.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1790,-0.5 1790,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1835\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1568.02,-18.5C1576.59,-18.5 1585.22,-18.5 1593.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1593.86,-22 1603.86,-18.5 1593.86,-15 1593.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0324502350>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = insert_dll_at_end(head, 6)\n",
    "print_forward_dlinked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.3 Insertion at the given position"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_dll_at_pos(head, data, pos):\n",
    "    if pos < 1:\n",
    "        print(f\"Invaild position {pos}.\")\n",
    "        return head\n",
    "    \n",
    "    if pos == 1:\n",
    "        return insert_dll_at_start(head, data)\n",
    "\n",
    "    idx = 1\n",
    "    cur = head\n",
    "    while cur.next:\n",
    "        if idx == pos:\n",
    "            break\n",
    "        cur = cur.next\n",
    "        idx += 1\n",
    "\n",
    "    if idx != pos:\n",
    "        print(f\"Invalid position {pos} for the list of length {idx}.\")\n",
    "        return head\n",
    "    \n",
    "    new_node = DLinkedList(data)\n",
    "    new_node.prev = cur.prev\n",
    "    new_node.next = cur\n",
    "    cur.prev.next = new_node\n",
    "    cur.prev = new_node\n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"3503pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 3503.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 3499,-41 3499,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 0.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(1)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(0)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(2)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 922,-36.5 922,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(1)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"871.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.16,-18.5C607.71,-18.5 616.32,-18.5 624.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.96,-22 634.96,-18.5 624.96,-15 624.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"958,-0.5 958,-36.5 1245,-36.5 1245,-0.5 958,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1009\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1060,-0.5 1060,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1102\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1144,-0.5 1144,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1194.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M922.16,-18.5C930.71,-18.5 939.32,-18.5 947.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"947.96,-22 957.96,-18.5 947.96,-15 947.96,-22\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1281,-0.5 1281,-36.5 1568,-36.5 1568,-0.5 1281,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1332\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(3)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1383,-0.5 1383,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1425\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1467,-0.5 1467,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1517.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(7)</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1245.16,-18.5C1253.71,-18.5 1262.32,-18.5 1270.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1270.96,-22 1280.96,-18.5 1270.96,-15 1270.96,-22\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1604,-0.5 1604,-36.5 1891,-36.5 1891,-0.5 1604,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1655\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(4)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1706,-0.5 1706,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1748\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 7.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1790,-0.5 1790,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1840.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(7)</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1568.16,-18.5C1576.71,-18.5 1585.32,-18.5 1593.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1593.96,-22 1603.96,-18.5 1593.96,-15 1593.96,-22\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1927,-0.5 1927,-36.5 2214,-36.5 2214,-0.5 1927,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1978\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(7)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2029,-0.5 2029,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"2071\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 7.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2113,-0.5 2113,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"2163.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(7)</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1891.16,-18.5C1899.71,-18.5 1908.32,-18.5 1916.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1916.96,-22 1926.96,-18.5 1916.96,-15 1916.96,-22\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"2250,-0.5 2250,-36.5 2537,-36.5 2537,-0.5 2250,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"2301\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(7)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2352,-0.5 2352,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"2394\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 7.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2436,-0.5 2436,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"2486.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(7)</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2214.16,-18.5C2222.71,-18.5 2231.32,-18.5 2239.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2239.96,-22 2249.96,-18.5 2239.96,-15 2239.96,-22\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"2573,-0.5 2573,-36.5 2860,-36.5 2860,-0.5 2573,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"2624\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(7)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2675,-0.5 2675,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"2717\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 7.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2759,-0.5 2759,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"2809.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(7)</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2537.16,-18.5C2545.71,-18.5 2554.32,-18.5 2562.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2562.96,-22 2572.96,-18.5 2562.96,-15 2562.96,-22\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"2896,-0.5 2896,-36.5 3183,-36.5 3183,-0.5 2896,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"2947\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(7)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2998,-0.5 2998,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"3040\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 7.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"3082,-0.5 3082,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"3132.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(6)</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2860.16,-18.5C2868.71,-18.5 2877.32,-18.5 2885.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2885.96,-22 2895.96,-18.5 2885.96,-15 2885.96,-22\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"3219,-0.5 3219,-36.5 3495,-36.5 3495,-0.5 3219,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"3270\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(7)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"3321,-0.5 3321,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"3363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 6.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"3405,-0.5 3405,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"3450\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3183.02,-18.5C3191.59,-18.5 3200.22,-18.5 3208.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3208.86,-22 3218.86,-18.5 3208.86,-15 3208.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0311484460>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = insert_dll_at_pos(head, 7, 6)\n",
    "print_forward_dlinked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"3826pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 3826.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 3822,-41 3822,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 8.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(0)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(8)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 0.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(1)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 922,-36.5 922,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(0)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"871.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(2)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.16,-18.5C607.71,-18.5 616.32,-18.5 624.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.96,-22 634.96,-18.5 624.96,-15 624.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"958,-0.5 958,-36.5 1245,-36.5 1245,-0.5 958,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1009\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(1)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1060,-0.5 1060,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1102\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1144,-0.5 1144,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1194.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M922.16,-18.5C930.71,-18.5 939.32,-18.5 947.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"947.96,-22 957.96,-18.5 947.96,-15 947.96,-22\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1281,-0.5 1281,-36.5 1568,-36.5 1568,-0.5 1281,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1332\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1383,-0.5 1383,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1425\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1467,-0.5 1467,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1517.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1245.16,-18.5C1253.71,-18.5 1262.32,-18.5 1270.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1270.96,-22 1280.96,-18.5 1270.96,-15 1270.96,-22\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1604,-0.5 1604,-36.5 1891,-36.5 1891,-0.5 1604,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1655\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(3)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1706,-0.5 1706,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1748\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1790,-0.5 1790,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1840.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(7)</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1568.16,-18.5C1576.71,-18.5 1585.32,-18.5 1593.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1593.96,-22 1603.96,-18.5 1593.96,-15 1593.96,-22\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"1927,-0.5 1927,-36.5 2214,-36.5 2214,-0.5 1927,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1978\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(4)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2029,-0.5 2029,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"2071\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 7.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2113,-0.5 2113,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"2163.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(7)</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1891.16,-18.5C1899.71,-18.5 1908.32,-18.5 1916.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1916.96,-22 1926.96,-18.5 1916.96,-15 1916.96,-22\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"2250,-0.5 2250,-36.5 2537,-36.5 2537,-0.5 2250,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"2301\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(7)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2352,-0.5 2352,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"2394\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 7.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2436,-0.5 2436,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"2486.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(7)</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2214.16,-18.5C2222.71,-18.5 2231.32,-18.5 2239.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2239.96,-22 2249.96,-18.5 2239.96,-15 2239.96,-22\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"2573,-0.5 2573,-36.5 2860,-36.5 2860,-0.5 2573,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"2624\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(7)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2675,-0.5 2675,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"2717\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 7.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2759,-0.5 2759,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"2809.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(7)</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2537.16,-18.5C2545.71,-18.5 2554.32,-18.5 2562.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2562.96,-22 2572.96,-18.5 2562.96,-15 2562.96,-22\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"2896,-0.5 2896,-36.5 3183,-36.5 3183,-0.5 2896,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"2947\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(7)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"2998,-0.5 2998,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"3040\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 7.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"3082,-0.5 3082,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"3132.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(7)</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2860.16,-18.5C2868.71,-18.5 2877.32,-18.5 2885.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2885.96,-22 2895.96,-18.5 2885.96,-15 2885.96,-22\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"3219,-0.5 3219,-36.5 3506,-36.5 3506,-0.5 3219,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"3270\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(7)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"3321,-0.5 3321,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"3363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 7.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"3405,-0.5 3405,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"3455.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(6)</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3183.16,-18.5C3191.71,-18.5 3200.32,-18.5 3208.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3208.96,-22 3218.96,-18.5 3208.96,-15 3208.96,-22\"/>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>11</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"3542,-0.5 3542,-36.5 3818,-36.5 3818,-0.5 3542,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"3593\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(7)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"3644,-0.5 3644,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"3686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 6.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"3728,-0.5 3728,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"3773\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;11 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>10&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M3506.02,-18.5C3514.59,-18.5 3523.22,-18.5 3531.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"3531.86,-22 3541.86,-18.5 3531.86,-15 3531.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0311405420>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = insert_dll_at_pos(head, 8, 1)\n",
    "print_forward_dlinked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Deletion\n",
    "\n",
    "#### 3.1 Delete the first node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delete_dll_first(head):\n",
    "    if head is None:\n",
    "        print(\"Empty list, nothing to delete.\")\n",
    "        return head\n",
    "    \n",
    "    if head.next is None:\n",
    "        del head\n",
    "        return None\n",
    "    \n",
    "    head.next.prev = None\n",
    "    new_head = head.next\n",
    "    del head\n",
    "    return new_head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1242pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1242.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1238,-41 1238,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(1)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 922,-36.5 922,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"871.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.16,-18.5C607.71,-18.5 616.32,-18.5 624.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.96,-22 634.96,-18.5 624.96,-15 624.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"958,-0.5 958,-36.5 1234,-36.5 1234,-0.5 958,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1009\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(3)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1060,-0.5 1060,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1102\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1144,-0.5 1144,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1189\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M922.02,-18.5C930.59,-18.5 939.22,-18.5 947.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"947.86,-22 957.86,-18.5 947.86,-15 947.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0311407f40>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"919pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 919.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 915,-41 915,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 911,-36.5 911,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(3)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"866\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.02,-18.5C607.59,-18.5 616.22,-18.5 624.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.86,-22 634.86,-18.5 624.86,-15 624.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0311407f40>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = DLinkedList(1)\n",
    "N = 5\n",
    "cur = head\n",
    "tail = None\n",
    "for i in range(head.data + 1, N):\n",
    "    new_node = DLinkedList(i)\n",
    "    new_node.prev = cur\n",
    "    cur.next = new_node\n",
    "    cur = cur.next\n",
    "    if i == N-1:\n",
    "        tail = cur\n",
    "print_forward_dlinked_list(head)\n",
    "head = delete_dll_first(head)\n",
    "print_forward_dlinked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.2 Delete the last node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delete_dll_last(head):\n",
    "    if head is None:\n",
    "        print(\"Empty list, nothing to delete.\")\n",
    "        return head\n",
    "    \n",
    "    if head.next is None:\n",
    "        del head\n",
    "        return None\n",
    "    \n",
    "    cur = head\n",
    "    while cur.next:\n",
    "        cur = cur.next\n",
    "\n",
    "    cur.prev.next = None\n",
    "    del cur\n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"919pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 919.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 915,-41 915,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 911,-36.5 911,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(3)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"866\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.02,-18.5C607.59,-18.5 616.22,-18.5 624.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.86,-22 634.86,-18.5 624.86,-15 624.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a03114cded0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"596pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 596.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 592,-41 592,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 588,-36.5 588,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"543\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.32,-18.5C284.82,-18.5 293.39,-18.5 301.93,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.93,-22 311.93,-18.5 301.93,-15 301.93,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a03244bfa00>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "print_forward_dlinked_list(head)\n",
    "head = delete_dll_last(head)\n",
    "print_forward_dlinked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.3 Delete the node at the given position"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delete_dll_at_pos(head, pos):\n",
    "    if pos < 1:\n",
    "        print(f\"Invaild position {pos}.\")\n",
    "        return head\n",
    "    \n",
    "    if pos == 1:\n",
    "        return delete_dll_first(head)\n",
    "\n",
    "    idx = 1\n",
    "    cur = head\n",
    "    while cur.next:\n",
    "        if idx == pos:\n",
    "            break\n",
    "        cur = cur.next\n",
    "        idx += 1\n",
    "\n",
    "    if idx != pos:\n",
    "        print(f\"Invalid position {pos} for the list of length {idx}.\")\n",
    "        return head\n",
    "    \n",
    "    cur.prev.next = cur.next\n",
    "    if cur.next:\n",
    "        cur.next.prev = cur.prev\n",
    "    del cur\n",
    "    \n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1242pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1242.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1238,-41 1238,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(1)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 922,-36.5 922,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"871.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.16,-18.5C607.71,-18.5 616.32,-18.5 624.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.96,-22 634.96,-18.5 624.96,-15 624.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"958,-0.5 958,-36.5 1234,-36.5 1234,-0.5 958,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1009\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(3)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1060,-0.5 1060,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1102\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1144,-0.5 1144,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1189\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M922.02,-18.5C930.59,-18.5 939.22,-18.5 947.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"947.86,-22 957.86,-18.5 947.86,-15 947.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a03114cce20>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"919pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 919.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 915,-41 915,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(1)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 911,-36.5 911,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"866\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.02,-18.5C607.59,-18.5 616.22,-18.5 624.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.86,-22 634.86,-18.5 624.86,-15 624.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a0311407f40>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = DLinkedList(1)\n",
    "N = 5\n",
    "cur = head\n",
    "tail = None\n",
    "for i in range(head.data + 1, N):\n",
    "    new_node = DLinkedList(i)\n",
    "    new_node.prev = cur\n",
    "    cur.next = new_node\n",
    "    cur = cur.next\n",
    "    if i == N-1:\n",
    "        tail = cur\n",
    "print_forward_dlinked_list(head)\n",
    "head = delete_dll_at_pos(head, 3)\n",
    "print_forward_dlinked_list(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_in_dll(head, data)-> bool:\n",
    "    pos = 0\n",
    "    while head.next:\n",
    "        pos += 1\n",
    "        if head.data == data:\n",
    "            print(f\"{data} found at position {pos}.\")\n",
    "            return True\n",
    "        head= head.next\n",
    "    print(f\"{data} not found in the list.\")\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1242pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1242.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1238,-41 1238,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(1)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 922,-36.5 922,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"871.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.16,-18.5C607.71,-18.5 616.32,-18.5 624.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.96,-22 634.96,-18.5 624.96,-15 624.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"958,-0.5 958,-36.5 1234,-36.5 1234,-0.5 958,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1009\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(3)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1060,-0.5 1060,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1102\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1144,-0.5 1144,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1189\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M922.02,-18.5C930.59,-18.5 939.22,-18.5 947.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"947.86,-22 957.86,-18.5 947.86,-15 947.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a03114cf3d0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 found at position 3.\n",
      "6 not found in the list.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 123,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "head = DLinkedList(1)\n",
    "N = 5\n",
    "cur = head\n",
    "tail = None\n",
    "for i in range(head.data + 1, N):\n",
    "    new_node = DLinkedList(i)\n",
    "    new_node.prev = cur\n",
    "    cur.next = new_node\n",
    "    cur = cur.next\n",
    "    if i == N-1:\n",
    "        tail = cur\n",
    "print_forward_dlinked_list(head)\n",
    "find_in_dll(head, 3)\n",
    "find_in_dll(head, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. Length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lenght_dll(head)-> int:\n",
    "    len = 0\n",
    "    while head:\n",
    "        len += 1\n",
    "        head= head.next\n",
    "    return len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"1242pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 1242.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 1238,-41 1238,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 276,-36.5 276,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev None</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"91,-0.5 91,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"133\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"175,-0.5 175,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"225.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"312,-0.5 312,-36.5 599,-36.5 599,-0.5 312,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"363\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(1)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"414,-0.5 414,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"456\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"498,-0.5 498,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"548.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M276.01,-18.5C284.55,-18.5 293.18,-18.5 301.79,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"301.88,-22 311.88,-18.5 301.88,-15 301.88,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"635,-0.5 635,-36.5 922,-36.5 922,-0.5 635,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"686\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(2)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"737,-0.5 737,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"779\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"821,-0.5 821,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"871.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M599.16,-18.5C607.71,-18.5 616.32,-18.5 624.91,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"624.96,-22 634.96,-18.5 624.96,-15 624.96,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"958,-0.5 958,-36.5 1234,-36.5 1234,-0.5 958,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"1009\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">prev DLL(3)</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1060,-0.5 1060,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1102\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"1144,-0.5 1144,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"1189\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next None</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M922.02,-18.5C930.59,-18.5 939.22,-18.5 947.8,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"947.86,-22 957.86,-18.5 947.86,-15 947.86,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a03114cc2e0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length of the list is 4\n"
     ]
    }
   ],
   "source": [
    "print_forward_dlinked_list(head)\n",
    "print(f\"Length of the list is {lenght_dll(head)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Circular Linked List\n",
    "\n",
    "A circular linked list is a collection of nodes where each node has two parts: data and a reference to the next node. The last node has a reference to the first node. The first node is called the head and the last node is called the tail. If the list is empty then the head is a `None` reference."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CLinkedList:\n",
    "    def __init__(self, data) -> None:\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return f\"CLL({self.data})\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [],
   "source": [
    "# print doubly linked list inline in notebook using graphviz\n",
    "def print_forward_clinked_list(head):\n",
    "    dot = Digraph(format='svg', graph_attr={'rankdir':'LR'})\n",
    "    node = head\n",
    "    i = 0\n",
    "    while True:\n",
    "        dot.node(name=str(i), label= \"{ data %.2f | next %s}\" % (node.data, node.next), shape='record')\n",
    "        if node.next:\n",
    "            dot.edge(f'{i}', f'{i+1}')\n",
    "        i += 1\n",
    "        node = node.next\n",
    "        if node == head:\n",
    "            break\n",
    "\n",
    "    display(dot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"946pt\" height=\"45pt\"\n",
       " viewBox=\"0.00 0.00 946.00 45.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 41)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-41 942,-41 942,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"0,-0.5 0,-36.5 185,-36.5 185,-0.5 0,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"42\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 1.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"84,-0.5 84,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"134.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(2)</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"221,-0.5 221,-36.5 406,-36.5 406,-0.5 221,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"263\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 2.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"305,-0.5 305,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"355.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(3)</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M185.11,-18.5C193.62,-18.5 202.27,-18.5 210.86,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"210.91,-22 220.91,-18.5 210.91,-15 210.91,-22\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"442,-0.5 442,-36.5 627,-36.5 627,-0.5 442,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"484\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 3.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"526,-0.5 526,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"576.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next DLL(4)</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M406.11,-18.5C414.62,-18.5 423.27,-18.5 431.86,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"431.91,-22 441.91,-18.5 431.91,-15 431.91,-22\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"663,-0.5 663,-36.5 848,-36.5 848,-0.5 663,-0.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"705\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">data 4.00</text>\n",
       "<polyline fill=\"none\" stroke=\"black\" points=\"747,-0.5 747,-36.5 \"/>\n",
       "<text text-anchor=\"middle\" x=\"797.5\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">next CLL(1)</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M627.11,-18.5C635.62,-18.5 644.27,-18.5 652.86,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"652.91,-22 662.91,-18.5 652.91,-15 652.91,-22\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"911\" cy=\"-18.5\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"911\" y=\"-14.8\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M848.01,-18.5C857.01,-18.5 865.74,-18.5 873.66,-18.5\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"873.91,-22 883.91,-18.5 873.91,-15 873.91,-22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7a02dffdbcd0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "head = CLinkedList(1)\n",
    "N = 5\n",
    "cur = head\n",
    "tail = None\n",
    "for i in range(head.data + 1, N):\n",
    "    new_node = DLinkedList(i)\n",
    "    cur.next = new_node\n",
    "    cur = cur.next\n",
    "    if i == N-1:\n",
    "        tail = cur\n",
    "        tail.next = head\n",
    "print_forward_clinked_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "llama",
   "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}