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

[Philip]

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

class LinkedList:
def __init__(self):
self.length = 0
self.head = None

def printBackward(self):
print "["
if self.head != None:
self.head.printBackward()
print "]"

def addFirst(self, cargo):
node = Node(cargo)
node.next = self.head
self.head = node
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
head = list
tail = list.next
printBackward(tail)
print head,

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:
head = list
tail = list.next
printBackward(tail)
print head,
print "]"

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

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

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

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

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

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

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

def remove(self):
cargo = self.head.cargo
self.head = self.head.next
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.

 

[MooMaster]

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:

First of all, however, add this to your Improved Queue Class-----
def printQueue(self):
if(self.isEmpty()):
print "Empty"
else:
pointer = self.head
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:
self.head = self.last = newNode
else:
#iterate through the list, keeping a reference to a
node and the node before it
tracker = self.head
while(tracker !=None):
copy2 = tracker.prev
if(newNode.cargo > tracker.cargo):
#add the new node by updating links, then update
head while keeping list intact
tracker.prev = newNode
newNode.next = tracker
self.head = newNode
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-----

2
1
1

10
2
1
1

Hope this helps!