Ordered list maintenance data structure
MIT License
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
console.log(p.value)
console.log(head.compare(p))
console.log(p.compare(head)
console.log(p.compare(p))
var createList = require("ordered-list")
var head = createList(item1,item2,...)
Creates a list with the given items
item1
is the value of the first item in the listitem2
is the value of the second item in the listReturns 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
node.next
The next node in the list
node.prev
The previous node in the list
node.value
The value of the node
node.compare(other)
Compares two nodes in the list. If other
giving the relative position of them within the list.
other
is another node in the listReturns A number which has the value:
0 if node comes after other
node.insert(value)
Inserts a node immediately after node
into the list having value value
value
is the value of the new node to insertnode.remove()
Removes a node from the list, modifying the list in place
node.split()
Splits the list after the node.
Returns The head of the rest of the list after node
(c) 2013 Mikola Lysenko. MIT