Зачем использовать "node.getNext () == null" в качестве соглашения для несуществующего узла?

Question

Это фрагмент кода из книги «Структуры данных и алгоритмы в Java (6-е изд.)». Этот метод является частью реализации 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 cast

if (node.getNext( ) == null) // convention for defunct node
    throw new IllegalArgumentException("p is no longer in the list");

return node;
}

Answer 1

Реализация в книге, о которой вы спрашиваете, использует явный узел trailer, который представляет позицию "один за концом" в структуре. Следовательно, все узлы в списке должны иметь следующий узел. Следовательно, если метод узла getNext() возвращает null, этого узла нет в списке.

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

Answer 3

В этом случае несуществующий узел означает несуществующий узел.

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

В этом случае у узла p есть метод с именем getNext(), который может вернуть значение null, если это так, то это означает, что он является последним из узлов. Другими словами, нет следующего узла.

Этот вид структур, как следует из названия, связывает между собой. getNext () должна возвращать позицию в памяти, где находится следующий узел, если такой позиции тогда не существует, то там нет узла.

Обычно node, скорее всего, будет иметь метод с именем setNext(Position<E> next), это аналог, который сохраняет позицию следующего элемента для этого узла.