Using Sentinel Nodes

  • Explain the advantages of using sentinel node-based implementation.

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

Using sentinel nodes eliminates many of the edge cases that arise in implementing linked list operations.

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

We don't need to treat the case where head == null differently as that never happens with a sentinel node implementation.

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