如何用o（1）性能脱离链接列表？

发布于 2025-01-22 21:32:37 字数 1037 浏览 3 评论 0原文

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

我对如何创建一个删除最内向节点的o（1）Dequeue（1）函数感到困惑。

例如，排列队列（节点（2，节点（1）），无）应导致队列：队列（无，节点（2，none）），其中队列的前部为节点（2，无）。

因为该功能应该具有O（1）性能，所以我看不到如何在不删除其父节点的情况下访问节点（1，无）。我只能删除“最外部”节点，因此，通过设置queue.front =queue.front.rest。I

。希望这是我第一次在Stackoverflow上发布，所以我知道我的帖子可能有点不清楚。

原文

    """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.

分享到QQ

分享到微博