Python 3: Popping from the front and end of a Node based Deque in O(1) time

0
votes

(I searched for well over 2 hours for a solution to this but couldn't find any sample code with what I needed)

Hey guys, I created a Queue class and a Deque class that inherits Queue. My Node class that I am using to build these structures is initialized with 2 fields: item, and next.

I am trying to have my Deque class dequeue from both ends in O(1) time, but my issue is that the next pointer only goes in one direction. I can easily add items to the end of the Deque by setting the next pointer to the new_node I create, and I can easily add items to the front by setting the head of the Deque = to my new_node and then say the next item is the old head.

I can even delete items from the front easily by just saying head = head.next

My issue: I cannot delete items from the REAR of the Deque because my pointer at the end is pointing towards nothing if I delete it. I cannot say tail = tail.next because that points to nothing.

I have no idea how I'm having an issue with such a seemingly easy problem but I cannot for the life of me figure out what to do here.

What am I missing/not accounting for??

My problem code is at the very bottom of what I am providing, but if you want to read the rest of it, feel free to!

class Node:

    def __init__(self, value):
        self.item = value
        self.next = None

    def get_value(self):
        return self.item

    def set_value(self, value):
        self.item = value

    def get_next(self):
        return self.next

    def set_next(self, other_node):
        self.next = other_node


class Queue:

    def __init__(self):
        self.size = 0
        self.head = None
        self.tail = None

    def is_empty(self):
        if self.size == 0:
            return True
        else:
            return False

    def peek(self):
        return self.head.item

    def enqueue(self, value):
        new_node = Node(value)
        if self.isEmpty():
            self.tail = new_node
            self.head = self.tail
            self.size += 1

        else:
            self.tail.next = new_node
            self.tail = new_node
            self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError('Can not dequeue from an empty queue')
        else:
            value = self.head.item
            self.head = self.head.next
            self.size -= 1
        return value

    def printout(self):
        if self.is_empty():
            return 'Queue is empty'

        else:
            temp = self.head
            while temp is not self.tail:
                print('[ {} ] -> '.format(temp.item), end='')
                temp = temp.next
            print('[ {} ]'.format(self.tail.item))


class Deque(Queue):

    def __init__(self):
        super().__init__()

    def peek_back(self):
        return self.tail.item

    def enqueue_front(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.head = new_node
            self.tail = self.head
            self.size += 1
        else:
            temp = self.head
            self.head = new_node
            self.head.next = temp
            self.size += 1

    def dequeue_back(self):
        if self.is_empty():
            raise IndexError
            # ??????
            # ??????
2
pythonpython-3.xlinked-listqueuedeque
Have you considered adding a self.previous variable in your Node class to point to the preceding, if any, node? – Sean Francis N. Ballais
Yes most definitely this is an option, but I was wondering if there was a way to do this just using the next pointer and what is provided in the Queue class. Basically to get it to work without modifying my Node class – Garrett1021
How about you use a separate queue with the same elements as the original queue but is flipped (i.e. the first element in the original queue would become the last element but its self.next would point to nothing, the second element in the original queue would become the second to the last element with its self.next pointing to what is now the last element, and so on) to keep track of what the previous element of each element in the original queue is? Please tell me if this is unclear. – Sean Francis N. Ballais
Very interesting. Thank you for your responses Sean! – Garrett1021

2 Answers

2
votes

You need a doubly linked list to achieve your goals in O(1).

You can subclass your Node class and add a pointer to the previous node, and use this in your Deque class.

Alternatively, as pointed out in the comments, you could use two singly linked lists (the second linked in reverse), but that doesn't seem very practical.

2
votes

As Sean stated in the comments, one solution would be to add a previous instance variable to your Node class. This is the practical and suggested approach.

However, since you're fixed on using this idea of using next exclusively, you can do the following. Since you track the size of the queue with size, assuming the queue is not empty, the only way you can get the next-to-last element and set the tail to point to it (deleting from the rear) is to:

next_to_last = self.head
for _ in range(self.size - 1):
    next_to_last = next_to_last.next
self.tail = next_to_last

While this is fine in terms of memory (only stores the local next_to_last variable, it is not an O(1) operation.

Another suggestion is to create separate Node classes for the Queue and the Dequeue; maybe store the Node class inside the queue classes themselves:

class Queue:
    class Node:
        # ...

class Dequeue:
    class Node:
        # ...

Using that approach, you can define a self.prev in your Dequeue's Node class, but not in the regular Queue's Node class.