java - DoublyLinkedList(普林斯顿版)删除方法如何工作？

Question

我正在尝试了解如何 DoublyLinkedList.java作为普林斯顿版本。请点击超链接以获取详细信息。

但是时间久了，我还有两个问题想完全理解这个实现。

问题 1:remove 方法中的 if-else block 如何工作？什么时候会发生分支？

    // 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)

Answer 1

正如 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;
}