DLL Operation: Insert Before

  • Trace the basic operations of a (doubly) linked-list implementation.
  • Understand the basic operations of a (doubly) linked list well enough to implement them.

Suppose we want to insert a note before the one pointed to by the reference variable target:

Exercise Complete the implementation of insertBefore.

public void insertBefore(Node<T> target, T data) {
	// TODO Implement me!
}

Hint: Use the following visualization as guidance.

Solution 
public void insertBefore(Node<T> target, T data) {
  Node<T> nodeToInsert = new Node<>(data);
  Node<T> prevNode = target.prev;

  target.prev = nodeToInsert;
  nodeToInsert.next = target;

  nodeToInsert.prev = prevNode;
  prevNode.next = nodeToInsert;
}

Caution: the implementation above fails to account for edge cases!