java - 删除/撤销双向链表中的节点

Question

我知道在双向链表中删除一个节点的时间复杂度是O(1)。我见过很多代码示例，其中人们在双向链表的删除方法中使用循环，但时间复杂度仍然是 O(1)。我编写了一个撤消代码，即删除双向链表中的节点，但我的问题是:我的代码是否会在 undo() 方法中撤消/删除 O(1) 中的节点我调用包含循环的 getNode() 方法？我希望得到解释!提前致谢!

private Node <T> getNode( int idx ){
        return getNode( idx, 0, size( ) - 1 );
    }
private Node<T> getNode( int idx, int lower, int upper ){
        Node<T> p;
        if( idx < lower || idx > upper ){
            throw new IndexOutOfBoundsException( "getNode index: " + idx + "; size: " + size( ) );
        }
        if( idx < size( ) / 2 )
        {
            p = beginMarker.next;
            for( int i = 0; i < idx; i++ )
                p = p.next;            
        }
        else
        {
            p = endMarker;
            for( int i = size( ); i > idx; i-- )
                p = p.prev;
        } 
        return p;
    }
public void undo(){
        if(isEmpty()){
            throw new RuntimeException("Undo history is empty");
        }
        else{
            T data = undoStackDatas.topAndPop();
            int index = undoStackIndexes.topAndPop();
            //Push data and index back into redo stacks
            redoStackDatas.push(data);
            redoStackIndexes.push(index);

            Node<T> obj = getNode(index);
            if(obj == beginMarker){
                beginMarker = obj.next;
            }
            else{
                obj.prev.next = obj.next; 
            }

            if(obj == endMarker){
                endMarker = obj.prev;
            }
            else{
                obj.next.prev = obj.prev;
            }
            theSize--;
            modCount--;
        }
    }

Answer 1

如果给定了必须删除的节点，则从双链表中删除节点的时间复杂度为 O(1)。

但是如果你必须搜索节点，那么你的复杂度就会因为搜索而改变。在这种情况下，你的复杂度将变为 O(n)。