9: Abstract Data Types

Example 1: Page 167

In [1]:
#demonstrates a stack implemented as a 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 ourself
		print self.dData,
#end class Link

class LinkList:
	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 item on list
		#(no links on list yet)

	def __del__(self):	#destructor (deletes list)
		self.__init__()

	def isEmpty(self):	#true if list is empty
		return self._pFirst == None

	def insertFirst(self, dd):	#insert at start of list
		#make new link
		pNewLink = Link(dd)
		pNewLink.pNext = self._pFirst	#newLink-->old first
		self._pFirst = pNewLink	#first-->newLink

	def deleteFirst(self):	#delete first item
		#(assumes list not empty)
		pTemp = self._pFirst	#save old first link
		self._pFirst = self._pFirst.pNext	#remove it: first-->old next
		key = pTemp.dData	#remember data
		del pTemp	#delete old first link
		return key	#return deleted link's data

	def displayList(self):	#display all links
		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 LinkList

class LinkStack:
	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._pList = LinkList()	#make a linked list

	def __del__(self):	#destructor
		del self._pList	#delete the linked list

	def push(self, j):	#put item on top of stack
		self._pList.insertFirst(j)

	def pop(self):	#take item from top of stack
		self._pList.deleteFirst()

	def isEmpty(self):	#true if stack is empty
		return self._pList.isEmpty()

	def displayStack(self):
		print
		print 'Stack (top-->bottom):',
		self._pList.displayList()
#end class LinkStack

theStack = LinkStack()	#make stack

theStack.push(20)	#push items
theStack.push(40)

theStack.displayStack()	#display stack (40, 20)

theStack.push(60)	#push items
theStack.push(80)

theStack.displayStack()	#display (80, 60, 40, 20,)

theStack.pop()	#pop items (80, 60)
theStack.pop()

theStack.displayStack()	#display stack (40, 20)
#end
Stack (top-->bottom): 40 20
Stack (top-->bottom): 80 60 40 20
Stack (top-->bottom): 40 20

Example 2: Page 171

In [2]:
#demonstrates list with first and last references

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 FirstLastList:
	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
		self._pLast = None	#last link

	def __del__(self):	#destructor
		self.__init__()	#deletes list

	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
		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
		self._pLast = pNewLink	#newLink <--last

	def removeFirst(self):	#remove first link
		#(assumes non-empty list)
		pTemp = self._pFirst	#remember first link
		if not self._pFirst.pNext:	#if only one item
			self._pLast = None#None <-- last
		self._pFirst = self._pFirst.pNext	#first-->old next
		del pTemp	#delete the link
		
	def displayList(self):
		print 'List (first-->last):',
		pCurrent = self._pFirst	#start at beginning
		while pCurrent:	#until end of list,
			pCurrent.displayLink()	#print data
			pCurrent = pCurrent.pNext	#move to next link
#end class FirstLastList

theList = FirstLastList()	#make 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.displayList()	#display the list

print
print 'Deleting first two items'

theList.removeFirst()	#remove first two items
theList.removeFirst()

theList.displayList()	#display again
#end
List (first-->last): 66 44 22 11 33 55
Deleting first two items
List (first-->last): 22 11 33 55

Example 3: Page 175

In [3]:
#demonstrates queue implemented as double-ended 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 FirstLastList:

	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
		self._pLast = None	#last link

	def __del__(self):	#destructor
		self.__init__()	#deletes list

	def isEmpty(self):	#true if no links
		return self._pFirst == None

	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
		self._pLast = pNewLink	#newLink <--last

	def removeFirst(self):	#delete first link
		#(assumes non-empty list)
		pTemp = self._pFirst	#remember first link
		temp = self._pFirst.dData
		if not self._pFirst.pNext:	#if only one item
			self._pLast = None#None <-- last
		self._pFirst = self._pFirst.pNext	#first-->old next
		del pTemp	#delete the link
		return temp
		
	def displayList(self):
		pCurrent = self._pFirst	#start at beginning
		while pCurrent:	#until end of list,
			pCurrent.displayLink()	#print data
			pCurrent = pCurrent.pNext	#move to next link
#end class FirstLastList

class LinkQueue:
	def __init__(self):
		self._theList = FirstLastList()

	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.removeFirst()

	def displayQueue(self):
		print 'Queue (front-->rear):',
		self._theList.displayList()
		print
#end class LinkQueue

theQueue = LinkQueue()	#make a queue

theQueue.insert(20)	#insert items
theQueue.insert(40)

theQueue.displayQueue()	#display queue (20, 40)

theQueue.insert(60)	#insert items
theQueue.insert(80)

theQueue.displayQueue()	#display queue (20, 40, 60, 80)

print 'Removing two items'
theQueue.remove()	#remove items (20, 40)
theQueue.remove()

theQueue.displayQueue()	#display queue (60, 80)
Queue (front-->rear): 20 40
Queue (front-->rear): 20 40 60 80
Removing two items
Queue (front-->rear): 60 80