{
"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": {}
}
]
}