prevent circular reference in Array in Javascript

Question

I have a Datastructure like the following.

array=[
    {id:"a",children:[
        {id:"b",children:[
            {id:"d",children:[]}]},
            {id:"c",children:[]}]}
]

If I want to insert the element {id:"e", children:["a","f"] at "c" ("a","e" are no Strings, but copies of the nodes) I want to check, that it exists in the upper Tree and would therefore create a circular reference. So I think I have to reverse walk the array. But as I'm pretty new to Javascript and Node, I have no idea how to do that.

Would it be agood idea, to create an array, I store all the dependencies in? something like this:

[
a:[],
b:[a],
c:[a,b]
d:[a,b]
]

then I could lookup the parent in the array and would see that in c, a and b are allready in dependency

This is a little confusing, but inserting a new object like that won't create a circular reference, it just inserts a new object ? To make a circular reference, the object has to actually refer to itself. — adeneo
– adeneo, Commented Jun 15, 2017 at 14:54
maybe I wrote it wrong. I would not add an item with strings like "a","e" but with copies of the nodes. So it would create one — Flo
– Flo, Commented Jun 15, 2017 at 14:55
If children : [e] actually referred to the parent object, you'd have circular reference, but that seems unlikely and most of the time wouldn't be an issue. Anyway, it's unclear what you want to check for? When inserting that object do you want to check that there aren't more objects with the id "e" or that the object doesn't already have circular references, or what ? — adeneo
– adeneo, Commented Jun 15, 2017 at 14:58
The first thing you have to avoid is to not place an object referencing itself into it's children property. On the other hand i can not imagine under what requirement you ended up with the necessity to check up circular references. Are you trying to nest up a flat data structure..? There might be ways to avoid that check for whatever you are trying to achieve. — Redu
– Redu, Commented Jun 15, 2017 at 15:04

Nina Scholz · Accepted Answer · 2017-06-15 15:23:17Z

1

You could use a hash table, if the id is unique.

var array = [{ id: "a", children: [{ id:"b", children: [{ id: "d", children: [] }] }, { id: "c", children: [] }]  }],
    hash = Object.create(null);

// creating circular reference
array[0].children[1].children.push(array[0]);

array.forEach(function iter(a) {
    if (hash[a.id]) {
        console.log(a.id, 'circular reference found');
        return;
    }
    hash[a.id] = true;
    a.children.forEach(iter);
});
console.log(array);

answered Jun 15, 2017 at 15:23

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

prevent circular reference in Array in Javascript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related