2.Basic Data Structures.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1\"><a href=\"#Linear-Structure-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Linear Structure</a></div><div class=\"lev2\"><a href=\"#Stack-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Stack</a></div><div class=\"lev3\"><a href=\"#Converting-Decimal-Numbers-to-Binary-Numbers-1.1.1\"><span class=\"toc-item-num\">1.1.1&nbsp;&nbsp;</span>Converting Decimal Numbers to Binary Numbers</a></div><div class=\"lev2\"><a href=\"#Queue-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Queue</a></div><div class=\"lev3\"><a href=\"#Hot-Potato-1.2.1\"><span class=\"toc-item-num\">1.2.1&nbsp;&nbsp;</span>Hot Potato</a></div><div class=\"lev3\"><a href=\"#Printing-Tasks-1.2.2\"><span class=\"toc-item-num\">1.2.2&nbsp;&nbsp;</span>Printing Tasks</a></div><div class=\"lev2\"><a href=\"#Deque-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Deque</a></div><div class=\"lev3\"><a href=\"#Palindrome-Checker-1.3.1\"><span class=\"toc-item-num\">1.3.1&nbsp;&nbsp;</span>Palindrome-Checker</a></div><div class=\"lev2\"><a href=\"#List-1.4\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>List</a></div><div class=\"lev3\"><a href=\"#Unordered-List-1.4.1\"><span class=\"toc-item-num\">1.4.1&nbsp;&nbsp;</span>Unordered List</a></div><div class=\"lev3\"><a href=\"#Ordered-List-1.4.2\"><span class=\"toc-item-num\">1.4.2&nbsp;&nbsp;</span>Ordered List</a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear Structure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "e.g. stacks, queues, deques and lists...\n",
    "\n",
    "Items are ordered depending on how they are added and removed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "LIFO: Last-in, First-out\n",
    "\n",
    "Newer items are near the top, while older items are near the base.\n",
    "\n",
    "Stacks are fundamentally important, as they can be used to reverse the order of items."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Implementing s Stack\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def push(self, item):\n",
    "        self.items.append(item)\n",
    "        \n",
    "    def pop(self):\n",
    "        return self.items.pop()\n",
    "    \n",
    "    def peek(self):\n",
    "        return self.items[len(self.items)-1]\n",
    "        #when you'd like to extract the last item of the list, do not forget len(*)-1.\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "s = Stack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "s.push(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Stack at 0x104f649b0>"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5]"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.isEmpty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "s.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#reverse the order of the given string\n",
    "def revstring(mystr):\n",
    "    # your code here\n",
    "    s = Stack()\n",
    "    newString = ''\n",
    "    for char in mystr:\n",
    "      s.push(char)\n",
    "    \n",
    "    while not s.isEmpty():\n",
    "      newString += s.pop()\n",
    "\t\n",
    "    return newString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "stacks are very important data structures for the processing of language constructs in computer science."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Converting Decimal Numbers to Binary Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How can we easily convert integer values into binary numbers?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def divideBy2(decNumber):\n",
    "    remstack = Stack()\n",
    "    \n",
    "    while decNumber != 0:\n",
    "        reminder = decNumber % 2\n",
    "        quatient = decNumber // 2 \n",
    "        remstack.push(reminder)\n",
    "        decNumber = quatient\n",
    "\n",
    "    binString = \"\"\n",
    "    \n",
    "    while not remstack.isEmpty():\n",
    "        binString = binString + str(remstack.pop())\n",
    "    \n",
    "    return binString"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1011\n"
     ]
    }
   ],
   "source": [
    "print (divideBy2(11))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def baseConverter(decNumber,base):\n",
    "    digits = '0123456789ABCDEF'\n",
    "    \n",
    "    remstack = Stack()\n",
    "    \n",
    "    while decNumber != 0:\n",
    "        reminder = digits[decNumber % base]\n",
    "        quatient = decNumber // base\n",
    "        remstack.push(reminder)\n",
    "        decNumber = quatient\n",
    "\n",
    "    string = \"\"\n",
    "    \n",
    "    while not remstack.isEmpty():\n",
    "        string = string + str(remstack.pop())\n",
    "    \n",
    "    return string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1011'"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "baseConverter(11,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'B'"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "baseConverter(11,16)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'31'"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "baseConverter(25,8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'100'"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "baseConverter(256,16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    #Implementing a queue in python\n",
    "\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "        def enqueue(self, item):\n",
    "            self.items.insert(0, item)\n",
    "            #O(n)\n",
    "\n",
    "        def dequeue(self):\n",
    "            return self.items.pop()\n",
    "\n",
    "        def size(self):\n",
    "            return len(self.items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "q = Queue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "q.enqueue(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.dequeue()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hot Potato"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def hotPotato(namelist, num):\n",
    "    simqueue = Queue()\n",
    "    \n",
    "    #add all children's name to the queue\n",
    "    for name in namelist:\n",
    "        simqueue.enqueue(name)\n",
    "    \n",
    "    #game starts\n",
    "    while simqueue.size() > 1:\n",
    "        #passing a potato repeatedly\n",
    "        for i in range(num):\n",
    "            simqueue.enqueue(simqueue.dequeue())\n",
    "        \n",
    "        #one of them is removed permanentely\n",
    "        simqueue.dequeue()\n",
    "    \n",
    "    return simqueue.dequeue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Susan\n"
     ]
    }
   ],
   "source": [
    "print(hotPotato([\"Bill\",\"David\",\"Susan\",\"Jane\",\"Kent\",\"Brad\"],7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Printing Tasks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average Wait  72.71 secs   1 tasks remaining.\n",
      "Average Wait  32.13 secs   0 tasks remaining.\n",
      "Average Wait  62.27 secs   1 tasks remaining.\n",
      "Average Wait 110.67 secs   0 tasks remaining.\n",
      "Average Wait 142.39 secs   0 tasks remaining.\n",
      "Average Wait 272.00 secs   2 tasks remaining.\n",
      "Average Wait  96.43 secs   1 tasks remaining.\n",
      "Average Wait  11.12 secs   1 tasks remaining.\n",
      "Average Wait 118.21 secs   1 tasks remaining.\n",
      "Average Wait  25.00 secs   2 tasks remaining.\n"
     ]
    }
   ],
   "source": [
    "#Simulate a printing task\n",
    "\n",
    "import random\n",
    "\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    \n",
    "    def enqueue(self, item):\n",
    "        self.items.insert(0, item)\n",
    "        #O(n)\n",
    "\n",
    "    def dequeue(self):\n",
    "        return self.items.pop()\n",
    "        #O(1)\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "\n",
    "class Printer:\n",
    "    def __init__(self, ppm):\n",
    "        self.pagerate = ppm\n",
    "        self.currentTask = None\n",
    "        self.timeRemaining = 0\n",
    "\n",
    "    def tick(self):\n",
    "        if self.currentTask != None:\n",
    "            self.timeRemaining = self.timeRemaining -1\n",
    "            if self.timeRemaining <= 0:\n",
    "                self.currentTask = None\n",
    "\n",
    "    def busy(self):\n",
    "        if self.currentTask != None:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def startNext(self,newtask):\n",
    "        self.currentTask = newtask\n",
    "        self.timeRemaining = newtask.getPages() * 60/self.pagerate\n",
    "\n",
    "class Task:\n",
    "    def __init__(self,time):\n",
    "        self.timestamp = time\n",
    "        self.pages = random.randrange(1,21)\n",
    "\n",
    "    def getStamp(self):\n",
    "        return self.timestamp\n",
    "\n",
    "    def getPages(self):\n",
    "        return self.pages\n",
    "\n",
    "    def waitTime(self, currenttime):\n",
    "        return currenttime - self.timestamp\n",
    "        #How long seconds it takes to register the task\n",
    "        #as the next task after the task is created.\n",
    "\n",
    "def newPrintTask():\n",
    "    num = random.randrange(1,181)\n",
    "    if num == 180:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def simulation(numSeconds, pagesPerMinute):\n",
    "    labprinter = Printer(pagesPerMinute)\n",
    "    printQueue = Queue()\n",
    "    waitingtimes = []\n",
    "\n",
    "    for currentSecond in range(numSeconds):\n",
    "\n",
    "        #A new task emerges every second with probability 1/180\n",
    "        if newPrintTask():\n",
    "            task = Task(currentSecond)\n",
    "            printQueue.enqueue(task)\n",
    "\n",
    "        #In case a new task which already existed in a waiting list\n",
    "        #will be added to the printer\n",
    "        if (not labprinter.busy()) and (not printQueue.isEmpty()):\n",
    "            nexttask = printQueue.dequeue()\n",
    "            waitingtimes.append(nexttask.waitTime(currentSecond))\n",
    "\n",
    "            labprinter.startNext(nexttask)\n",
    "\n",
    "        labprinter.tick()\n",
    "\n",
    "    averageWait = sum(waitingtimes)/len(waitingtimes)\n",
    "\n",
    "    print(\"Average Wait %6.2f secs %3d tasks remaining.\"%(averageWait,printQueue.size()))\n",
    "\n",
    "for i in range(10):\n",
    "    simulation(3600,5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average Wait   4.65 secs   0 tasks remaining.\n",
      "Average Wait  13.32 secs   0 tasks remaining.\n",
      "Average Wait  15.57 secs   1 tasks remaining.\n",
      "Average Wait   7.30 secs   0 tasks remaining.\n",
      "Average Wait  11.47 secs   0 tasks remaining.\n",
      "Average Wait   8.07 secs   0 tasks remaining.\n",
      "Average Wait  11.80 secs   1 tasks remaining.\n",
      "Average Wait  29.76 secs   0 tasks remaining.\n",
      "Average Wait  30.57 secs   0 tasks remaining.\n",
      "Average Wait  20.83 secs   0 tasks remaining.\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    simulation(3600,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average Wait   2.00 secs   0 tasks remaining.\n",
      "Average Wait   3.58 secs   0 tasks remaining.\n",
      "Average Wait   1.40 secs   0 tasks remaining.\n",
      "Average Wait   9.95 secs   0 tasks remaining.\n",
      "Average Wait   0.47 secs   0 tasks remaining.\n",
      "Average Wait   2.70 secs   0 tasks remaining.\n",
      "Average Wait   1.79 secs   0 tasks remaining.\n",
      "Average Wait   1.95 secs   0 tasks remaining.\n",
      "Average Wait   1.95 secs   0 tasks remaining.\n",
      "Average Wait   2.40 secs   0 tasks remaining.\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    simulation(3600,20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deque"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Deque stands for Double Ended Queue.\n",
    "\n",
    "This hybrid linear structure provides all the capabilities of stacks and queues in a single data structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Implement Deque in Python\n",
    "\n",
    "class Deque:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    def isEmpty(self):\n",
    "        #note how to judge whether the list is empty or not\n",
    "        return self.items == []\n",
    "\n",
    "    def addFront(self, item):\n",
    "        #note that we assign the O(1) acction to addFront\n",
    "        self.items.append(item)\n",
    "\n",
    "    def addRear(self, item):\n",
    "        #O(n)\n",
    "        self.items.append(0,item)\n",
    "\n",
    "    def removeFront(self):\n",
    "        return self.items.pop()\n",
    "\n",
    "    def removeRear(self):\n",
    "        return self.items.pop(0)\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Palindrome-Checker"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "palindrome: 回文"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def palchecker(aString):\n",
    "    chardeque = Deque()\n",
    "\n",
    "    for ch in aString:\n",
    "        chardeque.addFront(ch)\n",
    "\n",
    "    stillEqual = True\n",
    "\n",
    "    while chardeque.size() > 1 and stillEqual:\n",
    "        first = chardeque.removeFront()\n",
    "        last = chardeque.removeRear()\n",
    "        if first != last:\n",
    "            stillEqual = False\n",
    "\n",
    "    return stillEqual"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will implement an unordered list, using the commonly known data structure called \"linked list\".\n",
    "\n",
    "In order to construct linked list, we will use the node as a basic structure.\n",
    "\n",
    "Node = Data Field + Reference to the next item"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Unordered List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "code_folding": [
     0
    ],
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Implement an unordered list, using the node\n",
    "\n",
    "#First, we construct the node class.\n",
    "class Node:\n",
    "    def __init__(self, initdata):\n",
    "        self.data = initdata\n",
    "        self.next = None\n",
    "\n",
    "    def getData(self):\n",
    "        return self.data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.next\n",
    "\n",
    "    def setData(self, newdata):\n",
    "        self.data = newdata\n",
    "\n",
    "    def setNext(self, newnext):\n",
    "        self.next = newnext\n",
    "        #self.next refers to another node\n",
    "\n",
    "#Then, we construct the unordered list class, using nodes.\n",
    "#Note that a list itself doesn't contain nodes as its elements. It contains only its head.\n",
    "\n",
    "class UnorderedList:\n",
    "    def __init__(self):\n",
    "        #head is a reference to the first node.\n",
    "        self.head = None\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "\n",
    "    #Note that the new item is to be referred by the head\n",
    "    def add(self,item):\n",
    "        temp = Node(item)\n",
    "        temp.setNext(self.head)\n",
    "        self.head = temp\n",
    "\n",
    "    def size(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "\n",
    "        #implement traversal\n",
    "        while current != None:\n",
    "            count += 1\n",
    "            current = current.getNext()\n",
    "\n",
    "        return count\n",
    "\n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        while current != None and not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                current = current.getNext()\n",
    "        return found\n",
    "\n",
    "    def remove(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        found = False\n",
    "        while not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "\n",
    "        if previous == None:\n",
    "            #In case the first element corresponds to the item to be removed\n",
    "            self.head = current.getNext()\n",
    "        else:\n",
    "            previous.setNext(current.getNext())\n",
    "\n",
    "    def append(self, item):\n",
    "        #add the item to the end of the list cf:add is to add the item to the beginning of the list\n",
    "        #item is a node\n",
    "        if self.size == 0:\n",
    "            self.add(item)\n",
    "        else:\n",
    "            current = self.head\n",
    "            previous = None\n",
    "            while current != None:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "            previous.next = item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "test = UnorderedList()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "test.add(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "test.add(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "test.append(Node(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test.search(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test.search(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "code_folding": [
     0
    ],
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Implement an unordered list, using the node\n",
    "\n",
    "#First, we construct the node class.\n",
    "class Node:\n",
    "    def __init__(self, initdata):\n",
    "        self.data = initdata\n",
    "        self.next = None\n",
    "\n",
    "    def getData(self):\n",
    "        return self.data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.next\n",
    "\n",
    "    def setData(self, newdata):\n",
    "        self.data = newdata\n",
    "\n",
    "    def setNext(self, newnext):\n",
    "        self.next = newnext\n",
    "        #self.next refers to another node\n",
    "\n",
    "#Then, we construct the unordered list class, using nodes.\n",
    "#Note that a list itself doesn't contain nodes as its elements. It contains only its head.\n",
    "\n",
    "class UnorderedList:\n",
    "    def __init__(self):\n",
    "        #head is a reference to the first node.\n",
    "        self.head = None\n",
    "\n",
    "        #Add another instance \"tail\" in order to implement append method in O(1) time\n",
    "        #tail refers to the last node\n",
    "        self.tail = None\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "\n",
    "    #Note that the new item is to be referred by the head\n",
    "    def add(self,item):\n",
    "        temp = Node(item)\n",
    "\n",
    "        if self.isEmpty():\n",
    "            self.head = temp\n",
    "            self.tail = temp\n",
    "        else:\n",
    "            temp.setNext(self.head)\n",
    "            self.head = temp\n",
    "\n",
    "    def size(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "\n",
    "        #implement traversal\n",
    "        while current != None:\n",
    "            count += 1\n",
    "            current = current.getNext()\n",
    "\n",
    "        return count\n",
    "\n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        while current != None and not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                current = current.getNext()\n",
    "        return found\n",
    "\n",
    "    def remove(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        found = False\n",
    "        while not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "\n",
    "        if previous == None:\n",
    "            #In case the first element corresponds to the item to be removed\n",
    "            self.head = current.getNext()\n",
    "        else:\n",
    "            previous.setNext(current.getNext())\n",
    "\n",
    "    def append(self, item):\n",
    "        #add the item to the end of the list cf:add is to add the item to the beginning of the list\n",
    "        #item is a data\n",
    "        #Using tail instance to get faster\n",
    "        \n",
    "        if self.size == 0:\n",
    "            self.add(item)\n",
    "        else:\n",
    "            temp = Node(item)\n",
    "            self.tail.next = temp\n",
    "            self.tail = temp\n",
    "\n",
    "        '''\n",
    "        #Older Version of the append method\n",
    "        temp = Node(item)\n",
    "        if self.size == 0:\n",
    "            self.add(item)\n",
    "        else:\n",
    "            current = self.head\n",
    "            previous = None\n",
    "            while current != None:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "            previous.next = temp\n",
    "        '''\n",
    "\n",
    "    def getItems(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "        iteration = self.size()\n",
    "        while  count < iteration:\n",
    "            print (current.data)\n",
    "            if count < iteration -1:\n",
    "                current = current.next\n",
    "            count += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "test = UnorderedList()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "test.add(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "test.getItems()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "test.add(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "test.getItems()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test.search(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "test.append(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "1\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "test.getItems()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ordered List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "code_folding": [
     0
    ],
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Implement an unordered list, using the node\n",
    "\n",
    "#First, we construct the node class.\n",
    "class Node:\n",
    "    def __init__(self, initdata):\n",
    "        self.data = initdata\n",
    "        self.next = None\n",
    "\n",
    "    def getData(self):\n",
    "        return self.data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.next\n",
    "\n",
    "    def setData(self, newdata):\n",
    "        self.data = newdata\n",
    "\n",
    "    def setNext(self, newnext):\n",
    "        self.next = newnext\n",
    "        #self.next refers to another node\n",
    "\n",
    "#Then, construct the ordered list class, using nodes.\n",
    "\n",
    "class OrderedList:\n",
    "    def __init__(self):\n",
    "        #head is a reference to the first node.\n",
    "        self.head = None\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "\n",
    "    def size(self):\n",
    "        current = self.head\n",
    "        count = 0\n",
    "\n",
    "        #implement traversal\n",
    "        while current != None:\n",
    "            count += 1\n",
    "            current = current.getNext()\n",
    "\n",
    "        return count\n",
    "\n",
    "    def remove(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        found = False\n",
    "        while not found:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "\n",
    "        if previous == None:\n",
    "            #In case the first element corresponds to the item to be removed\n",
    "            self.head = current.getNext()\n",
    "        else:\n",
    "            previous.setNext(current.getNext())\n",
    "\n",
    "    def search(self,item):\n",
    "        current = self.head\n",
    "        found = False\n",
    "        #Add another variable \"stop\"\n",
    "        stop = False\n",
    "\n",
    "        while current != None and not found and not stop:\n",
    "            if current.getData() == item:\n",
    "                found = True\n",
    "            else:\n",
    "                if current.getData() > item:\n",
    "                    stop = True\n",
    "\n",
    "        return found\n",
    "\n",
    "    def add(self,item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        stop = False\n",
    "\n",
    "        while current != None and not stop:\n",
    "            if current.getData() > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "\n",
    "        temp = Node(item)\n",
    "\n",
    "        if previous == None:\n",
    "            temp.setNext(self.head)\n",
    "            self.head = temp\n",
    "        else:\n",
    "            temp.setNext(current)\n",
    "            previous.setNext(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.4.3"
  },
  "toc": {
   "toc_cell": true,
   "toc_number_sections": true,
   "toc_threshold": 6,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}