Nsryjdtyk

I've been struggling with this for a good while now. I've implemented a queue using a linked list. It's working fine, but I don't know why(?). I adapted the enqueue method from a java example but I can't work out why it's working.

class Node:



def __init__(self, data):

    self.data = data

    self.node= None



class Queue:



def __init__(self):

    self.first = Node(None)

    self.last = Node(None)

    self.n = 0



def enqueue(self, data):

    body = self.last

    self.last = Node(data)  # this is a new node



    if self.is_empty():

        self.first = self.last

    else:

        body.node = self.last # this adds body.node to self.first.node recursively ???? How is body node and self.first.node linked?

    self.n += 1



def dequeue(self):

    result = self.first.data

    self.first = self.first.node

    self.n -= 1

    return result



def is_empty(self):

    return self.n == 0

The problem is the enqueue method. I'm confused by the body variable. I've run the code through a pycharm debugger and carefully traced the three node variables self.first self.last and body. As the comments say, when body.node = self.last executes a new node object is attached to self.first.node recursively so that after three enqueue call I've got an object which looks like this: self.first.node.node.

Each node contains the appropriate data values and I can simply read them out of the queue with my dequeue method. (Happy days).

The problem is I cannot work out why. I can't see how body is programatically linked to self.first.

Can you please explain.

body is just a reference to self.last - that is the only place the assignment (body = self.last) occurs. This often has the name tmp or old_last or the like.

You need this since self.last is no longer referencing the last node in the queue, since self.last = Node(data). Now, since body is the old last, its node value was None (this is an invariant that has to be true - check it!). Since we do not want it to be last anymore, we set it to the new node we created - which is nicely referenced by self.last, which we just re-assigned. This is why body.node = self.last is right - the old last node is now pointing to the new last node (which is pointing to None, as we want).

There is nothing recursive here - just a temporary variable holding a reference to the old last.

When the queue is empty you get to:

self.first = self.last

which is where the node is first initialized (in enqueue). Note this means you have a minor bug, you lose the first reference in __init__ to the first Node(None), effectively a "memory leak" in other languages, but it matters little in Python.

The real bug is if you dequeue a new queue twice - try it. The first time will set first to None (which is not a Node), and the second will break since None has no data member.

Overall the implementation is flawed - I would redo it.