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 =var head =var p = headnextnextconsoleconsoleconsole
var createList =
Creates a list with the given items
item1is the value of the first item in the list
item2is the value of the second item in the list
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
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.
otheris another node in the list
Returns A number which has the value:
0 if node comes after other
Inserts a node immediately after
node into the list having value
valueis 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
(c) 2013 Mikola Lysenko. MIT