Linked lists in JSON

It's time for another Javascript post! This time it will be about efficiency, which is not only a subject dear to my heart, but abnormally important for web development in Javascript. Javascript is a slow, interpreted language that runs on the browsers on people's phones, so we need tightly focused code to avoid slowing down things even more. More specifically, efficient data structures. Even more specifically, efficient lists.

A sea of lists

A list is conceptually simple: A finite ordered collection of things. There. That's it. So, why does there exist nine gadzillion different variations of it? Efficient programming boils down to choosing the right data structures for the task at hand. Even the simple list has many different implementations, each suited to tackling a different set of problems.

The most common list implementations are:

1. Arrays. Just data stacked end-to-end in a long line. Efficient for random access reading, but costly to manipulate. To remove an element in the middle, you will have to traverse over the full list and shift all successive elements 1 index back.
2. Generators. Aka "lazy lists". These are just code that emit one data element at a time. Very efficient memory usage, as elements are conjured only when needed. Horribly inefficient for lookup.
3. Linked lists. A loose collection of nodes, where each node contains one data element, and has a reference to the next node in the list. Inefficient for lookup, but very efficient for manipulation and insertion.

In Javascript, and consequently JSON, only Arrays are natively supported. But that's fine, because Generators and Linked lists are easy to implement yourself. And that's what we're going to do today!

We're going to create a function for transforming Javascript arrays into JSON linked lists.

The Array to JSON Linked list translator

Array.prototype.toJSONll = function (idx) {
  idx = idx || 0;
  if (idx >= this.length) return "null";
  idxS = idx.toString();
  valueS = JSON.stringify(this[idx]);
  nextS = this.toJSONll(idx + 1);
  return ("{idx: " + idxS +
          ", value: " + valueS +
          ", next: " + nextS + "}");
  var idxS = null;
  var valueS = null;
  var nextS = null;
};

For convenience, it is implemented as an extension method to the standard Javascript Array class. This means you can include this snippet in your code, and voila! All your existing arrays now have a .toJSONll() method!

I've embedded the code into this actual webpage, so if you want to test it out, type a valid Javascript array into the text field below and push the button:

You can't test this, because you don't have Javascript enabled.  SYNTAX ERROR{idx: 0, value: "hey", next: {idx: 1, value: 4, next: {idx: 2, value: {"some":"object"}, next: null}}}

That's all for this time! I might make my next post about encoding lazy lists in JSON. What do you guys think?