adding book

1 files changed, 338 insertions, 0 deletions

diff --git a/Data_Structures_and_Algorithms_in_Java/ch5.ipynb b/Data_Structures_and_Algorithms_in_Java/ch5.ipynb
new file mode 100644
index 00000000..6ac7b766
--- /dev/null
+++ b/Data_Structures_and_Algorithms_in_Java/ch5.ipynb
@@ -0,0 +1,338 @@
+{
+ "metadata": {
+  "name": "ch5"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+  {
+   "cells": [
+    {
+     "cell_type": "heading",
+     "level": 1,
+     "metadata": {},
+     "source": "Chapter 5 : Linked Lists"
+    },
+    {
+     "cell_type": "heading",
+     "level": 3,
+     "metadata": {},
+     "source": "Example 5.1 Page No : 190"
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": "'''\nExample 5.1\nLink List\n'''\n\nclass Link:\n    def __init__(self,i,dd):\n        self.iData = i\n        self.dData = dd\n        self.next = None\n\n    def displayLink(self): # display ourself\n        print '{'  , self.iData , ', ' , self.dData , '} ' ,\n\nclass LinkList:\n    def __init__(self):\n        self.first = None\n\n    def isEmpty(self): # true if list is empty\n        return (self.first==None)\n\n    # insert at start of list\n    def insertFirst(self,i,  dd):\n        # make new link\n        newLink = Link(i, dd)\n        newLink.next = self.first\n        # newLink --> old first\n        self.first = newLink\n\n    def deleteFirst(self):\n        temp = self.first\n        self.first = self.first.next\n        return temp\n    \n    def displayList(self):\n        print 'List (first-->last): ' ,\n        current = self.first\n        while(current != None):\n            current.displayLink()\n            current = current.next\n        print ''\n\ntheList = LinkList() # make new list\ntheList.insertFirst(22,2.99)\ntheList.insertFirst(44,4.99)\ntheList.insertFirst(66,6.99)\ntheList.insertFirst(88,8.99)\ntheList.displayList()\n\nwhile( not theList.isEmpty() ): # until it's empty,\n    aLink = theList.deleteFirst() # delete link\n    print 'Deleted ' ,  # display it\n    aLink.displayLink()\n    print ''\n    \ntheList.displayList()",
+     "language": "python",
+     "metadata": {},
+     "outputs": [
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "List (first-->last):  { 88 ,  8.99 }  { 66 ,  6.99 }  { 44 ,  4.99 }  { 22 ,  2.99 }  \nDeleted  { 88 ,  8.99 }  \nDeleted  { 66 ,  6.99 }  \nDeleted  { 44 ,  4.99 }  \nDeleted  { 22 ,  2.99 }  \nList (first-->last):  \n"
+      }
+     ],
+     "prompt_number": 1
+    },
+    {
+     "cell_type": "heading",
+     "level": 3,
+     "metadata": {},
+     "source": "Example 5.2  Page No : 193"
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": "'''\nExample 5.2\ndemonstrates linked list\n'''\nclass Link:\n    def __init__(self,i,dd):\n        self.iData = i\n        self.dData = dd\n        self.next = None\n\n    def displayLink(self): # display ourself\n        print '{'  , self.iData , ', ' , self.dData , '} ' ,\n\nclass LinkList:\n    def __init__(self):\n        self.first = None\n\n    def isEmpty(self): # true if list is empty\n        return (self.first==None)\n\n    # insert at start of list\n    def insertFirst(self,i,  dd):\n        # make new link\n        newLink = Link(i, dd)\n        newLink.next = self.first\n        # newLink --> old first\n        self.first = newLink\n\n    def deleteFirst(self):\n        temp = self.first\n        self.first = self.first.next\n        return temp\n    \n    def displayList(self):\n        print 'List (first-->last): ' ,\n        current = self.first\n        while(current != None):\n            current.displayLink()\n            current = current.next\n        print ''\n\n    def find(self,key): # find link with given key\n        current = self.first #start at first\n        while(current.iData != key): # while no match,\n            if(current.next == None): # if end of list,\n                return None # didnt find it\n            else:\n                current = current.next # go to next link\n        return current\n    \n    def delete(self,key): # delete link with given key\n        current = self.first \n        previous = self.first\n        while(current.iData != key):\n            if(current.next == None):\n                return None # didnt find it\n            else:\n                previous = current\n                current = current.next\n        if(current == self.first): # if first link,\n            self.first = self.first.next\n        else:\n            previous.next = current.next\n        return current\n\n\ntheList = LinkList() # make list\ntheList.insertFirst(22,2.99)\ntheList.insertFirst(44,4.99)\ntheList.insertFirst(66,6.99)\ntheList.insertFirst(88,8.99)\ntheList.displayList()  # display list\nf = theList.find(44) # find item\nif( f != None):\n    print 'Found link with key ' , f.iData\nelse:\n    print \"Can't find link\"\nd = theList.delete(66) # delete item\nif( d != None ):\n    print \"Deleted link with key \" , d.iData\nelse:\n    print \"Can't delete link\"\n\ntheList.displayList()",
+     "language": "python",
+     "metadata": {},
+     "outputs": [
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "List (first-->last):  { 88 ,  8.99 }  { 66 ,  6.99 }  { 44 ,  4.99 }  { 22 ,  2.99 }  \nFound link with key  44\nDeleted link with key  66\nList (first-->last):  { 88 ,  8.99 }  { 44 ,  4.99 }  { 22 ,  2.99 }  \n"
+      }
+     ],
+     "prompt_number": 2
+    },
+    {
+     "cell_type": "heading",
+     "level": 3,
+     "metadata": {},
+     "source": "Example 5.3 Page NO :198"
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": "'''\nExample 5.3\ndemonstrates list with first and last references\n'''\nclass Link:\n    def __init__(self,d):\n        self.dData = d\n        self.next = None\n\n    def displayLink(self): # display ourself\n        print self.dData , \n\nclass FirstLastList:\n    def __init__(self):\n        self.first = None\n        self.last = None\n\n    def isEmpty(self): # true if list is empty\n        return (self.first==None)\n\n    # insert at start of list\n    def insertFirst(self, dd):\n        # make new link\n        newLink = Link(dd)\n        if (self.isEmpty()):\n            self.last = newLink\n        newLink.next = self.first\n        # newLink --> old first\n        self.first = newLink\n\n    def deleteFirst(self):\n        temp = self.first\n        if self.first.next ==None:\n            self.last = None\n        self.first = self.first.next\n        return temp\n\n    def insertLast(self,dd): # insert at end of list\n        newLink = Link(dd) # make new link\n        if( self.isEmpty() ): # if empty list,\n            self.first = newLink # first --> newLink\n        else:\n            self.last.next = newLink # old last --> newLink\n            self.last = newLink # newLink <-- last\n\n    def displayList(self):\n        print 'List (first-->last): ' ,\n        current = self.first\n        while(current != None):\n            current.displayLink()\n            current = current.next\n        print ''\n\n\ntheList = FirstLastList()\ntheList.insertFirst(22) \ntheList.insertLast(11)\ntheList.insertFirst(44) \ntheList.insertLast(33) \ntheList.insertFirst(66) \ntheList.insertLast(55) \ntheList.displayList() # display the list\ntheList.deleteFirst() \ntheList.deleteFirst() \ntheList.displayList() # display again",
+     "language": "python",
+     "metadata": {},
+     "outputs": [
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "List (first-->last):  66 44 22 11 33 55 \nList (first-->last):  22 11 33 55 \n"
+      }
+     ],
+     "prompt_number": 3
+    },
+    {
+     "cell_type": "heading",
+     "level": 3,
+     "metadata": {},
+     "source": "Example 5.4  Page No : 204"
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": "'''\nexample 5.4\ndemonstrates a stack implemented as a list\n'''\nclass Link:\n    def __init__(self,dd):\n        self.dData = dd\n        self.next = None\n\n    def displayLink(self): # display ourself\n        print self.dData , \n\nclass LinkList:\n    def __init__(self):\n        self.first = None\n\n    def isEmpty(self): # true if list is empty\n        return (self.first==None)\n\n    # insert at start of list\n    def insertFirst(self, dd):\n        # make new link\n        newLink = Link( dd)\n        newLink.next = self.first\n        # newLink --> old first\n        self.first = newLink\n\n    def deleteFirst(self):\n        temp = self.first\n        self.first = self.first.next\n        return temp\n    \n    def displayList(self):\n        current = self.first\n        while(current != None):\n            current.displayLink()\n            current = current.next\n        print ''\n\nclass LinkStack:\n    def __init__(self):\n        self.theList = LinkList()\n\n    def push(self,j): # put item on top of stack\n        self.theList.insertFirst(j)\n\n    def pop(self): # take item from top of stack\n        return self.theList.deleteFirst()\n\n    def isEmpty(self):\n        return ( self.theList.isEmpty() )\n\n    def displayStack(self):\n        print 'Stack (top-->bottom): ' ,\n        self.theList.displayList()\n\ntheStack = LinkStack() # make stack\ntheStack.push(20)\ntheStack.push(40) \ntheStack.displayStack() # display stack\n\ntheStack.push(60) # push items\ntheStack.push(80) \ntheStack.displayStack() # display stack\ntheStack.pop() \ntheStack.pop() \ntheStack.displayStack() # display stack",
+     "language": "python",
+     "metadata": {},
+     "outputs": [
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "Stack (top-->bottom):  40 20 \nStack (top-->bottom):  80 60 40 20 \nStack (top-->bottom):  40 20 \n"
+      }
+     ],
+     "prompt_number": 4
+    },
+    {
+     "cell_type": "heading",
+     "level": 3,
+     "metadata": {},
+     "source": "Example 5.5 Page No : 207"
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": "'''\nExample 5.5\ndemonstrates queue implemented as double-ended list\n'''\n\nclass Link:\n    def __init__(self,d): # constructor\n        self.dData = d\n        self.next = None\n\n    def displayLink(self): # display this link\n        print self.dData ,\n\nclass FirstLastList:\n    def __init__(self):\n        self.first = None\n        self.last = None\n\n    def isEmpty(self): # true if list is empty\n        return (self.first==None)\n\n    # insert at start of list\n    def insertFirst(self, dd):\n        # make new link\n        newLink = Link(dd)\n        if (self.isEmpty()):\n            self.last = newLink\n        newLink.next = self.first\n        # newLink --> old first\n        self.first = newLink\n\n    def deleteFirst(self):\n        temp = self.first\n        if self.first.next ==None:\n            self.last = None\n        self.first = self.first.next\n        return temp\n\n    def insertLast(self,dd): # insert at end of list\n        newLink = Link(dd) # make new link\n        if( self.isEmpty() ): # if empty list,\n            self.first = newLink # first --> newLink\n        else:\n            self.last.next = newLink # old last --> newLink\n        self.last = newLink # newLink <-- last\n    \n    def displayList(self):\n        print 'List (first-->last): ' ,\n        current = self.first\n        while(current != None):\n            current.displayLink()\n            current = current.next\n        print ''\n\n\nclass LinkQueue:\n    def __init__(self):\n        self.theList = FirstLastList() # make a 2-ended list\n\n    def isEmpty(self): # true if queue is empty\n        return self.theList.isEmpty()\n        \n    def insert(self,j): # insert, rear of queue\n        self.theList.insertLast(j)\n        \n    def remove(self): # remove, front of queue\n        return self.theList.deleteFirst()\n        \n    def displayQueue(self):\n        print 'Queue (front-->rear): ' , \n        self.theList.displayList()\n\ntheQueue = LinkQueue()\ntheQueue.insert(20) # insert items\ntheQueue.insert(40) \ntheQueue.displayQueue() # display queue\ntheQueue.insert(60) # insert items\ntheQueue.insert(80) \ntheQueue.displayQueue() # display queue\ntheQueue.remove() # remove items\ntheQueue.remove() \ntheQueue.displayQueue() # display queue",
+     "language": "python",
+     "metadata": {},
+     "outputs": [
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "Queue (front-->rear):  List (first-->last):  20 40 \nQueue (front-->rear):  List (first-->last):  20 40 60 80 \nQueue (front-->rear):  List (first-->last):  60 80 \n"
+      }
+     ],
+     "prompt_number": 5
+    },
+    {
+     "cell_type": "heading",
+     "level": 3,
+     "metadata": {},
+     "source": "Example 5.6  Page No : 215"
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": "'''\nexample 5.6\ndemonstrates sorted list\n'''\n\nclass Link:\n    def __init__(self,d): # constructor\n        self.dData = d\n        self.next = None\n\n    def displayLink(self): # display this link\n        print self.dData ,\n\nclass SortedList:\n    def __init__(self):\n        self.first = None\n\n    def isEmpty(self): # true if no links\n        return (self.first==None)\n\n    def insert(self,key): # insert, in order\n        newLink =  Link(key) # make new link\n        previous = None\n        current = self.first # until end of list,\n        while(current != None and key > current.dData):\n            previous = current\n            current = current.next\n        if(previous==None): # at beginning of list\n                self.first = newLink\n        else: # not at beginning\n                previous.next = newLink\n        newLink.next = current\n\n    def remove(self): # return & delete first link\n        temp = self.first # save first\n        self.first = self.first.next # delete first\n        return temp\n\n    def  displayList(self):\n        print \"List (first-->last): \" ,\n        current = self.first # start at beginning of listSorted Lists\n        while(current != None): # until end of list,\n            current.displayLink()\n            current = current.next # move to next link\n        print ''\n\n# create new list\ntheSortedList = SortedList()\ntheSortedList.insert(20) # insert 2 items\ntheSortedList.insert(40)\ntheSortedList.displayList() # display list\ntheSortedList.insert(10)\ntheSortedList.insert(30)\ntheSortedList.insert(50) # insert 3 more items\ntheSortedList.displayList() # display list\ntheSortedList.remove() # remove an item\ntheSortedList.displayList() # display list",
+     "language": "python",
+     "metadata": {},
+     "outputs": [
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "List (first-->last):  20 40 \nList (first-->last):  10 20 30 40 50 \nList (first-->last):  20 30 40 50 \n"
+      }
+     ],
+     "prompt_number": 6
+    },
+    {
+     "cell_type": "heading",
+     "level": 3,
+     "metadata": {},
+     "source": "Example 5.7  Page No : 218"
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": "'''\nexample 5.7\ndemonstrates sorted list used for sorting\n'''\nclass Link:\n    def __init__(self,d): # constructor\n        self.dData = d\n        self.next = None\n\n    def displayLink(self): # display this link\n        print self.dData ,\n\nclass SortedList:\n    def __init__(self,linkArr = None):\n        if linkArr == None:\n            self.first = None\n        else:\n            self.first = None # initialize list\n            for j in range(len(linkArr)):\n                self.insert( linkArr[j] )\n\n    def isEmpty(self): # true if no links\n        return (self.first==None)\n\n    def insert(self,k): # insert, in order\n        previous = None\n        current = self.first # until end of list,\n        while(current != None and k.dData > current.dData):\n            previous = current\n            current = current.next\n        if(previous==None): # at beginning of list\n                self.first = k\n        else: # not at beginning\n                previous.next = k\n        k.next = current\n\n    def remove(self): # return & delete first link\n        temp = self.first # save first\n        self.first = self.first.next # delete first\n        return temp\n\n    def  displayList(self):\n        print \"List (first-->last): \" ,\n        current = self.first # start at beginning of listSorted Lists\n        while(current != None): # until end of list,\n            current.displayLink()\n            current = current.next # move to next link\n        print ''\n\n\nsize = 10 # create array of links\nlinkArray = []\nimport random\nfor j in range(size): # fill array with links\n    # random number\n    n = int(random.random()*99)\n    newLink = Link(n) # make link\n    linkArray.append(newLink) # put in array\n\n# display array contents\nprint 'Unsorted array: ',\nfor j in range(size):\n    print linkArray[j].dData , \nprint ''\n\n# create new list\n# initialized with array\ntheSortedList = SortedList(linkArray)\nlinkArray = []\nfor j in range(size): # links from list to array\n    linkArray.append( theSortedList.remove())\n# display array contents\nprint 'Sorted Array: ',\nfor j in range(size):\n    print linkArray[j].dData ,",
+     "language": "python",
+     "metadata": {},
+     "outputs": [
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "Unsorted array:  28 87 63 12 73 91 30 91 85 65 \nSorted Array:  12 28 30 63 65 73 85 87 91 91\n"
+      }
+     ],
+     "prompt_number": 7
+    },
+    {
+     "cell_type": "heading",
+     "level": 3,
+     "metadata": {},
+     "source": "Example 5.8  Page no : 226"
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": "'''\nExample 5.8\ndemonstrates doubly-linked list\n'''\nclass Link:\n    def __init__(self,d): # constructor\n        self.dData = d\n        self.next = None\n        self.previous = None\n\n    def displayLink(self): # display this link\n        print self.dData ,\n\nclass DoublyLinkedList:\n    def __init__(self):\n        self.first = None # no items on list yet\n        self.last = None\n\n    def isEmpty(self): # true if no links\n        return self.first==None\n\n    def insertFirst(self,dd): # insert at front of list\n        newLink =  Link(dd) # make new link\n        if( self.isEmpty() ): # if empty list,    \n            self.last = newLink # newLink <-- last\n        else:\n            self.first.previous = newLink # newLink <-- old first\n        newLink.next = self.first # newLink --> old first\n        self.first = newLink # first --> newLink\n\n    def insertLast(self,dd):     # insert at end of list\n        newLink = Link(dd) # make new link\n        if( self.isEmpty() ) :    # if empty list,\n            self.first = newLink # first --> newLink\n        else:\n            self.last.next = newLink # old last --> newLink\n            newLink.previous = self.last    # old last <-- newLink\n        self.last = newLink # newLink <-- last\n\n    def deleteFirst(self): # delete first link\n        # (assumes non-empty list)\n        temp = self.first\n        if(self.first.next == None):             # if only one item\n            self.last = None # None <-- last\n        else:\n            self.first.next.previous = None # None <-- old next\n        self.first = self.first.next # first --> old next\n        return temp\n\n    def deleteLast(self): # delete last link\n        # (assumes non-empty list)\n        temp = self.last\n        if(self.first.next == None): # if only one item\n            self.first = None    # first --> None\n        else:\n            self.last.previous.next = None # old previous --> None\n            self.last = self.last.previous # old previous <-- last\n        return temp\n\n    # insert dd just after key\n    def insertAfter(self,key,dd):\n        # (assumes non-empty list)\n        current = self.first # start at beginning\n        while(current.dData != key):    # until match is found,\n            current = current.next # move to next link\n            if(current == None):\n                return False # didnt find it\n        newLink = Link(dd) # make new link\n        if(current==self.last): # if last link,\n            newLink.next = None   # newLink --> None\n            self.last = newLink# newLink <-- last\n        else: # not last link,\n            newLink.next = current.next # newLink --> old next # newLink <-- old next\n            current.next.previous = newLink\n        newLink.previous = current     # old current <-- newLink\n        current.next = newLink # old current --> newLink\n        return True # found it, did insertion\n\n    def deleteKey(self,key): # delete item w/ given key\n        # (assumes non-empty list)\n        current = self.first # start at beginningDoubly Linked Lists\n        while(current.dData != key):\n            current = current.next\n            if(current == None):\n                return None\n        if(current==self.first):\n            self.first = current.next\n        else: \n            # until match is found, move to next link didnt find it found it first item?  first --> old next\n            # not first  old previous --> old next\n            current.previous.next = current.next\n        if(current==self.last):\n            self.last = current.previous\n        else:\n            # last item?  old previous <-- last  not last  old previous <-- old next \n            current.next.previous = current.previous\n        return current # return value\n\n    def displayForward(self):\n        print 'List (first-->last): ',\n        current = self.first   # start at beginning\n        while(current != None):    # until end of list,\n            current.displayLink()# display data\n            current = current.next # move to next link\n        print ''\n\n    def displayBackward(self):\n        print  'List (last-->first): ' ,\n        current = self.last # start at end\n        while(current != None): # until start of list,\n            current.displayLink() # display data\n            current = current.previous # move to previous link\n        print ''\n\n# make a new list\ntheList = DoublyLinkedList()\ntheList.insertFirst(22) # insert at front\ntheList.insertFirst(44) \ntheList.insertFirst(66) \ntheList.insertLast(11) # insert at rear\ntheList.insertLast(33) \ntheList.insertLast(55) \ntheList.displayForward() # display list forward\ntheList.displayBackward() # display list backward\ntheList.deleteFirst() # delete first item\ntheList.deleteLast() # delete last item\ntheList.deleteKey(11) # delete item with key 11\ntheList.displayForward() # display list forward\ntheList.insertAfter(22, 77) # insert 77 after 22\ntheList.insertAfter(33, 88) # insert 88 after 33\ntheList.displayForward() # display list forward",
+     "language": "python",
+     "metadata": {},
+     "outputs": [
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "List (first-->last):  66 44 22 11 33 55 \nList (last-->first):  55 33 11 22 44 66 \nList (first-->last):  44 22 33 \nList (first-->last):  44 22 77 33 88 \n"
+      }
+     ],
+     "prompt_number": 8
+    },
+    {
+     "cell_type": "heading",
+     "level": 3,
+     "metadata": {},
+     "source": "Example 5.9  Page No : 235"
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": "'''\nexample 5.9\ndemonstrates iterators on a linked listListIterator\n'''\nclass Link:\n    def __init__(self,d): # constructor\n        self.dData = d\n        self.next = None\n\n    def displayLink(self): # display this link\n        print self.dData ,\n\nclass LinkList:\n    def __init__(self):\n        self.first = None\n\n    def isEmpty(self): # true if list is empty\n        return (self.first==None)\n\n    # insert at start of list\n    def insertFirst(self,i,  dd):\n        # make new link\n        newLink = Link(i, dd)\n        newLink.next = self.first\n        # newLink --> old first\n        self.first = newLink\n\n    def deleteFirst(self):\n        temp = self.first\n        self.first = self.first.next\n        return temp\n    \n    def displayList(self):\n        print 'List (first-->last): ' ,\n        current = self.first\n        while(current != None):\n            current.displayLink()\n            current = current.next\n        print ''\n\n    def find(self,key): # find link with given key\n        current = self.first #start at first\n        while(current.iData != key): # while no match,\n            if(current.next == None): # if end of list,\n                return None # didnt find it\n            else:\n                current = current.next # go to next link\n        return current\n    \n    def delete(self,key): # delete link with given key\n        current = self.first \n        previous = self.first\n        while(current.iData != key):\n            if(current.next == None):\n                return None # didnt find it\n            else:\n                previous = current\n                current = current.next\n        if(current == self.first): # if first link,\n            self.first = self.first.next\n        else:\n            previous.next = current.next\n        return current\n\n    def getFirst(self): # get value of first\n        return self.first\n\n    def setFirst(self,f): # set first to new link\n        self.first = f\n\n    def getIterator(self): # return iterator\n        return ListIterator(self) # initialized with\n\nclass ListIterator:\n    def __init__(self,l): # constructor\n        self.ourList = l\n        self.reset()\n        self.current = None\n        self.previous = None\n\n    def reset(self): # start at first\n        self.current = self.ourList.getFirst()\n        self.previous = None\n\n    def atEnd(self): # true if last link\n        return (self.current.next==None) \n    \n    def nextLink(self): # go to next link\n        self.previous = self.current\n        self.current = self.current.next\n\n    def getCurrent(self): # get current link\n        return self.current \n\n    def insertAfter(self,dd): # insert after\n        # current link\n        newLink = Link(dd)\n        if( self.ourList.isEmpty() ):# empty list\n            self.ourList.setFirst(newLink)\n            self.current = newLink\n        else: # not empty\n            newLink.next = self.current.next\n            self.current.next = newLink\n            self.nextLink() # point to new link\n\n    def insertBefore(self,dd): # insert before\n        # current link\n        newLink = Link(dd)\n        if(self.previous == None): # beginning of list (or empty list)\n            newLink.next = self.ourList.getFirst()\n            self.ourList.setFirst(newLink)\n            self.reset()\n        else: # not beginning\n            newLink.next = self.previous.next\n            self.previous.next = newLink\n            self.current = newLink\n\n    def deleteCurrent(self): # delete item at current\n        value = self.current.dData\n        if(self.previous == None): # beginning of list\n            self.ourList.setFirst(self.current.next)\n            self.reset()\n        else: # not beginning\n            self.previous.next = self.current.next\n            if( self.atEnd() ):\n                self.reset()\n            else:\n                current = current.next\n        return value\n\ntheList = LinkList() # new list\niter1 = theList.getIterator() # new iter\niter1.insertAfter(20)\niter1.insertAfter(40)\niter1.insertAfter(80)\niter1.insertBefore(60) # insert items\nwhile(True):\n    print 'Enter first letter of show, reset, ' , \n    print 'next, get, before, after, delete: ' ,\n    choice = raw_input()     # get users option\n    if choice == 's': # show list\n        if( not theList.isEmpty() ):\n            theList.displayList()\n        else:\n            print 'List is empty'\n    elif choice == 'r': # reset (to first)\n        iter1.reset()\n    elif choice == 'n': # advance to next item\n        if( not theList.isEmpty() and not iter1.atEnd() ):\n            iter1.nextLink()\n        else:\n            print \"Cant go to next link\"\n    elif choice=='g': # get current item\n        if( not theList.isEmpty() ):\n            value = iter1.getCurrent().dData\n            print \"Returned \" , value\n        else:\n            print \"List is empty\"\n    elif choice == 'b':  # insert before current\n        print \"Enter value to insert: \",\n        value = raw_input()\n        iter1.insertBefore(value)\n    elif choice=='a': # insert after current\n        print \"Enter value to insert: \",\n        value = raw_input()\n        iter1.insertAfter(value)\n    elif choice == 'd': # delete current item\n        if( not theList.isEmpty() ):\n            value = iter1.deleteCurrent()\n            print \"Deleted \" , value\n        else:\n            print \"Cant delete\"\n    else:\n        print \"Invalid entry\"\n        break",
+     "language": "python",
+     "metadata": {},
+     "outputs": [
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": " Enter first letter of show, reset,  next, get, before, after, delete: "
+      },
+      {
+       "name": "stdout",
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "s\n"
+      },
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": " List (first-->last):  20 40 60 80 \nEnter first letter of show, reset,  next, get, before, after, delete: "
+      },
+      {
+       "name": "stdout",
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "r\n"
+      },
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": " Enter first letter of show, reset,  next, get, before, after, delete: "
+      },
+      {
+       "name": "stdout",
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "n\n"
+      },
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": " Enter first letter of show, reset,  next, get, before, after, delete: "
+      },
+      {
+       "name": "stdout",
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "n\n"
+      },
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": " Enter first letter of show, reset,  next, get, before, after, delete: "
+      },
+      {
+       "name": "stdout",
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "g\n"
+      },
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": " Returned  60\nEnter first letter of show, reset,  next, get, before, after, delete: "
+      },
+      {
+       "name": "stdout",
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "b\n"
+      },
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": " Enter value to insert: "
+      },
+      {
+       "name": "stdout",
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "100\n"
+      },
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": " Enter first letter of show, reset,  next, get, before, after, delete: "
+      },
+      {
+       "name": "stdout",
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "a\n"
+      },
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": " Enter value to insert: "
+      },
+      {
+       "name": "stdout",
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "7\n"
+      },
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": " Enter first letter of show, reset,  next, get, before, after, delete: "
+      },
+      {
+       "name": "stdout",
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "s\n"
+      },
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": " List (first-->last):  20 40 100 7 60 80 \nEnter first letter of show, reset,  next, get, before, after, delete: "
+      },
+      {
+       "name": "stdout",
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": "\n"
+      },
+      {
+       "output_type": "stream",
+       "stream": "stdout",
+       "text": " Invalid entry\n"
+      }
+     ],
+     "prompt_number": 10
+    },
+    {
+     "cell_type": "code",
+     "collapsed": false,
+     "input": "",
+     "language": "python",
+     "metadata": {},
+     "outputs": []
+    }
+   ],
+   "metadata": {}
+  }
+ ]
+}
\ No newline at end of file