Last active
June 25, 2019 05:01
-
-
Save motss/4fe01603b339c2193c608f86244a9ad4 to your computer and use it in GitHub Desktop.
Reference cycles in JavaScript
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * 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