Skip to content

Instantly share code, notes, and snippets.

@motss
Last active June 25, 2019 05:01
Show Gist options
  • Select an option

  • Save motss/4fe01603b339c2193c608f86244a9ad4 to your computer and use it in GitHub Desktop.

Select an option

Save motss/4fe01603b339c2193c608f86244a9ad4 to your computer and use it in GitHub Desktop.
Reference cycles in JavaScript
/**
* Reference cycles can be hard to detect in normal program logic.
* It's even harder to print the entire linked list when it has its own item pointing to its first item,
* thus creating a circular linked list.
*
* However, it looks like V8 has a clever method on printing a circular data structure.
*
* In contrast, a handwritten printing mechanism fails to do so since
* there is always an item linked to the end of the list. This overflows the stack and
* crashes the browser. A simple way to deal with this is to make sure that no any other
* node has been visited or printed more than once. This will technically print all the
* list item and once it's back to the first item where it started from it stops right
* there because it encounters an already visited/ printed node.
*
* Here, I'm giving each item its own unique name, so that I can keep track of the visited
* nodes while traversing the circular linked list.
*/
printList = (a) => {
const l = [a.value];
const visited = new Set([a.name]);
let next = a.next;
while (next && !visited.has(next.name)) {
l.push(next.value);
visited.add(next.name);
next = next.next;
}
return l;
};
ll = (value, next, name) => ({ value, next, name });
/** Creating 2 lists: a, b via linked list function (FP-based) */
a = ll(2, null, 'a');
b = ll(5, a, 'b');
/** Update a to point to b, to complete a circular linked list */
a.next = b;
console.log('a', printList(a), a);
console.log('b', printList(b), b);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment