container-sortedlist

SortedList implementation in Javascript

To manage a sorted list of elements. Best use case: elements are frequently removed from the list or the property on which they are sorted can slightly change. Complexity in O(1) for removal. (For list sizes above a few hundreads elements, consider using an avl tree instead, such as container-avltree).

Note: Benchmarks seem to show that list iteration is as fast as array iteration on all major browsers.

To instantiate a new list:

// In this example, myList will hold elements sorted by zIndex
function myComparisonFunction(a, b) {
	return a.zIndex - b.zIndex;
}

var myList = new SortedList(myComparisonFunction);

To add an element:

var myObjectReference = myList.add(myObject);

To remove an element:

myList.removeByReference(myObjectReference); // O(1)
// or
myList.remove(myObject); // O(n)

To reposition an element:

myList.reposition(myObjectReference);

To move an element to the beginning of the list:

myList.moveToTheBeginning(myObjectReference);

To move an element to the end of the list:

myList.moveToTheEnd(myObjectReference);

To iterate through the elements, in sorted order:

for (var node = myList.first; node !== null; node = node.next) {
	console.log(object);
}

To apply a treatment on all the elements in sorted ordered:

myList.forEach(function (object) {
	console.log(object);
});

To apply a treatment on all the elements in opposite sorted ordered:

myList.forEachReverse(function (object) {
	console.log(object);
});

To convert into an array:

var myArray = myList.toArray();