Remove cycle from the object in JavaScript

Given an object with a cycle, remove the cycle or circular reference from it.

Example

Input:
const List = function(val){
  this.next = null;
  this.val = val;
};

const item1 = new List(10);
const item2 = new List(20);
const item3 = new List(30);

item1.next = item2;
item2.next = item3;
item3.next = item1;

// this form a cycle, if you console.log this you will see a circular object, 
// like, item1 -> item2 -> item3 -> item1 -> so on.

Output:
// removes cycle
// item1 -> item2 -> item3

If you see the above example, we have created a list object, that accepts a value and pointer to the next item in the list, similar to a linked list, and using this we have created the circular object.

We have to create a function that will break this cycle, in this example to break the cycle we will have to delete the next pointer of the item3.

Remove cycle from the object in JavaScript

There are two places where this cycle removal can take place,

1. For normal use of Object.
2. While creating the JSON string.

We will see both approaches.

Normal use

We can use WeakSet which is used to store only unique object references and detect if the given object was previously detected or not, if it was detected then delete it.

This cycle remove always takes place inplace.

const removeCycle = (obj) => {
    //set store
    const set = new WeakSet([obj]);
    
    //recursively detects and deletes the object references
    (function iterateObj(obj) {
        for (let key in obj) {
            // if the key is not present in prototye chain
            if (obj.hasOwnProperty(key)) {
                if (typeof obj[key] === 'object'){
                    // if the set has object reference
                    // then delete it
                    if (set.has(obj[key])){ 
                      delete obj[key];
                    }
                    else {
                      //store the object reference
                        set.add(obj[key]);
                      //recursively iterate the next objects
                        iterateObj(obj[key]);
                    }
                }
            }
        }
    })(obj);
}

Input:
const List = function(val){
  this.next = null;
  this.val = val;
};

const item1 = new List(10);
const item2 = new List(20);
const item3 = new List(30);

item1.next = item2;
item2.next = item3;
item3.next = item1;

removeCycle(item1);
console.log(item1);

Output:
/*
{val: 10, next: {val: 20, next: {val: 30}}}
*/

---

Using JSON.stringify while creating JSON.

JSON.stringify, accepts a replacer function that can be used to alter the value of the strinfication process.

We can use the same function to detect and remove the cycle from the object.

const getCircularReplacer = () => {
    //form a closure and use this 
    //weakset to monitor object reference.
    const seen = new WeakSet();
    
    //return the replacer function
    return (key, value) => {
        if (typeof value === 'object' && value !== null) {
            if (seen.has(value)) {
                return;
            }
            seen.add(value);
        }
        return value;
    };
};

input:
console.log(JSON.stringify(item1, getCircularReplacer()));

output:
"{'next':{'next':{'val':30},'val':20},'val':10}"

Reference:- https://github.com/sadanandpai/javascript-code-challenges/