DoublyLinkedList（princeton版本）刪除方法如何工作？

我想了解DoublyLinkedList.java如何作爲普林斯頓版本。請點擊超鏈接獲取詳細信息。DoublyLinkedList（princeton版本）刪除方法如何工作？

但經過很長時間，我仍然有兩個問題要完全理解這個實現。

問題1：remove方法中的if-else塊如何工作？分支何時發生？

// remove the element that was last accessed by next() or previous() 
    // condition: no calls to remove() or add() after last call to next() or previous() 
    public void remove() { 
     if (lastAccessed == null) throw new IllegalStateException(); 
     Node x = lastAccessed.prev; 
     Node y = lastAccessed.next; 
     x.next = y; 
     y.prev = x; 
     n--; 

     // Below if-else condition I don't understand on which situation 
     // "current == lastAccessed" will happen ? 
     if (current == lastAccessed) 
      current = y; 
     else 
      index--; 
     lastAccessed = null; 
    }

問題2：對於一個功能齊全DoublyLinkedList，我們也應該包含添加或在特定位置刪除節點，例如add(int index)或remove(int index)，但在普林斯頓版本我找不到對這個部分的任何暗示，怎麼可能我實施了這兩種方法？有人可以發表一些細節嗎？（注意：此版本使用的是ListIterator）

來源

2016-12-04 Lampard

歡迎來到Stack Overflow！看起來你正在尋求作業幫助。雖然我們本身沒有任何問題，但請觀察這些[應做和不應該]（http://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions/338845＃338845），並相應地編輯您的問題。 –

嗨，@Joe C，我不再是學生，只是對這段代碼感興趣，我可以輕鬆地找到DoublyLinkedList的其他實現，但是由於我在工作時間之後自己學習數據結構，所以我想知道上面的兩個問題，因爲原始代碼沒有足夠的提示這兩個部分，並且實現與Java stand庫不太相似，謝謝。 – Lampard

add/remove/set在迭代器上實現。如果您需要它們，您可以簡單地將便利方法添加到類本身（實踐中，不要使用此實現）。 if條件區分在調用「previous」或「next」之後調用的remove。 else分支覆蓋'next'分支。 – pvg

正如pvg所說，實現完全取決於用戶和需求。另外，DoublyLinkedLists不是很好的實現。

答1：假設你在列表中添加5個項目：3，2，53，23，1，然後執行以下無需調用next()或previous()第一：

iterator.remove();

它會拋出IllegalStateException因爲lastAccessed爲空。爲什麼它是空的？它爲空，因爲lastAccessed僅在next()和previous()中更新。通過調用next()或previous()，您沒有訪問任何節點。

答案2：您可以通過傳遞索引和要添加的節點的引用來添加。

public void add(int index, Node item) { 
    if (index > size) throw new IndexOutOfBoundsException(); 

    Node cursor = head.next; 
    int i = 0; 
    while (i < index) { 
     i++; 
     cursor = cursor.next; 
    } 

    item.next = cursor.next; 
    item.next.prev = item; 
    cursor.next = item; 
    item.prev = cursor; 
    size++; 
}

對於remove()功能，就可以實現這一點：remove(int index)。只需遍歷列表int i=0直到i < index，然後刪除該節點。這將花費O（n）時間。或者更簡單的方法是將參考傳遞給要刪除的節點。這將需要O（1）。

實施取決於您的要求。如果您需要通過索引刪除並且沒有對節點的引用，那麼您必須遍歷該列表。或者只是通過要刪除的節點的引用：

public void remove(Node item) { 
    Node prev = item.prev; 
    Node next = item.next; 

    prev.next = next; 
    next.prev = prev; 

    item.next = null; 
    item.prev = null; 
}

來源

2016-12-04 21:22:57 rafid059

DoublyLinkedList（princeton版本）刪除方法如何工作？

回答

相關問題