How does this linked queue code work? - Python

Question

I'm trying to get an understanding of how this code works and I've run into some confusion as to how to think about it, particularly with how everything is linked together.

Here's how I'm thinking about it:

When the Queue (Q) is initialized we have Q = [self._head = None, self._tail = None, size = 0] (not python code -- just a visual way to organize the data attributes), then when the first element is enqueued we create a node N1 = (e1, None) and it's assigned to self._head and self._tail and Q = [(e1, None), (e1, None), 1].

When a second element is enqueued to the queue we create a second node N2=(e2, None) and we have self._tail._next = newest which updates Q to Q = [(e1, None), (e1, N2), 1]. Then the code has self._tail = newest which then updates Q to Q=[(e1, None), (e2, None), 2].

It seems like it doesn't actually link anything here. What exactly am I missing here in my understanding of this code?

class LinkedQueue:

    class _Node:

        __slots__='__element', '__next'

        def __init__(self, element, next):
            self._element = element
            self._next = next

    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0

    def dequeue(self):
        if self.is_empty():
            raise Exception('Queue is empty')
        answer = self._head._element
        self._head = self._head._next
        self._size -= 1
        if self.is_empty():
            self._tail = None
        return answer

    def enqueue(self, e):
        newest = self._Node(e, None)
        if self.is_empty():
            self._head = newest
        else:
            self._tail._next = newest
        self._tail = newest
        self._size += 1

Josh K · Accepted Answer · 2017-09-06 00:28:04Z

1

A Queue will have at least two points: one to the head and one to the tail. This allows you to iterate over nodes in the order they were added and add new nodes to the end of the queue. We can visualize an empty Queue as:

    Head -> <- Tail

Adding a 1 to the Queue:

    Head -> 1 <- Tail

Adding a 2 to the Queue:

    Head -> 1 
            2 <- Tail

Adding a 3 to the Queue:

    Head -> 1 
            2
            3 <- Tail

Dequeueing an element means moving Head to the next element and returning the old value.

            1 <- first_element

    Head -> 2
            3 <- Tail

I have a fairly basic Queue implementation if you'd like to look at that.

answered Sep 6, 2017 at 0:28

Josh K

28.9k20 gold badges89 silver badges132 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How does this linked queue code work? - Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related