Singly_Link_List_Problems_With_Solutions.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CPE2B_MamarungkasHanzel_Assign7.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.8.8"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/MMRNGKS/Data-Structures-and-Algorithm-Analysis-Problem-Code-w-Solutions/blob/main/Singly_Link_List_Problems_With_Solutions.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7kc6haR1dDsj"
      },
      "source": [
        "# CPE 211 - Data Structures and Algorithm Analysis\n",
        "\n",
        "SINGLY LINKED LIST\n",
        "\n",
        "November 18, 2021\n",
        "\n",
        "\n",
        "\n",
        "---\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vtvS68BgdX96"
      },
      "source": [
        "**SINGLY LINKED LIST**\n",
        "\n",
        "PROBLEM: \n",
        "\n",
        "Given the class definition for a singly linked list Node below, define a function ***insert_tail(head,new_value)*** that inserts a new node having a value set to ***new_value*** at the tail of a singly linked list with ***head*** as the pointer to its first node. The function ***displayListNodes(head)*** displays all the values of all nodes of SLL with ***head*** pointer on the first node. Define a function ***reverse(head)*** that reverses the direction of the SLL, it returns the tail node as the new head node. You may use 3 node pointers ***prev***, ***current*** and ***next*** as local variables inside the function ***reverse***. Define a function ***isCircularList(head)*** that returns True if the linked list with ***head*** node is a circular list, otherwise it returns False. \n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rMBqmZISdCAC"
      },
      "source": [
        "class Node:\n",
        "    def __init__(self,value):\n",
        "        self.value = value\n",
        "        self.nextnode= None"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RlrYCoZBfVJM"
      },
      "source": [
        "A. Definition of function ***insert_tail(head,new_value)*** below: "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "smnX5gMgdCAL"
      },
      "source": [
        "def insert_tail(head,value):  # inserts a new node with value at the tail of a singly linked list with head as the first node\n",
        "    temp = head               # and returns the new node as the tail of the new list            \n",
        "    while temp.nextnode:      # OR temp.nextnode != None\n",
        "        temp = temp.nextnode\n",
        "    newnode = Node(value)\n",
        "    temp.nextnode=newnode\n",
        "    return newnode"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "apVt-bgxfrzi"
      },
      "source": [
        "B. Definition of function ***displayListNodes(head)*** below: "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ax1qhRaOdCAQ"
      },
      "source": [
        "def displayListNodes(head):  # display all the values of all nodes of a SLL with head as first node\n",
        "    temp = head\n",
        "    while temp:  # OR temp != None\n",
        "        print(temp.value)\n",
        "        temp = temp.nextnode\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2zEvvZAjgA5B"
      },
      "source": [
        "C. Complete the definition of function ***reverse(head)*** below: "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MiWncZr7dCAU"
      },
      "source": [
        "def reverse(head):  # reverse the SLL with head as first node and return the last node as the new head node \n",
        "    lastnode = None\n",
        "    curr = head\n",
        "    while curr:\n",
        "        nex = curr.nextnode\n",
        "        curr.nextnode = lastnode\n",
        "        lastnode = curr\n",
        "        curr = nex\n",
        "    head = lastnode\n",
        "    return lastnode"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EOOjXx2ngbQS"
      },
      "source": [
        "D. Test the function ***insert_tail(head,new_value)*** and ***displayListNodes(head)*** below:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zT1mkhP3dCAa",
        "outputId": "3d0f2f45-bed6-4e50-c346-85009b31caa4"
      },
      "source": [
        "L1=Node(1)\n",
        "insert_tail(L1,2)\n",
        "insert_tail(L1,3)\n",
        "insert_tail(L1,4)\n",
        "insert_tail(L1,5)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<__main__.Node at 0x7f111d0fac10>"
            ]
          },
          "metadata": {},
          "execution_count": 33
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ru9v32n1dCAd",
        "outputId": "e245090b-38d8-43e2-dde9-d5b28437cce1"
      },
      "source": [
        "displayListNodes(L1)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1\n",
            "2\n",
            "3\n",
            "4\n",
            "5\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Vg8Vu6mFg4YB"
      },
      "source": [
        "E. Test the function ***insert_tail(head,new_value)*** and ***displayListNodes(head)*** below:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "v87XnkBNdCAg",
        "outputId": "cd6c390d-23c4-47a7-fc13-7bba2b624d98"
      },
      "source": [
        "L2=Node('Jan')\n",
        "insert_tail(L2,'Feb')\n",
        "insert_tail(L2,'Mar')\n",
        "insert_tail(L2,'Apr')\n",
        "insert_tail(L2,'May')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<__main__.Node at 0x7f111d0fa7d0>"
            ]
          },
          "metadata": {},
          "execution_count": 35
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Ynq8q37jdCAj",
        "outputId": "696c6e76-24d5-43f5-d3b6-c32beff89d9a"
      },
      "source": [
        "displayListNodes(L2)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Jan\n",
            "Feb\n",
            "Mar\n",
            "Apr\n",
            "May\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BjXgaGhak1wM"
      },
      "source": [
        "F. Test the function ***reverse(head)*** below:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-HoKnlYvdCAt"
      },
      "source": [
        "L3=reverse(L1)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2CDP2p4BdCAw",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8fd53927-4768-467b-83b3-47985e28a714"
      },
      "source": [
        "displayListNodes(L3)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "4\n",
            "3\n",
            "2\n",
            "1\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jYNHPwkFdCA2"
      },
      "source": [
        "L4=reverse(L2)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_4nDOy7WdCA5",
        "outputId": "d77c6422-b7ad-4e08-e44b-3e38bf37871b"
      },
      "source": [
        "displayListNodes(L4)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "May\n",
            "Apr\n",
            "Mar\n",
            "Feb\n",
            "Jan\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "r4Fk_nbulKcr"
      },
      "source": [
        "G. Complete the definition of function ***isCircularList(head)*** below: "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ywIpKjT-dCBD"
      },
      "source": [
        "def isCircularList(head): # returns True if linked list is a circular list, otherwise it returns False\n",
        "    if head == None:\n",
        "        return True\n",
        "         \n",
        "    node = head.nextnode\n",
        "    i = 0\n",
        "     \n",
        "    while node != None and node != head:\n",
        "        i = i + 1\n",
        "        node = node.nextnode\n",
        "     \n",
        "    return(print(node==head))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Uo_6adKwlbcp"
      },
      "source": [
        "H. Test the function ***isCircularList(head)*** below:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QJehydVadCBG",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "059e399d-81de-45c3-c6fb-120f06990d7b"
      },
      "source": [
        "isCircularList(L3)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "False\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "MAjsX5JhdCBL",
        "outputId": "c353d4e1-c088-42ac-eba9-7160a106607e"
      },
      "source": [
        "isCircularList(L4)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "False\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yDN_BCsDmMIZ"
      },
      "source": [
        " I. Create a new SLL with head node ***L5*** below:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xDPj0LMRdCBP"
      },
      "source": [
        "L5=Node('Mon')\n",
        "insert_tail(L5,'Tue')\n",
        "insert_tail(L5,'Wed')\n",
        "insert_tail(L5,'Thu')\n",
        "tail=insert_tail(L5,'Fri')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "id": "b64k8nsRdCBU",
        "outputId": "905d20cd-d9a4-43bd-9ae2-352af063f290"
      },
      "source": [
        "tail.value"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'Fri'"
            ]
          },
          "metadata": {},
          "execution_count": 53
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1fyaHJ18lkSD"
      },
      "source": [
        "J. Write a 1 line code below that will make the linked list above with head node ***L5*** a circular list."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vFzN9RpRdCBY"
      },
      "source": [
        "tail.nextnode=L5    # make SLL with head node c as a circular list by making the tail nextnode pointer to point back to head"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GSzCqlDbl9I5"
      },
      "source": [
        "K. Test if SLL with head node ***L5*** is a circular list."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sCn2H_dHdCBh",
        "scrolled": true,
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c51edf1d-ab1b-44ea-c59b-c2658ac05089"
      },
      "source": [
        "isCircularList(L5)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "True\n"
          ]
        }
      ]
    }
  ]
}