Linked Lists with Symbols

2014-09-01 00:00:00 +0100 by Alex R. Young

LiLL (GitHub: BlackDice / lill, License: MIT, npm: lill) is a linked list implementation that uses the ECMAScript 6 Symbol API. Because Symbol isn't widely implemented, the author has used es6-symbol.

The motivation behind using Symbol is to provide a stateless public API with a low memory footprint. The ES6 wiki describes one of the use cases for Symbol as lightweight information hiding, so a linked list seems like a good example. In LiLL, information about neighbours is stored on the actual items, so you can hop from item to item without creating an entirely new data structure.

LiLL is attached to an owner object using Lill.attach, then you can call Lill.getNext(owner, item) or getPrevious. There are also methods for getting the head and tail.

To build and iterate over a list, you could do this:

var Lill = require('lill');
var scores = {};
Lill.add(scores, { name: 'AAA', score: 1000 });
Lill.add(scores, { name: 'ZZZ', score: 900 });

var item = Lill.getHead(scores);

while (item) {
  console.log('High score:', item.name, item.score);
  item = Lill.getNext(scores, item);

If you run this in Node's REPL you'll see entries with @@lill related data added to the owner object (scores), which describe the linked list. When Symbol is available without a shim then this will become symbols instead.