Thursday 8 September 2011

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
That's all for this time! I might make my next post about encoding lazy lists in JSON. What do you guys think?

5 comments:

  1. Thank you for posting this. JSON/Javascript is an important part of the modern coder's toolkit, and lots of coders don't pay a sufficient mind to the efficiency properties of their toolbelt contents! Glad to see that someone is planting that flag.

    ReplyDelete
  2. You have to traverse down your objects like normal to find the id when you want to delete something, which shouldn't be necessary.

    so
    obj(3).next = obj(4).next

    becomes (over iteration)
    obj.obj.obj.next() = obj.obj.obj.obj.next()

    ReplyDelete
  3. This is brilliant, but not up to the same standard as your postings of yesteryear. You had a fantastic streak of posts. My favorites were the c# memory management series, the job interview, and the post about management. It's rare that you get a view of the profession from so many angles and with such professionalism. I hope you have a few more in depth posts in store for 2012!

    ReplyDelete
  4. helo i have improved yr implumantashon with making it as a dubaly linked list. i think it works maybe

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

    ReplyDelete
  5. Hi Doug! Glad to see my post could be of inspiration to you!

    As an open source coder, nothing makes me more happy than to see other people expanding on and improving my code.

    Doubly linked lists sound like a great idea, but I'm a bit unsure about how this would affect the operational efficiency as it's using a dict for recursion-restriction lookup.

    I'll be sure to try it out and see how it goes. This could be a good excuse as any to start writing a JavaScript profiler. :)

    ReplyDelete