I have a data structure that is essentially a linked list stored in state. It represents a stream of changes (patches) to a base object. It is linked by key, rather than by object reference, to allow me to trivially serialise and deserialise the state.

It looks like this:

const latest = 'id4' // They're actually UUIDs, so I can't sort on them (text here for clarity)
const changes = {
  id4: {patch: {}, previous: 'id3'},
  id3: {patch: {}, previous: 'id2'},
  id2: {patch: {}, previous: 'id1'},
  id1: {patch: {}, previous: undefined},
}

At some times, a user chooses to run an expensive calculation and results get returned into state. We do not have results corresponding to every change but only some. So results might look like:

const results = {
  id3: {performance: 83.6},
  id1: {performance: 49.6},
}

Given the changes array, I need to get the results closest to the tip of the changes list, in this case results.id3.

I've written a while loop to do this, and it's perfectly robust at present:

    let id = latest
    let referenceId = undefined
    while (!!id) {
      if (!!results[id]) {
        referenceId = id
        id = undefined
      } else {
        id = changes[id].previous
      }
    }

The approach is O(N) but that's the pathological case: I expect a long changelist but with fairly frequent results updates, such that you'd only have to walk back a few steps to find a matching result.

While loops can be vulnerable

Following the great work of Gene Krantz (read his book "Failure is not an option" to understand why NASA never use recursion!) I try to avoid using while loops in code bases: They tend to be susceptible to inadvertent mistakes.

For example, all that would be required to make an infinite loop here is to do delete changes.id1.

So, I'd like to avoid that vulnerability and instead fail to retrieve any result, because not returning a performance value can be handled; but the user's app hanging is REALLY bad!

Other approaches I tried

Sorted array O(N)

To avoid the while loop, I thought about sorting the changes object into an array ordered per the linked list, then simply looping through it.

The problem is that I have to traverse the whole changes list first to get the array in a sorted order, because I don't store an ordering key (it would violate the point of a linked list, because you could no longer do O(1) insert).

It's not a heavy operation, to push an id onto an array, but is still O(N).

The question

Is there a way of traversing this linked list without using a while loop, and without an O(N) approach to convert the linked list into a normal array?

CodePudding user response：

Since you only need to append at the end and possibly remove from the end, the required structure is a stack. In JavaScript the best data structure to implement a stack is an array -- using its push and pop features.

So then you could do things like this:

const changes = []; 

function addChange(id, patch) {
    changes.push({id, patch});
}

function findRecentMatch(changes, constraints) {
    for (let i = changes.length - 1; i >= 0; i--) {
        const {id} = changes[i];
        if (constraints[id]) return id;
    }
}

// Demo
addChange("id1", { data: 10 });
addChange("id2", { data: 20 });
addChange("id3", { data: 30 });
addChange("id4", { data: 40 });

const results = {
  id3: {performance: 83.6},
  id1: {performance: 49.6},
}

const referenceId = findRecentMatch(changes, results);
console.log(referenceId);  // id3

Depending on what you want to do with that referenceId you might want findRecentMatch to return the index in changes instead of the change-id itself. This gives you the possibility to still retrieve the id, but also to clip the changes list to end at that "version" (i.e. as if you popped all the entries up to that point, but then in one operation).

CodePudding user response：

While writing out the question, I realised that rather than avoiding a while-loop entirely, I can add an execution count and an escape hatch which should be sufficient for the purpose.

This solution uses Object.keys() which is strictly O(N) so not technically a correct answer to the question - but it is very fast.

If I needed it faster, I could restructure changes as a map instead of a general object and access changes.size as per this answer

    let id = latest
    let referenceId = undefined
    const maxLoops = Object.keys(changes).length
    let loop = 0
    while (!!id && loop < maxLoops) {
      loop  
      if (!!results[id]) {
        referenceId = id
        id = undefined
      } else {
        id = changes[id].previous
      }
    }