Using Sentinel Nodes

A common practice when implementing a link list is to use sentinel nodes.

• Sentinel nodes are dummy nodes that you add to both ends of your linked list.
• You will have the head and the tail pointer to always point to sentinel nodes. The constructor will construct the sentinel nodes; they will never be removed nor updated.
• You should not count the sentinel nodes as elements of the data structure.
• The sentinel nodes should not be considered when iterating over the elements of the data structure.

Here is the constructor of LinkedList building the sentinel nodes:

public LinkedList() {
  head = new Node<>(null, this);
  tail = new Node<>(null, this);
  head.next = tail;
  tail.prev = head;
  numElements = 0;
}

Exercise Update the implementation of delete (in DoublyLinkedList.java) to account for all edge cases. Consider head and tail point to sentinel nodes.

public void delete(Position<T> target) {
  Node<T> targetNode = convert(target);
  Node<T> beforeTarget = targetNode.prev;
  Node<T> afterTarget = targetNode.next;

  beforeTarget.next = afterTarget;
  afterTarget.prev = beforeTarget;
}