{ "metadata": { "name": "", "signature": "sha256:78657e06ea6117b67568778cbd053fe193ae0df563d1cdc0a431335e7e291192" }, "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": [ " \n", "class 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", "\n", "class 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", "theList = LinkList() # make new list\n", "theList.insertFirst(22,2.99)\n", "theList.insertFirst(44,4.99)\n", "theList.insertFirst(66,6.99)\n", "theList.insertFirst(88,8.99)\n", "theList.displayList()\n", "\n", "while( not theList.isEmpty() ): # until it's empty,\n", " aLink = theList.deleteFirst() # delete link\n", " print 'Deleted ' , # display it\n", " aLink.displayLink()\n", " print ''\n", " \n", "theList.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 } \n", "Deleted { 88 , 8.99 } \n", "Deleted { 66 , 6.99 } \n", "Deleted { 44 , 4.99 } \n", "Deleted { 22 , 2.99 } \n", "List (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": [ " \n", "class 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", "\n", "class 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", "\n", "theList = LinkList() # make list\n", "theList.insertFirst(22,2.99)\n", "theList.insertFirst(44,4.99)\n", "theList.insertFirst(66,6.99)\n", "theList.insertFirst(88,8.99)\n", "theList.displayList() # display list\n", "f = theList.find(44) # find item\n", "if( f != None):\n", " print 'Found link with key ' , f.iData\n", "else:\n", " print \"Can't find link\"\n", "d = theList.delete(66) # delete item\n", "if( d != None ):\n", " print \"Deleted link with key \" , d.iData\n", "else:\n", " print \"Can't delete link\"\n", "\n", "theList.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 } \n", "Found link with key 44\n", "Deleted link with key 66\n", "List (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": [ " \n", "class 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", "\n", "class 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", "\n", "theList = FirstLastList()\n", "theList.insertFirst(22) \n", "theList.insertLast(11)\n", "theList.insertFirst(44) \n", "theList.insertLast(33) \n", "theList.insertFirst(66) \n", "theList.insertLast(55) \n", "theList.displayList() # display the list\n", "theList.deleteFirst() \n", "theList.deleteFirst() \n", "theList.displayList() # display again" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "List (first-->last): 66 44 22 11 33 55 \n", "List (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": [ " \n", "class 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", "\n", "class 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", "\n", "class 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", "\n", "theStack = LinkStack() # make stack\n", "theStack.push(20)\n", "theStack.push(40) \n", "theStack.displayStack() # display stack\n", "\n", "theStack.push(60) # push items\n", "theStack.push(80) \n", "theStack.displayStack() # display stack\n", "theStack.pop() \n", "theStack.pop() \n", "theStack.displayStack() # display stack" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Stack (top-->bottom): 40 20 \n", "Stack (top-->bottom): 80 60 40 20 \n", "Stack (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": [ " \n", "class 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", "\n", "class 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", "\n", "class 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", "\n", "theQueue = LinkQueue()\n", "theQueue.insert(20) # insert items\n", "theQueue.insert(40) \n", "theQueue.displayQueue() # display queue\n", "theQueue.insert(60) # insert items\n", "theQueue.insert(80) \n", "theQueue.displayQueue() # display queue\n", "theQueue.remove() # remove items\n", "theQueue.remove() \n", "theQueue.displayQueue() # display queue" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Queue (front-->rear): List (first-->last): 20 40 \n", "Queue (front-->rear): List (first-->last): 20 40 60 80 \n", "Queue (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": [ " \n", "\n", "class 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", "\n", "class 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\n", "theSortedList = SortedList()\n", "theSortedList.insert(20) # insert 2 items\n", "theSortedList.insert(40)\n", "theSortedList.displayList() # display list\n", "theSortedList.insert(10)\n", "theSortedList.insert(30)\n", "theSortedList.insert(50) # insert 3 more items\n", "theSortedList.displayList() # display list\n", "theSortedList.remove() # remove an item\n", "theSortedList.displayList() # display list" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "List (first-->last): 20 40 \n", "List (first-->last): 10 20 30 40 50 \n", "List (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": [ " \n", "class 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", "\n", "class 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", "\n", "size = 10 # create array of links\n", "linkArray = []\n", "import random\n", "for 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\n", "print 'Unsorted array: ',\n", "for j in range(size):\n", " print linkArray[j].dData , \n", "print ''\n", "\n", "# create new list\n", "# initialized with array\n", "theSortedList = SortedList(linkArray)\n", "linkArray = []\n", "for j in range(size): # links from list to array\n", " linkArray.append( theSortedList.remove())\n", "# display array contents\n", "print 'Sorted Array: ',\n", "for 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 \n", "Sorted 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": [ " \n", "class 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", "\n", "class 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\n", "theList = DoublyLinkedList()\n", "theList.insertFirst(22) # insert at front\n", "theList.insertFirst(44) \n", "theList.insertFirst(66) \n", "theList.insertLast(11) # insert at rear\n", "theList.insertLast(33) \n", "theList.insertLast(55) \n", "theList.displayForward() # display list forward\n", "theList.displayBackward() # display list backward\n", "theList.deleteFirst() # delete first item\n", "theList.deleteLast() # delete last item\n", "theList.deleteKey(11) # delete item with key 11\n", "theList.displayForward() # display list forward\n", "theList.insertAfter(22, 77) # insert 77 after 22\n", "theList.insertAfter(33, 88) # insert 88 after 33\n", "theList.displayForward() # display list forward" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "List (first-->last): 66 44 22 11 33 55 \n", "List (last-->first): 55 33 11 22 44 66 \n", "List (first-->last): 44 22 33 \n", "List (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": [ " \n", "class 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", "\n", "class 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", "\n", "class 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", "\n", "theList = LinkList() # new list\n", "iter1 = theList.getIterator() # new iter\n", "iter1.insertAfter(20)\n", "iter1.insertAfter(40)\n", "iter1.insertAfter(80)\n", "iter1.insertBefore(60) # insert items\n", "while(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 \n", "Enter 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\n", "Enter 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 \n", "Enter 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": {} } ] }