Rudiments
Public Member Functions | List of all members
linkedlist< valuetype > Class Template Reference

Public Member Functions

 linkedlist ()
 
 ~linkedlist ()
 
void prepend (valuetype value)
 
void prepend (linkedlistnode< valuetype > *node)
 
void append (valuetype value)
 
void append (linkedlistnode< valuetype > *node)
 
void insertBefore (linkedlistnode< valuetype > *node, valuetype value)
 
void insertBefore (linkedlistnode< valuetype > *node, linkedlistnode< valuetype > *newnode)
 
void insertAfter (linkedlistnode< valuetype > *node, valuetype value)
 
void insertAfter (linkedlistnode< valuetype > *node, linkedlistnode< valuetype > *newnode)
 
void moveBefore (linkedlistnode< valuetype > *node, linkedlistnode< valuetype > *nodetomove)
 
void moveAfter (linkedlistnode< valuetype > *node, linkedlistnode< valuetype > *nodetomove)
 
void detach (linkedlistnode< valuetype > *node)
 
bool remove (valuetype value)
 
bool removeAll (valuetype value)
 
bool remove (linkedlistnode< valuetype > *node)
 
uint64_t getLength () const
 
linkedlistnode< valuetype > * getFirst ()
 
linkedlistnode< valuetype > * getLast ()
 
linkedlistnode< valuetype > * getPrevious (linkedlistnode< valuetype > *node)
 
linkedlistnode< valuetype > * getNext (linkedlistnode< valuetype > *node)
 
linkedlistnode< valuetype > * find (valuetype value)
 
linkedlistnode< valuetype > * find (linkedlistnode< valuetype > *startnode, valuetype value)
 
void insertionSort ()
 
void heapSort ()
 
void clear ()
 
void print () const
 
void print (uint64_t count) const
 

Detailed Description

template<class valuetype>
class linkedlist< valuetype >

The linkedlist class allows you to store an arbitrary number of values in a doubly-linked list. Since the linkedlist class is template-based, you can store arbitrary types of values.

Each linkedlist is composed of a series of linkedlistnodes. Each linkedlistnode contains a value.

Constructor & Destructor Documentation

template<class valuetype>
linkedlist< valuetype >::linkedlist ( )

Creates an empty instance of the linkedlist class.

template<class valuetype>
linkedlist< valuetype >::~linkedlist ( )

Deletes this instance of the linkedlist class and all of its linkedlistnodes. Note however, that the data stored in each linkedlistnode is not deleted by this call.

Member Function Documentation

template<class valuetype>
void linkedlist< valuetype >::append ( valuetype  value)

Creates a new linkedlistnode containing "value" and appends it to the linkedlist.

template<class valuetype>
void linkedlist< valuetype >::append ( linkedlistnode< valuetype > *  node)

Appends already created linkedlistnode "node" to the linkedlist.

template<class valuetype>
void linkedlist< valuetype >::clear ( )

Deletes all linkedlistnodes currently in the linkedlist. Note however, that the data stored in each linkedlistnode is not deleted by this call.

template<class valuetype>
void linkedlist< valuetype >::detach ( linkedlistnode< valuetype > *  node)

Detaches "node" from the list.

template<class valuetype>
linkedlistnode<valuetype>* linkedlist< valuetype >::find ( valuetype  value)

Returns a pointer to the first linkedlistnode containing "value" or NULL if "value" was not found.

template<class valuetype>
linkedlistnode<valuetype>* linkedlist< valuetype >::find ( linkedlistnode< valuetype > *  startnode,
valuetype  value 
)

Returns a pointer to the first linkedlistnode after "startnode" containing "value" or NULL if "value" was not found.

template<class valuetype>
linkedlistnode<valuetype>* linkedlist< valuetype >::getFirst ( )

Returns the first node in the linkedlist.

template<class valuetype>
linkedlistnode<valuetype>* linkedlist< valuetype >::getLast ( )

