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 lined list.
• You will have the head and the tail pointer to always point to sentinel nodes.
• Sentinel nodes will be constructed by the constructor; 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 insertFront. Considering head and tail point to sentinel nodes.

public Position<T> insertFront(T data) {
  if (head == null) {
    head = new Node<T>(data, this);
    tail = head;
    numElements += 1;
    return head;
  }

  Node<T> newFront = new Node<T>(data, this);

  Node<T> currFront = head;
  newFront.next = currFront;
  currFront.prev = newFront;
  head = newFront;

  numElements += 1;
  return newFront;
}

@Override
public Position<T> insertFront(T data) {
  Node<T> newFront = new Node<T>(data, this);

  Node<T> currFront = head.next;
  newFront.next = currFront;
  currFront.prev = newFront;
  head.next = newFront;
  newFront.prev = head;

  numElements += 1;
  return newFront;
}