'How to dequeue a linked list with O(1) performance?

    """dequeues item, removing first item from front NodeList
    If front NodeList is empty, remove items from rear NodeList
    and add to front NodeList until rear NodeList is empty
    If front NodeList and rear NodeList are both empty, raise IndexError
    Must be O(1) - general case"""
class Node:
    def __init__(self, value: Any, rest: Optional[Node]):
        self.value = value      # value
        self.rest = rest        # NodeList

class Queue:
    def __init__(self, rear: Optional[Node] = None, front: Optional[Node] = None, num_items: int = 0):
        self.rear = rear    # rear NodeList
        self.front = front   # front NodeList
        self.num_items = num_items  # number of items in Queue

I'm confused as to how I could create an O(1) dequeue() function that removes the innermost Node.

For example, dequeuing Queue(Node(2, Node(1)), None) should result in the queue: Queue(None, Node(2, None)), where the front of the Queue is Node(2, None).

Because the function should have O(1) performance, I don't see how I could access Node(1, None) without removing its parent nodes. I could only remove the "outermost" Node, such that dequeuing Queue(Node(2, Node(1, None)) results in Queue(Node(1, None)) by setting Queue.front = Queue.front.rest.

I hope this makes sense. This is my first time posting on StackOverflow, so I know my post may be a bit unclear. Please let me know if any details are wrong.



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source