Removing/undoing双向链表中的唯一节点

Question

我的代码从最新添加的开始一个一个地撤消添加的元素。除非列表中只剩下一个节点并且我的代码没有从列表中 undo/remove 它，否则它会正确执行所有操作。例如：

[A, B, C, D, E] //call undo()
[A, B, C, D] //call undo()
[A, B, C] //call undo()
[A, B] //call undo()
[A] //call undo() and it throws Exception here <------------------
Exception in thread "main" java.lang.NullPointerException

如果我撤消 [A] 它应该 return 空列表 []。注意：我必须使用一个名为 beginMarker 和 endMarker 的虚拟节点，其值为 null，因此最后一个元素如下所示：

beginMarker <-> "A" <-> endMarker

对于最后一个元素，代码检查大小是否等于 1，如果为真，则继续执行，但不会清空列表。任何帮助将不胜感激！

 public void add(x){
         .........
         undoStack.push(newNode);
    }
    public void undo(){
            if(undoStack.isEmpty()){
                throw new RuntimeException("Undo history is empty");
            }
            else{
                Node<T> object = undoStack.topAndPop();

                redoStack.push(object);
                if(this.size() == 1){
                    beginMarker = object.next;
                    beginMarker.next = null;
                    //beginMarker.next = null;
                }

                if(object.prev == beginMarker){
                    beginMarker.next = object.next.prev;
                    object.next.prev = beginMarker;
                }

                else if(object.next == null){
                    object.prev.next = null;
                }
                else{
                    object.next.prev = object.prev;
                    object.prev.next = object.next;
                }





                theSize--;
                modCount--;
                countUndone++;
}

Class SimpleStack

public class SimpleStack<AnyType>{

  // Tracks the top node of stack.
  private Node<AnyType> topOfStack;

  // Construct the stack.
  public SimpleStack( ) {
    topOfStack = null;
  }

  // Test if the stack is logically empty.
  // @return true if empty, false otherwise.
  public boolean isEmpty( ) {
    return topOfStack == null;
  }

  // Make the stack logically empty.
  public void clear( ) {
    topOfStack = null;
  }

  // Insert a new item into the stack.
  // @param x the item to insert.
  public void push( AnyType x ) {
    topOfStack = new Node<AnyType>( x, topOfStack );
  }

  // Remove the most recently inserted item from the stack.
  // @throws UnderflowException if the stack is empty.
  public void pop( ) {
    if( isEmpty( ) )
      throw new RuntimeException( "SimpleStack pop" );
    topOfStack = topOfStack.next;
  }

  // Get the most recently inserted item in the stack.
  // Does not alter the stack.
  // @return the most recently inserted item in the stack.
  // @throws UnderflowException if the stack is empty.
  public AnyType getTop( ) {
    if( isEmpty( ) )
      throw new RuntimeException( "SimpleStack empty in getTop" );
    return topOfStack.data;
  }

  // Return and remove the most recently inserted item
  // from the stack.
  // @return the most recently inserted item in the stack.
  // @throws UnderflowException if the stack is empty.
  public AnyType topAndPop( ) {
    if( isEmpty( ) )
      throw new RuntimeException( "SimpleStack empty in topAndPop" );

    AnyType topItem = topOfStack.data;
    topOfStack = topOfStack.next;
    return topItem;
  }

  // A singly linked Node which contains data and a link to another
  public class Node<T>{
    public T data;
    public Node<T> next;

    public Node(T d, Node<T> n ){
      this.data = d;
      this.next = n;
    }
  }

}

Answer 1

我不会对 NPE 发生在这里感到惊讶：

if(object.prev == beginMarker){
    beginMarker.next = object.next.prev; 
    //                             ^^^^ 
    //                             is it here ? object.next is null in your case
    object.next.prev = beginMarker;
}

它应该修复它以简单地写

if(object.prev == beginMarker && object.next != null) {
    beginMarker.next = object.next.prev;
    object.next.prev = beginMarker;
}

但是，您实际上不必具体说明案例 size() == 1。一个更简单的实现是（假设你添加一个指向列表末尾的指针）：

public void undo() {
    if (undoStack.isEmpty()) {
        throw new NoSuchElementException("Undo history is empty");
    } else {
        Node<T> object = undoStack.topAndPop();
        redoStack.push(object);

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

        theSize--;
        modCount--;
        countUndone++;
    }
}

这应该有效，因为使用 endMarker 会阻止您在列表中包含任何 null 节点。

Removing/undoing双向链表中的唯一节点

Removing/undoing the only node in a doubly linked list

java

nodes

doubly-linked-list