Ordered list maintenance data structure


A data structure for ordered list maintenance. This generalizes a linked list, except it adds the ability to query the order of any two elements in the list in constant time. This implementation is based on Bender's O(1) amortized algorithm using two-level indirection.


var createList = require("ordered-list")
var head = createList(1, 0, -5, 10)
var p = head.next.next


var createList = require("ordered-list")

Creates a list with the given items

  • item1 is the value of the first item in the list
  • item2 is the value of the second item in the list
  • ... and so on

Returns A the first node in a new ordered list data structure. If no arguments are specified, returns a list with one node having the value undefined. Terminals of the list are null

The next node in the list

The previous node in the list

The value of the node

Compares two nodes in the list. If other giving the relative position of them within the list.

  • other is another node in the list

Returns A number which has the value:

  • <0 if node comes before other
  • 0 if node === other
  • 0 if node comes after other

Inserts a node immediately after node into the list having value value

  • value is the value of the new node to insert

Removes a node from the list, modifying the list in place

Splits the list after the node.

Returns The head of the rest of the list after node

(c) 2013 Mikola Lysenko. MIT