# [linked lists] Newbie - chapter 19 in "How to think like a CS in python"

Discussion in 'Python' started by Philip, Jul 14, 2005.

1. ### PhilipGuest

Hi,
I'm reading "How to think like a computer scientist in python". So far,
it's been smooth sailing, but the final exercise in chapter 19 really
has me stumped. Is it just me, or did this book get very difficult, very
quickly? It says:

"As an exercise, write an implementation of the Priority Queue ADT using a
linked list. You should keep the list sorted so that removal is a constant
time operation. Compare the performance of this implementation with the
Python list implementation."

Here is the code so far:

import sys

class Node:
def __init__(self, cargo=None, next=None, prev=None):
self.cargo = cargo
self.next = next
self.prev = prev

def __str__(self):
return str(self.cargo)

def printBackward(self):
if self.next != None:
tail = self.next
tail.printBackward()
print self.cargo

def __init__(self):
self.length = 0

def printBackward(self):
print "["
print "]"

node = Node(cargo)
self.length = self.length + 1

def printList(node):
sys.stdout.write("[")
while node:
sys.stdout.write(str(node.cargo))
if node.next != None:
sys.stdout.write(", ")
else:
sys.stdout.write("]")
node = node.next
print

def printBackward(list):
if list == None:
return
tail = list.next
printBackward(tail)

def removeSecond(list):
if list == None: return
if list.next == None: return
first = list
second = list.next
first.next = second.next
second.next = None
return second

def printBackwardNicely(list):
print "[",
if list != None:
tail = list.next
printBackward(tail)
print "]"

class Queue:
def __init__(self):
self.length = 0

def isEmpty(self):
return (self.length == 0)

def insert(self, cargo):
node = Node(cargo)
node.next = None
else:
while last.next: last = last.next
last.next = node
self.length = self.length + 1

def remove(self):
self.length = self.length - 1
return cargo

class ImprovedQueue:
def __init__(self):
self.length = 0
self.last = None

def isEmpty(self):
return (self.length == 0)

def insert(self, cargo):
node = Node(cargo)
node.next = None
if self.length == 0:
else:
last = self.last
last.next = node
self.last = node
self.length = self.length + 1

def remove(self):
self.length = self.length - 1
if self.length == 0:
self.last = None
return cargo

class PriorityQueue:
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

def insert(self, item):
self.items.append(item)

def remove(self):
maxi = 0
for i in range(1,len(self.items)):
if self.items > self.items[maxi]:
maxi = i
item = self.items[maxi]
self.items[maxi:maxi+1] = []
return item

class Golfer:
def __init__(self, name, score):
self.name = name
self.score = score

def __str__(self):
return "%-16s: %d" % (self.name, self.score)

def __cmp__(self, other):
if self.score < other.score: return 1
if self.score > other.score: return -1
return 0

I figured I'd copy ImprovedQueue and tamper with the insert method
so as to traverse the linked list, checking if the cargo of the next node
was smaller than the one I was inserting, and if so, to set the current
node's next to the new node, and the new node's next to the node with the
lesser value, but I just can't get this to work outside of my head. I'd
appreciate any pointers anyone might give me to figure this out.

Philip, Jul 14, 2005

2. ### MooMasterGuest

Re: Newbie - chapter 19 in "How to think like a CS in python"

Well, being a lowly CS student myself this sounded like fun, so I went
ahead and took the challenge. The first thing you have to consider is
how to add the new element to the list. Obviously you have to iterate
through the list, find the first element that the new one is greater
than, and insert this one before it while keeping the list structure
intact. You must also remember to update the head if necessary, and add
at the end if the element to be added is less than what is already in
the list...So this is what I came up with:

def printQueue(self):
if(self.isEmpty()):
print "Empty"
else:
while(pointer != None):
print str(pointer.cargo)
pointer = pointer.next

Then------
class PriorityQueueList(ImprovedQueue):
def __init__(self):
ImprovedQueue.__init__(self)

def insert(self, cargo):
newNode = Node(cargo)
if self.length == 0:
else:
#iterate through the list, keeping a reference to a
node and the node before it
while(tracker !=None):
copy2 = tracker.prev
if(newNode.cargo > tracker.cargo):
tracker.prev = newNode
newNode.next = tracker
newNode.prev = copy2
if(copy2 !=None):
copy2.next = newNode
break
else:
tracker = tracker.next
#if a repeat element is added
#we want to add to end to preserve the queue structure,
thus if the element hasn't
#been added at this point it should be added at the end

if(newNode.prev ==None and newNode.next ==None):
last = self.last
last.next = newNode
self.last = newNode
self.length = self.length + 1

This produces the following output-----
>>> l = PriorityQueueList()
>>> l.insert(1)
>>> l.insert(2)
>>> l.insert(1)
>>> l.printQueue()

2
1
1
>>> l.insert(10)
>>> l.printQueue()

10
2
1
1

Hope this helps!

MooMaster, Jul 20, 2005