class Link:
def __init__(self,i,dd):
self.iData = i
self.dData = dd
self.next = None
def displayLink(self): # display ourself
print '{' , self.iData , ', ' , self.dData , '} ' ,
class LinkList:
def __init__(self):
self.first = None
def isEmpty(self): # true if list is empty
return (self.first==None)
# insert at start of list
def insertFirst(self,i, dd):
# make new link
newLink = Link(i, dd)
newLink.next = self.first
# newLink --> old first
self.first = newLink
def deleteFirst(self):
temp = self.first
self.first = self.first.next
return temp
def displayList(self):
print 'List (first-->last): ' ,
current = self.first
while(current != None):
current.displayLink()
current = current.next
print ''
theList = LinkList() # make new list
theList.insertFirst(22,2.99)
theList.insertFirst(44,4.99)
theList.insertFirst(66,6.99)
theList.insertFirst(88,8.99)
theList.displayList()
while( not theList.isEmpty() ): # until it's empty,
aLink = theList.deleteFirst() # delete link
print 'Deleted ' , # display it
aLink.displayLink()
print ''
theList.displayList()
class Link:
def __init__(self,i,dd):
self.iData = i
self.dData = dd
self.next = None
def displayLink(self): # display ourself
print '{' , self.iData , ', ' , self.dData , '} ' ,
class LinkList:
def __init__(self):
self.first = None
def isEmpty(self): # true if list is empty
return (self.first==None)
# insert at start of list
def insertFirst(self,i, dd):
# make new link
newLink = Link(i, dd)
newLink.next = self.first
# newLink --> old first
self.first = newLink
def deleteFirst(self):
temp = self.first
self.first = self.first.next
return temp
def displayList(self):
print 'List (first-->last): ' ,
current = self.first
while(current != None):
current.displayLink()
current = current.next
print ''
def find(self,key): # find link with given key
current = self.first #start at first
while(current.iData != key): # while no match,
if(current.next == None): # if end of list,
return None # didnt find it
else:
current = current.next # go to next link
return current
def delete(self,key): # delete link with given key
current = self.first
previous = self.first
while(current.iData != key):
if(current.next == None):
return None # didnt find it
else:
previous = current
current = current.next
if(current == self.first): # if first link,
self.first = self.first.next
else:
previous.next = current.next
return current
theList = LinkList() # make list
theList.insertFirst(22,2.99)
theList.insertFirst(44,4.99)
theList.insertFirst(66,6.99)
theList.insertFirst(88,8.99)
theList.displayList() # display list
f = theList.find(44) # find item
if( f != None):
print 'Found link with key ' , f.iData
else:
print "Can't find link"
d = theList.delete(66) # delete item
if( d != None ):
print "Deleted link with key " , d.iData
else:
print "Can't delete link"
theList.displayList()
class Link:
def __init__(self,d):
self.dData = d
self.next = None
def displayLink(self): # display ourself
print self.dData ,
class FirstLastList:
def __init__(self):
self.first = None
self.last = None
def isEmpty(self): # true if list is empty
return (self.first==None)
# insert at start of list
def insertFirst(self, dd):
# make new link
newLink = Link(dd)
if (self.isEmpty()):
self.last = newLink
newLink.next = self.first
# newLink --> old first
self.first = newLink
def deleteFirst(self):
temp = self.first
if self.first.next ==None:
self.last = None
self.first = self.first.next
return temp
def insertLast(self,dd): # insert at end of list
newLink = Link(dd) # make new link
if( self.isEmpty() ): # if empty list,
self.first = newLink # first --> newLink
else:
self.last.next = newLink # old last --> newLink
self.last = newLink # newLink <-- last
def displayList(self):
print 'List (first-->last): ' ,
current = self.first
while(current != None):
current.displayLink()
current = current.next
print ''
theList = FirstLastList()
theList.insertFirst(22)
theList.insertLast(11)
theList.insertFirst(44)
theList.insertLast(33)
theList.insertFirst(66)
theList.insertLast(55)
theList.displayList() # display the list
theList.deleteFirst()
theList.deleteFirst()
theList.displayList() # display again
class Link:
def __init__(self,dd):
self.dData = dd
self.next = None
def displayLink(self): # display ourself
print self.dData ,
class LinkList:
def __init__(self):
self.first = None
def isEmpty(self): # true if list is empty
return (self.first==None)
# insert at start of list
def insertFirst(self, dd):
# make new link
newLink = Link( dd)
newLink.next = self.first
# newLink --> old first
self.first = newLink
def deleteFirst(self):
temp = self.first
self.first = self.first.next
return temp
def displayList(self):
current = self.first
while(current != None):
current.displayLink()
current = current.next
print ''
class LinkStack:
def __init__(self):
self.theList = LinkList()
def push(self,j): # put item on top of stack
self.theList.insertFirst(j)
def pop(self): # take item from top of stack
return self.theList.deleteFirst()
def isEmpty(self):
return ( self.theList.isEmpty() )
def displayStack(self):
print 'Stack (top-->bottom): ' ,
self.theList.displayList()
theStack = LinkStack() # make stack
theStack.push(20)
theStack.push(40)
theStack.displayStack() # display stack
theStack.push(60) # push items
theStack.push(80)
theStack.displayStack() # display stack
theStack.pop()
theStack.pop()
theStack.displayStack() # display stack
class Link:
def __init__(self,d): # constructor
self.dData = d
self.next = None
def displayLink(self): # display this link
print self.dData ,
class FirstLastList:
def __init__(self):
self.first = None
self.last = None
def isEmpty(self): # true if list is empty
return (self.first==None)
# insert at start of list
def insertFirst(self, dd):
# make new link
newLink = Link(dd)
if (self.isEmpty()):
self.last = newLink
newLink.next = self.first
# newLink --> old first
self.first = newLink
def deleteFirst(self):
temp = self.first
if self.first.next ==None:
self.last = None
self.first = self.first.next
return temp
def insertLast(self,dd): # insert at end of list
newLink = Link(dd) # make new link
if( self.isEmpty() ): # if empty list,
self.first = newLink # first --> newLink
else:
self.last.next = newLink # old last --> newLink
self.last = newLink # newLink <-- last
def displayList(self):
print 'List (first-->last): ' ,
current = self.first
while(current != None):
current.displayLink()
current = current.next
print ''
class LinkQueue:
def __init__(self):
self.theList = FirstLastList() # make a 2-ended list
def isEmpty(self): # true if queue is empty
return self.theList.isEmpty()
def insert(self,j): # insert, rear of queue
self.theList.insertLast(j)
def remove(self): # remove, front of queue
return self.theList.deleteFirst()
def displayQueue(self):
print 'Queue (front-->rear): ' ,
self.theList.displayList()
theQueue = LinkQueue()
theQueue.insert(20) # insert items
theQueue.insert(40)
theQueue.displayQueue() # display queue
theQueue.insert(60) # insert items
theQueue.insert(80)
theQueue.displayQueue() # display queue
theQueue.remove() # remove items
theQueue.remove()
theQueue.displayQueue() # display queue
class Link:
def __init__(self,d): # constructor
self.dData = d
self.next = None
def displayLink(self): # display this link
print self.dData ,
class SortedList:
def __init__(self):
self.first = None
def isEmpty(self): # true if no links
return (self.first==None)
def insert(self,key): # insert, in order
newLink = Link(key) # make new link
previous = None
current = self.first # until end of list,
while(current != None and key > current.dData):
previous = current
current = current.next
if(previous==None): # at beginning of list
self.first = newLink
else: # not at beginning
previous.next = newLink
newLink.next = current
def remove(self): # return & delete first link
temp = self.first # save first
self.first = self.first.next # delete first
return temp
def displayList(self):
print "List (first-->last): " ,
current = self.first # start at beginning of listSorted Lists
while(current != None): # until end of list,
current.displayLink()
current = current.next # move to next link
print ''
# create new list
theSortedList = SortedList()
theSortedList.insert(20) # insert 2 items
theSortedList.insert(40)
theSortedList.displayList() # display list
theSortedList.insert(10)
theSortedList.insert(30)
theSortedList.insert(50) # insert 3 more items
theSortedList.displayList() # display list
theSortedList.remove() # remove an item
theSortedList.displayList() # display list
class Link:
def __init__(self,d): # constructor
self.dData = d
self.next = None
def displayLink(self): # display this link
print self.dData ,
class SortedList:
def __init__(self,linkArr = None):
if linkArr == None:
self.first = None
else:
self.first = None # initialize list
for j in range(len(linkArr)):
self.insert( linkArr[j] )
def isEmpty(self): # true if no links
return (self.first==None)
def insert(self,k): # insert, in order
previous = None
current = self.first # until end of list,
while(current != None and k.dData > current.dData):
previous = current
current = current.next
if(previous==None): # at beginning of list
self.first = k
else: # not at beginning
previous.next = k
k.next = current
def remove(self): # return & delete first link
temp = self.first # save first
self.first = self.first.next # delete first
return temp
def displayList(self):
print "List (first-->last): " ,
current = self.first # start at beginning of listSorted Lists
while(current != None): # until end of list,
current.displayLink()
current = current.next # move to next link
print ''
size = 10 # create array of links
linkArray = []
import random
for j in range(size): # fill array with links
# random number
n = int(random.random()*99)
newLink = Link(n) # make link
linkArray.append(newLink) # put in array
# display array contents
print 'Unsorted array: ',
for j in range(size):
print linkArray[j].dData ,
print ''
# create new list
# initialized with array
theSortedList = SortedList(linkArray)
linkArray = []
for j in range(size): # links from list to array
linkArray.append( theSortedList.remove())
# display array contents
print 'Sorted Array: ',
for j in range(size):
print linkArray[j].dData ,
class Link:
def __init__(self,d): # constructor
self.dData = d
self.next = None
self.previous = None
def displayLink(self): # display this link
print self.dData ,
class DoublyLinkedList:
def __init__(self):
self.first = None # no items on list yet
self.last = None
def isEmpty(self): # true if no links
return self.first==None
def insertFirst(self,dd): # insert at front of list
newLink = Link(dd) # make new link
if( self.isEmpty() ): # if empty list,
self.last = newLink # newLink <-- last
else:
self.first.previous = newLink # newLink <-- old first
newLink.next = self.first # newLink --> old first
self.first = newLink # first --> newLink
def insertLast(self,dd): # insert at end of list
newLink = Link(dd) # make new link
if( self.isEmpty() ) : # if empty list,
self.first = newLink # first --> newLink
else:
self.last.next = newLink # old last --> newLink
newLink.previous = self.last # old last <-- newLink
self.last = newLink # newLink <-- last
def deleteFirst(self): # delete first link
# (assumes non-empty list)
temp = self.first
if(self.first.next == None): # if only one item
self.last = None # None <-- last
else:
self.first.next.previous = None # None <-- old next
self.first = self.first.next # first --> old next
return temp
def deleteLast(self): # delete last link
# (assumes non-empty list)
temp = self.last
if(self.first.next == None): # if only one item
self.first = None # first --> None
else:
self.last.previous.next = None # old previous --> None
self.last = self.last.previous # old previous <-- last
return temp
# insert dd just after key
def insertAfter(self,key,dd):
# (assumes non-empty list)
current = self.first # start at beginning
while(current.dData != key): # until match is found,
current = current.next # move to next link
if(current == None):
return False # didnt find it
newLink = Link(dd) # make new link
if(current==self.last): # if last link,
newLink.next = None # newLink --> None
self.last = newLink# newLink <-- last
else: # not last link,
newLink.next = current.next # newLink --> old next # newLink <-- old next
current.next.previous = newLink
newLink.previous = current # old current <-- newLink
current.next = newLink # old current --> newLink
return True # found it, did insertion
def deleteKey(self,key): # delete item w/ given key
# (assumes non-empty list)
current = self.first # start at beginningDoubly Linked Lists
while(current.dData != key):
current = current.next
if(current == None):
return None
if(current==self.first):
self.first = current.next
else:
# until match is found, move to next link didnt find it found it first item? first --> old next
# not first old previous --> old next
current.previous.next = current.next
if(current==self.last):
self.last = current.previous
else:
# last item? old previous <-- last not last old previous <-- old next
current.next.previous = current.previous
return current # return value
def displayForward(self):
print 'List (first-->last): ',
current = self.first # start at beginning
while(current != None): # until end of list,
current.displayLink()# display data
current = current.next # move to next link
print ''
def displayBackward(self):
print 'List (last-->first): ' ,
current = self.last # start at end
while(current != None): # until start of list,
current.displayLink() # display data
current = current.previous # move to previous link
print ''
# make a new list
theList = DoublyLinkedList()
theList.insertFirst(22) # insert at front
theList.insertFirst(44)
theList.insertFirst(66)
theList.insertLast(11) # insert at rear
theList.insertLast(33)
theList.insertLast(55)
theList.displayForward() # display list forward
theList.displayBackward() # display list backward
theList.deleteFirst() # delete first item
theList.deleteLast() # delete last item
theList.deleteKey(11) # delete item with key 11
theList.displayForward() # display list forward
theList.insertAfter(22, 77) # insert 77 after 22
theList.insertAfter(33, 88) # insert 88 after 33
theList.displayForward() # display list forward
class Link:
def __init__(self,d): # constructor
self.dData = d
self.next = None
def displayLink(self): # display this link
print self.dData ,
class LinkList:
def __init__(self):
self.first = None
def isEmpty(self): # true if list is empty
return (self.first==None)
# insert at start of list
def insertFirst(self,i, dd):
# make new link
newLink = Link(i, dd)
newLink.next = self.first
# newLink --> old first
self.first = newLink
def deleteFirst(self):
temp = self.first
self.first = self.first.next
return temp
def displayList(self):
print 'List (first-->last): ' ,
current = self.first
while(current != None):
current.displayLink()
current = current.next
print ''
def find(self,key): # find link with given key
current = self.first #start at first
while(current.iData != key): # while no match,
if(current.next == None): # if end of list,
return None # didnt find it
else:
current = current.next # go to next link
return current
def delete(self,key): # delete link with given key
current = self.first
previous = self.first
while(current.iData != key):
if(current.next == None):
return None # didnt find it
else:
previous = current
current = current.next
if(current == self.first): # if first link,
self.first = self.first.next
else:
previous.next = current.next
return current
def getFirst(self): # get value of first
return self.first
def setFirst(self,f): # set first to new link
self.first = f
def getIterator(self): # return iterator
return ListIterator(self) # initialized with
class ListIterator:
def __init__(self,l): # constructor
self.ourList = l
self.reset()
self.current = None
self.previous = None
def reset(self): # start at first
self.current = self.ourList.getFirst()
self.previous = None
def atEnd(self): # true if last link
return (self.current.next==None)
def nextLink(self): # go to next link
self.previous = self.current
self.current = self.current.next
def getCurrent(self): # get current link
return self.current
def insertAfter(self,dd): # insert after
# current link
newLink = Link(dd)
if( self.ourList.isEmpty() ):# empty list
self.ourList.setFirst(newLink)
self.current = newLink
else: # not empty
newLink.next = self.current.next
self.current.next = newLink
self.nextLink() # point to new link
def insertBefore(self,dd): # insert before
# current link
newLink = Link(dd)
if(self.previous == None): # beginning of list (or empty list)
newLink.next = self.ourList.getFirst()
self.ourList.setFirst(newLink)
self.reset()
else: # not beginning
newLink.next = self.previous.next
self.previous.next = newLink
self.current = newLink
def deleteCurrent(self): # delete item at current
value = self.current.dData
if(self.previous == None): # beginning of list
self.ourList.setFirst(self.current.next)
self.reset()
else: # not beginning
self.previous.next = self.current.next
if( self.atEnd() ):
self.reset()
else:
current = current.next
return value
theList = LinkList() # new list
iter1 = theList.getIterator() # new iter
iter1.insertAfter(20)
iter1.insertAfter(40)
iter1.insertAfter(80)
iter1.insertBefore(60) # insert items
while(True):
print 'Enter first letter of show, reset, ' ,
print 'next, get, before, after, delete: ' ,
choice = raw_input() # get users option
if choice == 's': # show list
if( not theList.isEmpty() ):
theList.displayList()
else:
print 'List is empty'
elif choice == 'r': # reset (to first)
iter1.reset()
elif choice == 'n': # advance to next item
if( not theList.isEmpty() and not iter1.atEnd() ):
iter1.nextLink()
else:
print "Cant go to next link"
elif choice=='g': # get current item
if( not theList.isEmpty() ):
value = iter1.getCurrent().dData
print "Returned " , value
else:
print "List is empty"
elif choice == 'b': # insert before current
print "Enter value to insert: ",
value = raw_input()
iter1.insertBefore(value)
elif choice=='a': # insert after current
print "Enter value to insert: ",
value = raw_input()
iter1.insertAfter(value)
elif choice == 'd': # delete current item
if( not theList.isEmpty() ):
value = iter1.deleteCurrent()
print "Deleted " , value
else:
print "Cant delete"
else:
print "Invalid entry"
break