summaryrefslogtreecommitdiff
path: root/Data_Structures_and_Algorithms_in_Java/ch5.ipynb
diff options
context:
space:
mode:
Diffstat (limited to 'Data_Structures_and_Algorithms_in_Java/ch5.ipynb')
-rw-r--r--Data_Structures_and_Algorithms_in_Java/ch5.ipynb981
1 files changed, 929 insertions, 52 deletions
diff --git a/Data_Structures_and_Algorithms_in_Java/ch5.ipynb b/Data_Structures_and_Algorithms_in_Java/ch5.ipynb
index 6ac7b766..ecd02576 100644
--- a/Data_Structures_and_Algorithms_in_Java/ch5.ipynb
+++ b/Data_Structures_and_Algorithms_in_Java/ch5.ipynb
@@ -1,6 +1,7 @@
{
"metadata": {
- "name": "ch5"
+ "name": "",
+ "signature": "sha256:78657e06ea6117b67568778cbd053fe193ae0df563d1cdc0a431335e7e291192"
},
"nbformat": 3,
"nbformat_minor": 0,
@@ -11,25 +12,89 @@
"cell_type": "heading",
"level": 1,
"metadata": {},
- "source": "Chapter 5 : Linked Lists"
+ "source": [
+ "Chapter 5 : Linked Lists"
+ ]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
- "source": "Example 5.1 Page No : 190"
+ "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()",
+ "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 } \nDeleted { 88 , 8.99 } \nDeleted { 66 , 6.99 } \nDeleted { 44 , 4.99 } \nDeleted { 22 , 2.99 } \nList (first-->last): \n"
+ "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
@@ -38,19 +103,108 @@
"cell_type": "heading",
"level": 3,
"metadata": {},
- "source": "Example 5.2 Page No : 193"
+ "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()",
+ "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 } \nFound link with key 44\nDeleted link with key 66\nList (first-->last): { 88 , 8.99 } { 44 , 4.99 } { 22 , 2.99 } \n"
+ "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
@@ -59,19 +213,87 @@
"cell_type": "heading",
"level": 3,
"metadata": {},
- "source": "Example 5.3 Page NO :198"
+ "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",
+ "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 \nList (first-->last): 22 11 33 55 \n"
+ "text": [
+ "List (first-->last): 66 44 22 11 33 55 \n",
+ "List (first-->last): 22 11 33 55 \n"
+ ]
}
],
"prompt_number": 3
@@ -80,19 +302,90 @@
"cell_type": "heading",
"level": 3,
"metadata": {},
- "source": "Example 5.4 Page No : 204"
+ "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",
+ "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 \nStack (top-->bottom): 80 60 40 20 \nStack (top-->bottom): 40 20 \n"
+ "text": [
+ "Stack (top-->bottom): 40 20 \n",
+ "Stack (top-->bottom): 80 60 40 20 \n",
+ "Stack (top-->bottom): 40 20 \n"
+ ]
}
],
"prompt_number": 4
@@ -101,19 +394,104 @@
"cell_type": "heading",
"level": 3,
"metadata": {},
- "source": "Example 5.5 Page No : 207"
+ "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",
+ "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 \nQueue (front-->rear): List (first-->last): 20 40 60 80 \nQueue (front-->rear): List (first-->last): 60 80 \n"
+ "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
@@ -122,19 +500,80 @@
"cell_type": "heading",
"level": 3,
"metadata": {},
- "source": "Example 5.6 Page No : 215"
+ "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",
+ "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 \nList (first-->last): 10 20 30 40 50 \nList (first-->last): 20 30 40 50 \n"
+ "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
@@ -143,19 +582,97 @@
"cell_type": "heading",
"level": 3,
"metadata": {},
- "source": "Example 5.7 Page No : 218"
+ "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 ,",
+ "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 \nSorted Array: 12 28 30 63 65 73 85 87 91 91\n"
+ "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
@@ -164,19 +681,155 @@
"cell_type": "heading",
"level": 3,
"metadata": {},
- "source": "Example 5.8 Page no : 226"
+ "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",
+ "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 \nList (last-->first): 55 33 11 22 44 66 \nList (first-->last): 44 22 33 \nList (first-->last): 44 22 77 33 88 \n"
+ "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
@@ -185,140 +838,364 @@
"cell_type": "heading",
"level": 3,
"metadata": {},
- "source": "Example 5.9 Page No : 235"
+ "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",
+ "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: "
+ "text": [
+ " Enter first letter of show, reset, next, get, before, after, delete: "
+ ]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
- "text": "s\n"
+ "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: "
+ "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"
+ "text": [
+ "r\n"
+ ]
},
{
"output_type": "stream",
"stream": "stdout",
- "text": " Enter first letter of show, reset, next, get, before, after, delete: "
+ "text": [
+ " Enter first letter of show, reset, next, get, before, after, delete: "
+ ]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
- "text": "n\n"
+ "text": [
+ "n\n"
+ ]
},
{
"output_type": "stream",
"stream": "stdout",
- "text": " Enter first letter of show, reset, next, get, before, after, delete: "
+ "text": [
+ " Enter first letter of show, reset, next, get, before, after, delete: "
+ ]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
- "text": "n\n"
+ "text": [
+ "n\n"
+ ]
},
{
"output_type": "stream",
"stream": "stdout",
- "text": " Enter first letter of show, reset, next, get, before, after, delete: "
+ "text": [
+ " Enter first letter of show, reset, next, get, before, after, delete: "
+ ]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
- "text": "g\n"
+ "text": [
+ "g\n"
+ ]
},
{
"output_type": "stream",
"stream": "stdout",
- "text": " Returned 60\nEnter first letter of show, reset, next, get, before, after, delete: "
+ "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"
+ "text": [
+ "b\n"
+ ]
},
{
"output_type": "stream",
"stream": "stdout",
- "text": " Enter value to insert: "
+ "text": [
+ " Enter value to insert: "
+ ]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
- "text": "100\n"
+ "text": [
+ "100\n"
+ ]
},
{
"output_type": "stream",
"stream": "stdout",
- "text": " Enter first letter of show, reset, next, get, before, after, delete: "
+ "text": [
+ " Enter first letter of show, reset, next, get, before, after, delete: "
+ ]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
- "text": "a\n"
+ "text": [
+ "a\n"
+ ]
},
{
"output_type": "stream",
"stream": "stdout",
- "text": " Enter value to insert: "
+ "text": [
+ " Enter value to insert: "
+ ]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
- "text": "7\n"
+ "text": [
+ "7\n"
+ ]
},
{
"output_type": "stream",
"stream": "stdout",
- "text": " Enter first letter of show, reset, next, get, before, after, delete: "
+ "text": [
+ " Enter first letter of show, reset, next, get, before, after, delete: "
+ ]
},
{
"name": "stdout",
"output_type": "stream",
"stream": "stdout",
- "text": "s\n"
+ "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: "
+ "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"
+ "text": [
+ "\n"
+ ]
},
{
"output_type": "stream",
"stream": "stdout",
- "text": " Invalid entry\n"
+ "text": [
+ " Invalid entry\n"
+ ]
}
],
"prompt_number": 10
@@ -326,7 +1203,7 @@
{
"cell_type": "code",
"collapsed": false,
- "input": "",
+ "input": [],
"language": "python",
"metadata": {},
"outputs": []
generated by cgit (git 2.34.1) at 2025-05-24 00:27:45 +0000