为什么要使用“ node.getNext（）== null”作为已失效节点的约定？

Question

这是《 Java中的数据结构和算法》（第六版）一书中的代码片段。该方法是LinkedPositionalList实现的一部分。我不确切了解这行的含义：“ if（node.getNext（）== null）//已失效节点的约定”是针对的。我希望对其功能进行一些解释。// private utilities/** Validates the position and returns it as a node. */private Node<E> validate(Position<E> p) throws IllegalArgumentException { if (!(p instanceof Node)) throw new IllegalArgumentException("Invalid p");Node<E> node = (Node<E>) p; // safe castif (node.getNext( ) == null) // convention for defunct node    throw new IllegalArgumentException("p is no longer in the list");return node;}

Answer 1

在这种情况下，失效节点表示不存在的节点。

if (node.getNext( ) == null) // convention for defunct node

在这种情况下，该节点p有一个称为的方法，该方法getNext()可以返回null，如果返回，则表示它是节点的最后一个。换句话说，没有下一个节点。

顾名思义，这种结构相互链接。getNext（）应该在内存中返回下一个节点的位置，如果该位置不存在，则那里不存在任何节点。

通常node可能会有一个称为setNext(Position<E> next)this的方法，该方法为该节点保存下一个项目的位置。

Answer 2

如果您读过这本书，第7章的“双向链接列表实现”部分将说明由于消除了列表中任何已删除的位置（节点）而导致的无效位置概念。因为该remove()方法实现了将要删除的位置设置为null值。

因此，该validate()方法实际上检查输入位置是否未从列表中删除。再次，通过检查调用getNext()是否会带来null价值。如果是这样，则必须null使用该remove()方法将其设置为已删除位置。因此，由于输入位置p不再在列表中（因为它是已删除的位置），因此将引发错误。

为了更好地理解，只需参考本书中的delete（）方法即可。这是书中的内容：

// Removes the element stored at Position p and returns it (invalidating p).

public E remove(Position<E> p) throws IllegalArgumentException {

  Node<E> node = validate(p);

  Node<E> predecessor = node.getPrev();

  Node<E> successor = node.getNext();

  predecessor.setNext(successor);

  successor.setPrev(predecessor);

  size−−;

  E answer = node.getElement();

  node.setElement(null);          // help with garbage collection

  node.setNext(null);             // and convention for defunct node

  node.setPrev(null);

  return answer;

}