How does JavaScript's DOM updating algorithm work?

Here's a simple DOM playground that logs the state whenever a button is clicked:

<!-- begin snippet: js hide: false console: false babel: false -->

<!-- language: lang-js -->

const parent = document.querySelector('#parent');
const [div1, div2, div3] = parent.children;
const [removeDiv2, addDiv4, reset] =
  document.querySelectorAll('button');

const div4 = document.createElement('div');
div4.classList.add('children');
div4.id = 'div4';
div4.textContent = 'div4';


logCurrentState();


removeDiv2.addEventListener('click', () => {
  parent.removeChild(div2);
  logCurrentState();
});


addDiv4.addEventListener('click', () => {
  parent.insertBefore(div4, div3);
  logCurrentState();
});


reset.addEventListener('click', () => {
  parent.replaceChildren(div1, div2, div3);
  console.clear();
  logCurrentState();
})

function logCurrentState() {
  console.log(
    [...parent.children].map(
      child => ({
        previous: child.previousElementSibling?.id ?? null,
        current: child.id,
        next: child.nextElementSibling?.id ?? null
      })
    )
  );
}

<!-- language: lang-css -->

.children {
  padding: 1em;
  font-family: monospace;
}

#div1 {
  background: #ef6461;
}

#div2 {
  background: #e4b363;
}

#div3 {
  background: #e8e9eb;
}

#div4 {
  background: #e0dfd5;
}

<!-- language: lang-html -->

<script src="https://gh-canon.github.io/stack-snippet-console/console.min.js"></script>

<div id="parent">
  <div class="children" id="div1">div1</div>
  <div class="children" id="div2">div2</div>
  <div class="children" id="div3">div3</div>
</div>

<button>Remove div2</button>
<button>Add div4</button>
<button>Reset</button>

<!-- end snippet -->

As one can see, JS updates each element's relevant properties (e.g. .nextElementSibling, previousElementSibling, .children, etc.) immediately when a DOM-modifying method (e.g. .removeChild(), .insertBefore(), .replaceWith(), etc.) is called.

For convenience, here's an excerpt from the logs:

// Original
[
  { previous: null, current: 'div1', next: 'div2' },
  { previous: 'div1', current: 'div2', next: 'div3' },
  { previous: 'div2', current: 'div3', next: null }
]

// After removing div2
[
  { previous: null, current: 'div1', next: 'div3' },
  { previous: 'div1', current: 'div3', next: null }
]

How does the engine do this under the hood? Is it standardized by the spec or implementation-specific? What is the complexity of the algorithm in question?

> JS updates each element's relevant properties

Not really. JS does trigger the update, but it (generally) doesn't do the update by itself.

In most user agents the DOM doesn't live within the JS engine, the JS engine just sends instructions to the DOM engine through an API that is defined at https://dom.spec.whatwg.org/

Stuff like Element#previousElementSibling in the JS world are getters, like you could define one yourself e.g with

const obj = {
  get myProp() { /* execute something and return a value */ }
};

except that here it executes internal code that will call methods of the DOM engine, which will ultimately convert the DOM value back to a JS value that the JS engine can work with.

The standards do no define how a DOM value is converted to or from a JS value, so this would be left to the implementation, but they do define how a value is converted between JS and infra or Web IDL, which do define the data types used by the specifications, and which ensures that all (complying) implementations will expose the same behavior.

Some readings about a particular implementation (Chromium + V8).
Special mention to jsdom and their JS implementation, where you can see how they also use a getter to implement previousElementSibling et al.