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

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

  1. Philip

    Philip Guest

    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.
     
    Philip, Jul 14, 2005
    #1
    1. Advertising

  2. Philip

    MooMaster Guest

    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:

    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-----
    >>> 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
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    483
    emerth
    Jul 10, 2003
  2. Sonoman
    Replies:
    9
    Views:
    379
    lilburne
    Nov 9, 2003
  3. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    472
    emerth
    Jul 10, 2003
  4. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    410
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  5. jawdoc
    Replies:
    9
    Views:
    760
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page