jsclass

LinkedList

A linked list is a data structure used to represent sequences of objects. It’s a bit like an array, except that, instead of each item being indexed using a number, each item has a pointer to the item after it (and sometimes the one before as well). The only type implemented in this library is the doubly circular type. This is the most ‘general’, but the code has been constructed in such a way that you can build on part of this library to create singly-linked and linear lists.

// In the browser
JS.require('JS.LinkedList', function(LinkedList) { ... });

var LinkedList = require('jsclass/src/linked_list').LinkedList;

LinkedList.Doubly.Circular

This is the only concrete list type fully implemented in this library. The class structure is as follows, should you wish to build other list types:

• LinkedList implements methods common to all linked lists
• LinkedList.Doubly implements methods common to linear and circular doubly-linked lists

If you’re curious, I recommend reading the source code.

Using linked lists

To use a linked list, you create it as follows and add objects to it:

var list = new LinkedList.Doubly.Circular();
var foo = {}, bar = {}, baz = {};
list.push(foo);
list.push(bar);
list.push(baz);

// list.first == foo
// list.first.next == bar
// list.first.next.next == list.last == baz

// circular list, so...
// list.first.prev == baz
// list.last.next == foo

The objects you add to a list are given prev and next properties to refer to their neighbours by. Note that the things you add to a linked list must be objects (not numbers, strings, etc) or the list will not work properly.

Available methods

The linked list API looks like this:

• at(n) – returns the object at index n in the list.
• push(object) – appends object to the list.
• pop() – removes the last item in the list and returns it.
• shift() – removes the first item in the list and returns it.
• unshift(object) – adds object to the start of the list.
• insertAt(n, object) – inserts object at position n in the list.
• insertAfter(node, object) – inserts object into the list after node.
• insertBefore(node, object) – inserts object into the list before node.
• remove(object) – removes object from the list.

LinkedList.Node

Each node in a linked list can only belong to that list – it cannot have multiple prev/next pointers. If you want to add an object to several lists, you can wrap it in a node object before adding it to each list:

var listA = new LinkedList.Doubly.Circular();
var listB = new LinkedList.Doubly.Circular();

var obj = {name: 'Jimmy'};
listA.push(new LinkedList.Node(obj));
listB.push(new LinkedList.Node(obj));

listA.first.data.name   // -> "Jimmy" 
listB.first.data.name   // -> "Jimmy" 

listA.first == listB.first    // -> false
listA.first.data == listB.first.data    // -> true

Each node object is distinct, but has a data pointer to the object it wraps. This also lets you add the same object to a list multiple times.

Enumerating a linked list

If the Enumerable module is loaded before the LinkedList code, then you can treat linked lists as enumerable objects. You can loop over their nodes like so:

list.forEach(function(node, i) {
    // do stuff with node
    // i is the position in the list
}, context);

context is optional, and specifies the meaning of the this keyword inside the function. All the usual Enumerable methods are available on list objects – see the Enumerable docs for more info.