reoder_linked_list.js

// Doubly-linked list
const list = {
  root: 'a',
  nodes: {
    a: {id: 'a', next: 'b'},
    b: {id: 'b', prev: 'a', next: 'c'},
    c: {id: 'c', prev: 'b', next: 'd'},
    d: {id: 'd', prev: 'c'},
  }
};

// Complexity: O(n)
function getInOrder({root, nodes}) {
  const out = [];
  let el = {next: root};
  while(el = nodes[el.next]) out.push(el.id);
  return out;
}

// Complexity: O(1)
function moveBetween(list, idToMove, prevId, nextId) {
  const {nodes} = list;
  const prev = nodes[prevId];
  const next = nodes[nextId];

  const node = nodes[idToMove];
  const nodeNext = nodes[node.next];
  const nodePrev = nodes[node.prev];

  // 1. update node's next
  if (nodeNext) nodeNext.prev = node.prev;

  // 2. update node's prev
  if (nodePrev) nodePrev.next = node.next;

  // 3. update node's next & prev
  node.next = nextId;
  node.prev = prevId;

  // 4. update next & prev to node
  if (prev) prev.next = idToMove;
  if (next) next.prev = idToMove;

  // 5. update the root
  if (list.root === idToMove) list.root = node.next;
  if (list.root === nextId) list.root = idToMove
}

// Proof
console.log(getInOrder(list));
moveBetween(list, 'd', 'a', 'b');
//moveBetween(list, 'a', 'b', 'c');
//moveBetween(list, 'd', undefined, 'a');
//moveBetween(list, 'a', 'd', undefined);
console.log(getInOrder(list));