DoublyLinkedList（普林斯顿版）删除方法如何工作？

Question

我想了解 DoublyLinkedList.java 如何作为普林斯顿版本工作。详情请点击炒作-link

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

问题 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)，但在普林斯顿版本中我找不到任何提示这部分，那么我怎么能实现这两种方法呢？有人可以 post 一些细节吗？（注意：此版本使用 ListIterator）

Answer 1

正如pvg所说，实现完全取决于用户和要求。另外，DoublyLinkedLists.

的实现不是很好

答案 1：假设您在列表中添加了 5 个项目：3、2、53、23、1。然后在不调用 next() 或 previous() 第一：

iterator.remove();

它将抛出 IllegalStateException 因为 lastAccessed 为空。为什么它是空的？它为空，因为 lastAccessed 仅在 next() 和 previous() 中更新。您尚未通过调用 next() 或 previous().

访问过 任何节点

答案2：可以通过传入要添加的节点的index和引用来添加

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

DoublyLinkedList（普林斯顿版）删除方法如何工作？

How DoublyLinkedList (princeton version) remove method works?

java

algorithm

data-structures

doubly-linked-list