Define "cyclic data structures"

At the JSON site it says

JSON does not support cyclic data structures, so be careful to not give cyclical structures to the JSON 开发者_JS百科stringifier.

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

---

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

Now you can do this, for example:

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

---

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": ??? } }

---

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;

---

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.

---

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" }
  }

---

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

---

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

---

CYCLE: A situation in which you return to the same place where you started.

CYCLIC DATA STRUCTURE: A data structure in which such situation might arise. For example graph,linked list (singly/doubly), dequeue, etc.

A linked list node in JS is implemented as:

function Node(data){
    this.data = data;
    this.next = null;
}

Now I create two such nodes as shown below:

var node1 = new Node(10);
var node2 = new Node(20);

And link them to form a cycle.

node1.next = node2;
node2.next = node1;

The following traversal code will enter an infinite loop which shows the existence of a cycle.

node = node1;
while(node!==null){
    print(node.data);
    node = node.next;
}

---

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.