[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[i] > 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.