[Tutor] confused by linked queue

[John Fouhy]

On 25/07/06, Christopher Spears <cspears2002 at yahoo.com> wrote:
>                >>> from linked_queue import *
> >>> queue = Queue()
> >>> queue.isEmpty()
> True
> >>> queue.insert("cargo")
> >>> print queue.head
> cargo
> >>> print queue.length
> 1
> >>> queue.insert("more_cargo")
> >>> print queue.length
> 2
> >>> print queue.head
> cargo
>
> Where is my second node?  How can I access it?

Try 'print queue.head.next' :-)

A queue is, well, a queue.  Visualise a queue of people.  Initially,
the queue is empty: there's no one standing there.  Then someone comes
and stands at the head of the queue; now the queue has one person in
it (queue.length is 1).

Then, another person comes along.  That person starts at the head of
the queue, and walks down the queue until they find the end.  Then
they join the end.

This is what is happening in this bit of code --- here, you walk down
the queue until you get to the end (ie: a node with no "next" node):

                       # find the last node in the list
                       last = self.head
                       while last.next:
                               last = last.next

And here, you add the new node on to the end:

                       # append the new node
                       last.next = node

It appears there is a bug in the code; these two lines should NOT be
part of the while loop (ie: the indendation is incorrect).

The result looks something like this:

(best viewed with a fixed-width font)

head --> /--------\    /--------\
         | next --+--> | next --+--> None
         |        |    |        |
         | cargo-\|    | cargo-\|
         \-------+/    \-------+/
                 |             |
                \|/           \|/
              "cargo"    "more cargo"

Hope this helps; if not, ask more questions :-)

-- 
John.