'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 |
|---|
