def insert(key): #insert, in order
pNewLink = Link(key) #make new link
pPrevious = None #start at first
pCurrent = pFirst
#until end of list,
while pCurrent and key > pCurrent.dData: #or key > current,
pPrevious = pCurrent
pCurrent = pCurrent.pNext #got to next item
if not pPrevious: #at beginning of list
pFirst = pNewLink #first --> newlink
else: #not at begining
pPrevious.pNext = pNewLink #old prev --> newLink
pNewLink.pNext = pCurrent #newLink --> old current
#end insert()
#demonstrates sorted list
class Link:
def __init__(self, dd): #special method to create objects
#with instances customized to a specific initial state
self.dData = dd #data item
self.pNext = None #next link in list
def displayLink(self): #display this link
print self.dData,
#end class Link
class SortedList:
def __init__(self): #special method to create objects
#with instances customized to a specific initial state
#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._pFirst = None #first link
def __del__(self): #destructor (deletes list)
self.__init__()
def isEmpty(self): #true if no links
return self._pFirst == None
def insert(self, key): #insert, in order
pNewLink = Link(key) #make new link
pPrevious = None #start at first
pCurrent = self._pFirst
#until end of list,
while pCurrent and key > pCurrent.dData: #or key > current,
pPrevious = pCurrent
pCurrent = pCurrent.pNext #got to next item
if not pPrevious: #at beginning of list
self._pFirst = pNewLink #first --> newlink
else: #not at begining
pPrevious.pNext = pNewLink #old prev --> newLink
pNewLink.pNext = pCurrent #newLink --> old current
#end insert()
def remove(self): #remove first link
#(assumes non-empty list)
pTemp = self._pFirst #save first
self._pFirst = self._pFirst.pNext #new first-->next
del pTemp #delete old first link
def displayList(self):
print
print 'List (first-->last):',
pCurrent = self._pFirst #start at beginning of list
while pCurrent: #until end of list,
pCurrent.displayLink() #print data
pCurrent = pCurrent.pNext #move to next link
#end class SortedList
theSortedList = SortedList() #create new list
theSortedList.insert(20) #insert 2 items
theSortedList.insert(40)
theSortedList.displayList() #display list (20, 40)
theSortedList.insert(10) #insert 3 more items
theSortedList.insert(30)
theSortedList.insert(50)
theSortedList.displayList() #display list
# (10, 20, 30, 40, 50)
theSortedList.remove() #remove smallest item
theSortedList.displayList() #display list (20, 30, 40, 50)
#end
#demonstrates sorted list used for sorting
from pylab import array
from random import randrange #for random numbers
class Link:
def __init__(self, dd): #special method to create objects
#with instances customized to a specific initial state
self.dData = dd #data item
self.pNext = None #next link in list
class SortedList:
def __init__(self, linkArr, length): #special method to create objects
#with instances customized to a specific initial state
#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._pFirst = None #first item on list
for j in xrange(length): #copy array
self.insert(linkArr[j]) #to list
def insert(self, pArg): #insert (in order)
pPrevious = None #start at first
pCurrent = self._pFirst
#until end of list,
while pCurrent and pArg.dData > pCurrent.dData: #or key > current,
pPrevious = pCurrent
pCurrent = pCurrent.pNext #go to next item
if not pPrevious: #at beginning of list
self._pFirst = pArg #first --> k
else: #not at begining
pPrevious.pNext = pArg #old prev --> k
pArg.pNext = pCurrent #k --> old current
#end insert()
def remove(self): #return & delete first link
#(assumes non-empty list)
pTemp = self._pFirst #save first
self._pFirst = self._pFirst.pNext #delete first
return pTemp #return value
#end class SortedList
size = 10#array size
linkArray = array([None] * 10) #array for links
for j in xrange(size): #fill with links
n = randrange(0, 100) #random number (0 to 99)
pNewLink = Link(n) #make link
linkArray[j] = pNewLink #put link in array
print 'Unsorted array:', #display array contents
for j in linkArray:
print j.dData,
theSortedList = SortedList(linkArray, size) #create new list
for j in xrange(size): #links from list to array
linkArray[j] = theSortedList.remove()
print
print 'Sorted Array:', #display array contents
for j in linkArray:
print j.dData,
del linkArray #delete links
def insertFirst(dd): #insert at front of list
pNewLink = Link(dd) #make new link
if isEmpty(): #if empty list,
pLast = pNewLink #newLink <-- last
else:
pFirst.pPrevious = pNewLink #newLink <-- old first
pNewLink.pNext = pFirst #newLink --> old first
pFirst = pNewLink #first --> newLink
#demonstrates doubly-linked list
class Link:
def __init__(self, dd): #special method to create objects
#with instances customized to a specific initial state
self.dData = dd#data item
self.pNext = None #next link in list
self.pPrevious = None #previous link in list
def displayLink(self): #display this link
print self.dData,
class DoublyLinkedList:
def __init__(self): #special method to create objects
#with instances customized to a specific initial state
#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
self._pFirst = None #pointer to first item
self._pLast = None #pointer to last item
def __del__(self): #destructor (deletes list)
self.__init__()
def isEmpty(self): #true if no links
return self._pFirst == None
def insertFirst(self, dd): #insert at front of list
pNewLink = Link(dd) #make new link
if self.isEmpty(): #if empty list,
self._pLast = pNewLink #newLink <-- last
else:
self._pFirst.pPrevious = pNewLink #newLink <-- old first
pNewLink.pNext = self._pFirst #newLink --> old first
self._pFirst = pNewLink #first --> newLink
def insertLast(self, dd): #insert at end of list
pNewLink = Link(dd) #make new link
if self.isEmpty(): #if empty list,
self._pFirst = pNewLink #first --> newLink
else:
self._pLast.pNext = pNewLink #old last --> newLink
pNewLink.pPrevious = self._pLast #old last <-- newLink
self._pLast = pNewLink #newLink <-- last
def removeFirst(self): #remove first link
pTemp = self._pFirst #(assumes non-empty list)
if not self._pFirst.pNext: #if only one item
self._pLast = None#none <-- last
else:
self._pFirst.pNext.pPrevious = None#none <-- old next
self._pFirst = self._pFirst.pNext #first --> old next
del pTemp #delete old first
def removeLast(self): #remove last link
pTemp = self._pLast #assumes non-empty list
if not self._pFirst.pNext: #if only one item
self._pFirst = None#first --> none
else:
self._pLast.pPrevious.pNext = None#old previous --> none
self._pLast = self._pLast.pPrevious #old previous <-- last
del pTemp #delete old last
#insert dd just after key
def insertAfter(self, key, dd):
#(assumes non-empty list)
pCurrent = self._pFirst #start at beginning
while pCurrent.dData != key: #until match is found,
pCurrent = pCurrent.pNext #move to next link
if not pCurrent:
return False #didn't find it
pNewLink = Link(dd) #make new link
if pCurrent == self._pLast: #if last link,
pNewLink.pNext = None#newLink --> none
self._pLast = pNewLink #newLink <-- last
else: #not last link,
#newLink --> old next
pNewLink.pNext = pCurrent.pNext
#newLink <-- old next
pCurrent.pNext.pPrevious = pNewLink
pNewLink.pPrevious = pCurrent #old current <-- newLink
pCurrent.pNext = pNewLink #old current --> newLink
return True#found it, did insertion
def removeKey(self, key): #remove item w/ givem key
#(assumes nn-empty list)
pCurrent = self._pFirst #start at beginning
while pCurrent.dData != key: #until match is found,
pCurrent = pCurrent.pNext #move to next link
if not pCurrent:
return False #didn't find it
if pCurrent == self._pFirst: #found it; first item?
self._pFirst = pCurrent.pNext #first --> old next
else: #not first
#old previous --> old next
pCurrent.pPrevious.pNext = pCurrent.pNext
if pCurrent == self._pLast: #last item?
self._pLast = pCurrent.pPrevious #old previous <-- last
else: #not last
#old previous <-- old next
pCurrent.pNext.pPrevious = pCurrent.pPrevious
del pCurrent #delete item
return True#successful deletion
def displayForward(self):
print 'List (first-->last):',
pCurrent = self._pFirst #start at beginning
while pCurrent: #until end of list,
pCurrent.displayLink() #display data
pCurrent = pCurrent.pNext #move to next link
print
def displayBackward(self):
print 'List (first-->last):',
pCurrent = self._pLast #start at end
while pCurrent: #until start of list,
pCurrent.displayLink() #display data
pCurrent = pCurrent.pPrevious #go to previous link
print
#end class DoublyLinkedList
theList = DoublyLinkedList() #make a new list
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
print 'Deleting first, last, and 11'
theList.removeFirst() #remove first item
theList.removeLast() #remove last item
theList.removeKey(11) #remove item with key 11
theList.displayForward() #display list forward
print 'Inserting 77 after 22, and 88 after 33'
theList.insertAfter(22, 77) #insert 77 after 22
theList.insertAfter(33, 88) #insert 88 after 33
theList.displayForward() #display list forward