刪除/撤銷雙向鏈表中的節點

Question

我知道刪除雙向鏈表中的節點的時間複雜度爲O（1）。我見過很多代碼示例，其中人們在雙向鏈表中使用remove方法中的循環，但時間複雜度爲O（1）。我已經寫了一個代碼，撤消，即刪除雙向鏈表中的節點，但我的問題是：我的代碼撤消/刪除O（1）undo()方法中的節點，因爲我呼叫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

，因爲當你跟蹤代碼的執行路徑，您需要遍歷這些for循環，爲循環完全執行你的，你將增加的for循環的時間複雜度。你只是不能減少使用方法調用的時間複雜度，因爲在程序執行過程中，所有執行的語句都會被計數。

Answer 2

從雙向鏈表中刪除一個節點是O（1），如果給了你必須刪除的節點。

但是在這種情況下，您必須搜索節點，那麼您的複雜性將因搜索而改變。在這種情況下，您的複雜度將變爲O（n）。