Define "cyclic data structures"

Question

At the JSON site it says

JSON does not support cyclic data structures, so be careful to not give cyclical structures to the JSON stringifier.

What does it mean by this? Can someone give me an example of such a data structure in Javascript?

Answer 1

A data structure with a cyclic graph: http://en.wikipedia.org/wiki/Cycle_graph

Answer 2

if you have:

var a = {value: 'a'};
var b = {value: a};
var c = {value: a};

In JSON for b it would look like:

"{value: {value: 'a'}}"

In JSON for c it would look like:

"{value: {value: 'a'}}"

No pointers.

Answer 3

var cyclic = {};
cyclic.somekey = cyclic;
cyclic.another = "Hello world!";

Now you can do this, for example:

alert(cyclic.somekey.somekey.somekey.another);

Answer 4

If you imagine the members of the data structure laid out as a graph, a cyclic data structure is where a member refers back to another one or the structure itself.

For example:

var obj = new Object();

obj.left = new Object();

obj.left.left = obj;

This is impossible to represent in JSON, you would need to refer to the outer {} part somehow:

{ "left": { "left": ??? } }

Answer 5

The object contains a cycle, i.e., it refers to itself or, more generally, some object to which it refers either directly or through some property is the original object.

 var $this =  { };
 $this["self"] = $this;

or more likely

 var child = { parent: null };
 var parent = { child: child };
 child.parent = parent;

Answer 6

A cyclic data structure is a structure that holds a reference to itself (directly or indirectly). See also http://en.wikipedia.org/wiki/Circular_reference

Here is an example of such structure:

var c = { value: 'abc' };
c['c'] = c;
c['a'] = { value: c };

If you try to print its string representation recursively, you will end up with a stack overflow, because to print a value of c you must print the value of c.

Answer 7

js> var a = {label:"a", next:null};
js> var b = {label:"b", next:a};
js> a.next = b; // cycle is created here
[object Object]
js> print(a.next.label);
b
js> print(a.next.next.label);
a
js> print(a.next.next.next.label);
b
js> print(a.next.next.next.next.label);
a

Answer 8

I guess the textbook example of a cyclic structure is the doubly-linked list. Each element points to the previous and next elements in the list. This means each element forms a cycle with the previous and next element.

A --> B  --> C
A <-- B  <-- C

(Here each A, B, C although written twice is one object.)

A points to B, as next in the list. B points to A as previous in the list. So there is a cycle from A to B and back to A. The same is true for every element in the list, with elements not at the head or tail beloning to two cycles.

One solution to serializing lists like this is to use IDs to represent each object. This removes the cycles in the structure. We could then write out

  list: {
     items:
      { id:"a", value1: ... etc },
      { id:"b", values .... },
      { id:"c", values .... }
     links:
       { elem:"a", next:"b" },
       { elem:"b", next:"c", prev: "a"},
       { elem:"c", prev:"b" }
  }