Linked List.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "20b4266f",
   "metadata": {},
   "source": [
    "# Single Linked List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "236824e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.nextnode = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "01e43586",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = Node(1)\n",
    "b = Node(2)\n",
    "c = Node(3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "f292a300",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "5133ea1e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "9e4aa089",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.nextnode = b\n",
    "a.nextnode.value"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f85909a9",
   "metadata": {},
   "source": [
    "# Double Linked Lists\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "8f0fade5",
   "metadata": {},
   "outputs": [],
   "source": [
    "class DoubleLinkedListNode(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next_node = None\n",
    "        self.prev_node = None\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "b40dd97d",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = DoubleLinkedListNode(1)\n",
    "b = DoubleLinkedListNode(2)\n",
    "c = DoubleLinkedListNode(3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "ae5601fc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "a.next_node = b\n",
    "b.prev_node = a\n",
    "b.next_node = c\n",
    "print(b.next_node.value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "a0a27a5e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "print(a.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca70d8ea",
   "metadata": {},
   "source": [
    "# Singly Linked List Cycle Check"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "b70a91b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next_node = None\n",
    "        \n",
    "def cycleCheck(node):\n",
    "    marker1 = node \n",
    "    marker2 = node\n",
    "    \n",
    "    while marker2 != None and marker2.next_node != None: \n",
    "        marker1 = marker1.next_node\n",
    "        marker2 = marker2.next_node.next_node\n",
    "        \n",
    "        if marker2 == marker1:\n",
    "            return True\n",
    "        \n",
    "    return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "b92f3517",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "ALL TEST CASES PASSED\n"
     ]
    }
   ],
   "source": [
    "#Run this cell to test your solution\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "a = Node(1)\n",
    "b = Node(2)\n",
    "c = Node(3)\n",
    "\n",
    "a.next_node = b\n",
    "b.next_node = c\n",
    "c.next_node = a #Cycle here!!\n",
    "\n",
    "print(cycleCheck(a))\n",
    "\n",
    "\n",
    "#Non cycle list\n",
    "x = Node(1)\n",
    "y = Node(2)\n",
    "z = Node(3)\n",
    "\n",
    "x.next_node = y\n",
    "y.next_node = z\n",
    "\n",
    "class TestCycleCheck(object):\n",
    "    def test(self, sol):\n",
    "        assert_equal(sol(a), True)\n",
    "        assert_equal(sol(x), False)\n",
    "        \n",
    "        print(\"ALL TEST CASES PASSED\")\n",
    "t = TestCycleCheck()\n",
    "t.test(cycleCheck)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29ddadc9",
   "metadata": {},
   "source": [
    "# Linked List Reserval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "07d00f3c",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next_node = None\n",
    "        \n",
    "def reverse(head):    \n",
    "\n",
    "    previous = None\n",
    "    \n",
    "    while head:\n",
    "        temp = head\n",
    "        head = head.next_node\n",
    "        temp.next_node = previous\n",
    "        previous = temp \n",
    "        \n",
    "    return previous"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "bf133343",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "a = Node(1)\n",
    "b = Node(2)\n",
    "c = Node(3)\n",
    "d = Node(4)\n",
    "\n",
    "a.next_node = b\n",
    "b.next_node = c\n",
    "c.next_node = d\n",
    "\n",
    "print(a.next_node.value)\n",
    "print(b.next_node.value)\n",
    "print(c.next_node.value)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "0f2ad4d8",
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'NoneType' object has no attribute 'value'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-47-4e3cda198804>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0md\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mnext_node\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mvalue\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m: 'NoneType' object has no attribute 'value'"
     ]
    }
   ],
   "source": [
    "d.next_node.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "1230afaf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x23eb8395670>"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverse(a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "d0c821de",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "print(d.next_node.value)\n",
    "print(c.next_node.value)\n",
    "print(b.next_node.value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "339dc377",
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'NoneType' object has no attribute 'value'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-29-1715b6944b26>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mnext_node\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mvalue\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m: 'NoneType' object has no attribute 'value'"
     ]
    }
   ],
   "source": [
    "print(a.next_node.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1948998d",
   "metadata": {},
   "source": [
    "# Linked List nth to last node "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "4debd64e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nth_to_last_node(n, head):\n",
    "    \n",
    "    left_pointer = head\n",
    "    right_pointer = head\n",
    "    \n",
    "    for i in range(n-1):\n",
    "        \n",
    "        if not right_pointer.next_node:\n",
    "            raise LookupError(\"Error: n is larger than the linked list\")\n",
    "        \n",
    "        right_pointer = right_pointer.next_node\n",
    "        \n",
    "    while right_pointer.next_node:\n",
    "        left_pointer = left_pointer.next_node\n",
    "        right_pointer = right_pointer.next_node\n",
    "    return left_pointer\n",
    "\n",
    "class LinkedList():\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next_node = None\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "c3adcb5f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "\n",
    "a = LinkedList(2)\n",
    "b = LinkedList(3)\n",
    "c = LinkedList(4)\n",
    "d = LinkedList(5)\n",
    "e = LinkedList(6)\n",
    "f = LinkedList(7)\n",
    "g = LinkedList(8)\n",
    "\n",
    "a.next_node = b\n",
    "b.next_node = c\n",
    "c.next_node = d\n",
    "d.next_node = e\n",
    "e.next_node = f\n",
    "f.next_node = g\n",
    "\n",
    "\n",
    "print(nth_to_last_node(3,a).value)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "15ba0c3d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "all test cases passed\n"
     ]
    }
   ],
   "source": [
    "from nose.tools import assert_equal\n",
    "\n",
    "class TestNLast(object):\n",
    "    def test(self,sol):\n",
    "        assert_equal(sol(3,a),e)\n",
    "        print(\"all test cases passed\")\n",
    "t = TestNLast()\n",
    "t.test(nth_to_last_node)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fdcc72f8",
   "metadata": {},
   "source": [
    "# Implement a Singly Linked List\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ac89e87d",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.next_node = None\n",
    "    "
   ]
  }
 ],
 "metadata": {
  "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}