Returns the last node in the linkedlist.

template<class valuetype>
uint64_t linkedlist< valuetype >::getLength ( ) const

Returns the number of nodes in the linkedlist.

template<class valuetype>
linkedlistnode<valuetype>* linkedlist< valuetype >::getNext ( linkedlistnode< valuetype > *  node)

Returns the node after "node" or NULL if this node is the last node in the list. "node" is presumed to be in the list.

template<class valuetype>
linkedlistnode<valuetype>* linkedlist< valuetype >::getPrevious ( linkedlistnode< valuetype > *  node)

Returns the node prior to "node" or NULL if this node is the first node in the list. "node" is presumed to be in the list.

template<class valuetype>
void linkedlist< valuetype >::heapSort ( )

Sorts the linkedlist in ascending order using a heap sort algorithm. This sort is faster than heapSort() but uses additional memory in proportion to the size of the list.

template<class valuetype>
void linkedlist< valuetype >::insertAfter ( linkedlistnode< valuetype > *  node,
valuetype  value 
)

Creates a new linkedlistnode containing "value" and inserts it into the linkedlist after "node".

template<class valuetype>
void linkedlist< valuetype >::insertAfter ( linkedlistnode< valuetype > *  node,
linkedlistnode< valuetype > *  newnode 
)

Inserts already created linkedlistnode "newnode" into the linkedlist after "node".

template<class valuetype>
void linkedlist< valuetype >::insertBefore ( linkedlistnode< valuetype > *  node,
valuetype  value 
)

Creates a new linkedlistnode containing "value" and inserts it into the linkedlist before "node".

template<class valuetype>
void linkedlist< valuetype >::insertBefore ( linkedlistnode< valuetype > *  node,
linkedlistnode< valuetype > *  newnode 
)

Inserts already created linkedlistnode "newnode" into the linkedlist before "node".

template<class valuetype>
void linkedlist< valuetype >::insertionSort ( )

Sorts the linkedlist in ascending order using a modified insertion sort algorithm. This sort is slower than heapSort() but uses no additional memory.

template<class valuetype>
void linkedlist< valuetype >::moveAfter ( linkedlistnode< valuetype > *  node,
linkedlistnode< valuetype > *  nodetomove 
)

Moves node "nodetomove" to the position after "node" in the linkedlist.

template<class valuetype>
void linkedlist< valuetype >::moveBefore ( linkedlistnode< valuetype > *  node,
linkedlistnode< valuetype > *  nodetomove 
)

Moves node "nodetomove" to the position before "node" in the linkedlist.

template<class valuetype>
void linkedlist< valuetype >::prepend ( valuetype  value)

Creates a new linkedlistnode containing "value" and prepends it to the linkedlist.

template<class valuetype>
void linkedlist< valuetype >::prepend ( linkedlistnode< valuetype > *  node)

Prepends already created linkedlistnode "node" to the linkedlist.

template<class valuetype>
void linkedlist< valuetype >::print ( ) const

Prints out a representation of the linkedlist.

template<class valuetype>
void linkedlist< valuetype >::print ( uint64_t  count) const

Prints out a representation of the first "count" nodes of the linkedlist.

template<class valuetype>
bool linkedlist< valuetype >::remove ( valuetype  value)

Deletes the first linkedlistnode containing "value".

Note that this operation requires a search and is expensive in both execution time and code size.

Returns true on success and false on failure.

template<class valuetype>
bool linkedlist< valuetype >::remove ( linkedlistnode< valuetype > *  node)

Removed linkedlistnode "node" from the linkedlist.

Note that this operation does not require a search and is far less expensive than the remove(value) operation and removeAll().

Returns true on success and false on failure.

template<class valuetype>
bool linkedlist< valuetype >::removeAll ( valuetype  value)

Deletes all linkedlistnodes containing "value".

Note that this operation requires a search and is expensive in both execution time and code size.

Returns true on success and false on failure.