Skip to content

Doubly linked list container type with navigation between node siblings and between node and container

License

Notifications You must be signed in to change notification settings

vissermc/chainlist.js

Repository files navigation

ChainList.js

Use this container type when the elements needs quick access to its siblings and/or its parent container or associated parent element. Hence, its navigability is the very similar to the DOM.

It is implemented as a doubly linked list, therefore navigating n elements away takes O(n) time. Additionally, there is fast (O(1)) access to the parent list, the last element, and the element count.

Both the list (ChainList) and its nodes (ChainList.Node) inherit from ChainList.Link. Concrete elements can either inherit from ChainList.Node or aggregate it by passing itself as parameter (see dashed 'elem' in diagram). Similarly, a concrete container can either inherit from ChainList or aggregate it (see dashed 'parent' in diagram). Some functions, such as 'indexLink', 'nextLink', and 'prevLink', traverse over all links.

UML

Also available, a sorted variant of ChainList called ChainListSorted. It does not have a unshift, push, or insertAt function. Only insert and insertArray can be used to insert elements. They will be inserted at the correct sorted location according the comparison function supplied to the constructor.

Example

var list = ChainList.fromArray([6,3,7,8])
list.get(2) == 7
var thirdNode = list.index(2)  
thirdNode.elem()== 7  
thirdNode.next().elem()==8  
thirdNode.list() == list  
var list2 = new ChainList();  
var elemX = {};
elemX.node = list2.insertAt(0,elemX); // also store a reference to the node from within the elem object.  
...  
elemX.node.next().elem() // travel from the item to an adjacent item

List-only functions

  • ChainList( parent )
    Constructor, where a parent aggregator can be supplied which can be accessed using 'list.parent()'.
  • ChainListSorted( parent, compareFunc )
    Constructor for a sorted ChainList, where the compareFunc(a,b) will determine where the element will be placed: before the first element b where the function returns a positive number.
  • parent ()
    Returns the parent object, or itself, if parent is null/undefined.
  • setParent ()
    Sets the parent object.
  • clear ()
    Removes all elements from the list.
  • count () Returns the amount of elements in the list (in constant time).
  • insertAt ( index,elem )
    Inserts at index 'index', starting from zero, the element in this list and returns the created node. Negative indices will insert backwards, where -1 will append the item.
  • removeAt ( index )
  • ChainList.fromArray ( array,parent )

Node-only functions

  • ChainList.Node ( prev, elem optional ) Constructor. Adds a node after 'prev'. It will be correctly inserted in the list between the other nodes.
  • elem () Returns the element object, or itself, if the element is null/undefined.
  • remove () Removes this node from the list
  • setElem ( val ) Changes the element.

Common functions

  • first ()
  • last ()
  • index ( n )
    In case link is a list, it returns the n'th node, or if n is negative, returns (count - n)'th node. Else, it returns n'th successor or -n'th predecessor. This list itself is never returned, not does it wrap around.
  • selfIndex () Returns index of the node, or -1 if object is the list.
  • get ( n )
    In case link is a list, it returns the n'th elem, or if n is negative, returns (count - n)'th elem. Else, it returns n'th successor or -n'th predecessor. It will not wrap around.
  • takeRange ( start,end ) takes and inserts a range of nodes from another list
  • take ( list ) takes and inserts (the rest of) another list
  • takeSome ( list,count ) takes and inserts certain amount of nodes.
  • clone ()
    Returns a copy of (the rest of) the list.
  • cloneRange ( end ) Creates a new list of a range of nodes.
  • cloneSome ( count ) Creates a new list of a certain amount of nodes.
  • shiftRange ( end ) Removes a range of nodes
  • shiftSome ( count ) Removes the certain amount of node
  • shift () Removes the current node
  • slice ( begin,end ) Clones a subset of nodes in a new list.
  • splice ( index,cutCount,elemToInsert1 ) Removes nodes and inserts elements aggregrated in new nodes, and returns the removed nodes as a list.
  • pop () Removes the last node
  • insert ( elem ) Inserts a single element by aggregating it in a new node.
  • insertArray ( elems ) InsertS multiple elements by aggregating them in new node.
  • unshift (elem1...)
    Inserts elems by aggregating then in new nodes, at the begin of the list return new length property.
  • push ( elem1, ..., elemN )
    Inserts elems by aggregating then in new nodes, at the end of the list return new length property.
  • indexOf ( node ) Returns the position of the node, or -1 if it cannot be found.
  • indexOfElem ( elem ) Returns the position of the element, or -1 if it cannot be found.
  • lastIndexOfElem ( elem )
  • indexLink ( n )
    Returns n'th successor or -n'th predecessor link. This list itself is also link that might be returned. This function wraps around.
  • nextLink ()
    Returns the next link, i.e. either a node or the list.
  • prevLink ()
    Returns the previous link, i.e. either a node or the list.
  • next ()
    returns the next node, or null if it was the last.
  • prev ()
    returns the previous link, or null if it was the first.
  • countRange ( end )
  • isList ()
  • reverse ()
  • forEachRange ( end, func ( elem,index,Node ): retval )
  • forEach ( func ( elem,index,Node ): retval )
  • forEachBackRange ( end, func ( elem,index,Node ): retval )
  • forEachBack ( func (elem,index,Node ): retval )
  • map ( func ( elem,index,Node ): retval )

About

Doubly linked list container type with navigation between node siblings and between node and container

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published