Doubly List Delete

Remove the first node matching a value by splicing its neighbours together through prev and next pointers.

Time O(n) Space O(1) Doubly Linked List delete

How it works

Remove the first node matching a value by splicing its neighbours together through prev and next pointers.

Implementation

function dllDeleteOp(state, target) {
  const valueArr = state.value;
  const next = state.next;
  const prev = state.prev;
  let current = state.head;
  while (current !== -1) {
    visitNode(current);
    compareKeys(current, target);
    if (valueArr[current] === target) {
      const p = prev[current];
      const n = next[current];
      if (p !== -1) {
        next[p] = n;
      } else {
        state.head = n;
      }
      if (n !== -1) {
        prev[n] = p;
      }
      removeNode(current);
      finish(current);
      return;
    }
    current = next[current];
  }
  reportNotFound();
}