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

◆ linkedlist()

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

Creates an empty instance of the linkedlist class.

◆ ~linkedlist()

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

◆ append() [1/2]

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

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

◆ append() [2/2]

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

Appends already created linkedlistnode "node" to the linkedlist.

◆ clear()

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.

◆ detach()

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

Detaches "node" from the list.

◆ find() [1/2]

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.

◆ find() [2/2]

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.

◆ getFirst()

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

Returns the first node in the linkedlist.

◆ getLast()

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

Returns the last node in the linkedlist.

◆ getLength()

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

Returns the number of nodes in the linkedlist.

◆ getNext()

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.

◆ getPrevious()

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.

◆ heapSort()

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.

◆ insertAfter() [1/2]

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".

◆ insertAfter() [2/2]

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

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

◆ insertBefore() [1/2]

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".

◆ insertBefore() [2/2]

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

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

◆ insertionSort()

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.

◆ moveAfter()

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

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

◆ moveBefore()

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

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

◆ prepend() [1/2]

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

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

◆ prepend() [2/2]

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

Prepends already created linkedlistnode "node" to the linkedlist.

◆ print() [1/2]

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

Prints out a representation of the linkedlist.

◆ print() [2/2]

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

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

◆ remove() [1/2]

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.

◆ remove() [2/2]

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.

◆ removeAll()

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.