AD2. LinkedList.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![img](pic/link.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Element(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedList(object):\n",
    "    def __init__(self, head=None):\n",
    "        self.head = head\n",
    "        \n",
    "        \n",
    "        \n",
    "    '''Append the element'''\n",
    "    def append(self, new_element):\n",
    "        current = self.head\n",
    "        if self.head:\n",
    "            while current.next:\n",
    "                current = current.next\n",
    "            current.next = new_element\n",
    "        else:\n",
    "            self.head = new_element\n",
    "            \n",
    "            \n",
    "            \n",
    "    '''get the element form a given position'''\n",
    "    def get_position(self, position):\n",
    "        current = self.head\n",
    "        count = 1\n",
    "        if self.head:\n",
    "            while count < position:\n",
    "                current = current.next\n",
    "                count += 1\n",
    "            return current\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    '''incert a new element at a given position'''\n",
    "    def insert(self, new_element, position):\n",
    "        current = self.head\n",
    "        count = 1\n",
    "        if position == 1:\n",
    "            new_element.next = current\n",
    "            self.head = new_element\n",
    "        else:\n",
    "            while count < position - 1:\n",
    "                current = current.next\n",
    "                count += 1\n",
    "            new_element.next = current.next\n",
    "            current.next = new_element\n",
    "\n",
    "            \n",
    "    '''Delete the first node with a given value'''\n",
    "      \n",
    "    def delete(self, value):\n",
    "        current = self.head\n",
    "        prev = None\n",
    "        while current and current.value != value:\n",
    "            prev = current\n",
    "            current = current.next\n",
    "        if current is not None:\n",
    "            if current == self.head:\n",
    "                self.head = self.head.next\n",
    "            else:\n",
    "                prev.next = current.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test cases\n",
    "# Set up some Elements\n",
    "e1 = Element(101)\n",
    "e2 = Element(203)\n",
    "e3 = Element(304)\n",
    "e4 = Element(494)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Start setting up a LinkedList\n",
    "ll = LinkedList(e1)\n",
    "ll.append(e2)\n",
    "ll.append(e3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "494\n"
     ]
    }
   ],
   "source": [
    "# Test get_position\n",
    "# Should print 3\n",
    "print(ll.head.next.next.value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "304\n"
     ]
    }
   ],
   "source": [
    "# Should also print 3\n",
    "print(ll.get_position(4).value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "494\n"
     ]
    }
   ],
   "source": [
    "# Test insert\n",
    "ll.insert(e4, 3)\n",
    "# Should print 4 now\n",
    "print (ll.get_position(3).value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "101\n"
     ]
    }
   ],
   "source": [
    "# Test delete\n",
    "ll.delete(1)\n",
    "# Should print 2 now\n",
    "print (ll.get_position(1).value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "203\n"
     ]
    }
   ],
   "source": [
    "# Should print 4 now\n",
    "print (ll.get_position(2).value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "494\n"
     ]
    }
   ],
   "source": [
    "# Should print 3 now\n",
    "print (ll.get_position(3).value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Assignment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - Create a Linked List to store 10000 random numbers and \n",
    " - delete odd positioned numbers and \n",
    " - insert value '555' \n",
    " - write a function to find a sum of all values and calculate sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random as random\n",
    "E =[]\n",
    "for k in range(100):\n",
    "    E.append(Element(random.randint(1,10000)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "ll = LinkedList()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "for  k in range(100):\n",
    "    ll.append(E[k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9656\n",
      "9656\n",
      "4509\n",
      "1356\n",
      "9312\n",
      "8289\n",
      "7020\n",
      "9412\n",
      "4431\n",
      "2283\n",
      "8265\n",
      "9535\n",
      "4155\n",
      "9205\n",
      "4135\n",
      "9736\n",
      "5228\n",
      "4380\n",
      "5084\n",
      "3540\n",
      "7285\n",
      "5262\n",
      "2848\n",
      "3315\n",
      "912\n",
      "5989\n",
      "3884\n",
      "6281\n",
      "179\n",
      "5496\n",
      "5660\n",
      "4249\n",
      "6588\n",
      "3374\n",
      "2093\n",
      "8686\n",
      "3882\n",
      "2106\n",
      "2014\n",
      "5232\n",
      "712\n",
      "8064\n",
      "5489\n",
      "1096\n",
      "9049\n",
      "8249\n",
      "9278\n",
      "1333\n",
      "8010\n",
      "6917\n",
      "9583\n",
      "2687\n",
      "6262\n",
      "2035\n",
      "2881\n",
      "2176\n",
      "6238\n",
      "230\n",
      "7835\n",
      "6427\n",
      "8934\n",
      "5016\n",
      "5557\n",
      "6439\n",
      "9998\n",
      "7756\n",
      "3268\n",
      "1722\n",
      "4205\n",
      "8121\n",
      "4732\n",
      "2966\n",
      "4188\n",
      "6723\n",
      "7726\n",
      "5965\n",
      "8040\n",
      "567\n",
      "181\n",
      "4605\n",
      "2461\n",
      "7387\n",
      "3866\n",
      "5203\n",
      "1940\n",
      "4572\n",
      "5532\n",
      "8942\n",
      "883\n",
      "9101\n",
      "513\n",
      "4534\n",
      "872\n",
      "8980\n",
      "5252\n",
      "7153\n",
      "5669\n",
      "499\n",
      "1785\n",
      "8385\n"
     ]
    }
   ],
   "source": [
    "for i in range(100):\n",
    "    print(ll.get_position(i).value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### This is not a solution. Do it yourself....."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.1"
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}