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

Public Member Functions

 singlylinkedlist ()
 
 ~singlylinkedlist ()
 
void prepend (valuetype value)
 
void prepend (singlylinkedlistnode< valuetype > *node)
 
void append (valuetype value)
 
void append (singlylinkedlistnode< valuetype > *node)
 
void insertAfter (singlylinkedlistnode< valuetype > *node, valuetype value)
 
void insertAfter (singlylinkedlistnode< valuetype > *node, singlylinkedlistnode< valuetype > *newnode)
 
void moveAfter (singlylinkedlistnode< valuetype > *node, singlylinkedlistnode< valuetype > *nodetomove)
 
void detach (singlylinkedlistnode< valuetype > *node)
 
bool remove (valuetype value)
 
bool removeAll (valuetype value)
 
bool remove (singlylinkedlistnode< valuetype > *node)
 
uint64_t getLength () const
 
singlylinkedlistnode< valuetype > * getFirst ()
 
singlylinkedlistnode< valuetype > * getLast ()
 
singlylinkedlistnode< valuetype > * getNext (singlylinkedlistnode< valuetype > *node)
 
singlylinkedlistnode< valuetype > * find (valuetype value)
 
singlylinkedlistnode< valuetype > * find (singlylinkedlistnode< 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 singlylinkedlist< valuetype >

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

Each singlylinkedlist is composed of a series of singlylinkedlistnodes. Each singlylinkedlistnode contains a value.

This class is similar to the linkedlist class but uses less memory and many of its operations are faster.

However, the move, detach and remove operations are much slower. If your application must run these operations regularly, you should consider using the linkedlist class instead.

Constructor & Destructor Documentation

◆ singlylinkedlist()

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

Creates an empty instance of the singlylinkedlist class.

◆ ~singlylinkedlist()

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

Deletes this instance of the singlylinkedlist class and all of its singlylinkedlistnodes. Note however, that the data stored in each singlylinkedlistnode is not deleted by this call.

Member Function Documentation

◆ append() [1/2]

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

Creates a new singlylinkedlistnode containing "value" and appends it to the singlylinkedlist.

◆ append() [2/2]

template<class valuetype >
void singlylinkedlist< valuetype >::append ( singlylinkedlistnode< valuetype > *  node)

Appends already created singlylinkedlistnode "node" to the singlylinkedlist.

◆ clear()

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

Deletes all singlylinkedlistnodes currently in the singlylinkedlist. Note however, that the data stored in each singlylinkedlistnode is not deleted by this call.

◆ detach()

template<class valuetype >
void singlylinkedlist< valuetype >::detach ( singlylinkedlistnode< valuetype > *  node)

Detaches "node" from the list.

Note that this operation requires a search and is expensive in both execution time and code size. Consider using the linkedlist class.

◆ find() [1/2]

template<class valuetype >
singlylinkedlistnode<valuetype>* singlylinkedlist< valuetype >::find ( valuetype  value)

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

◆ find() [2/2]

template<class valuetype >
singlylinkedlistnode<valuetype>* singlylinkedlist< valuetype >::find ( singlylinkedlistnode< valuetype > *  startnode,
valuetype  value 
)

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

◆ getFirst()

template<class valuetype >
singlylinkedlistnode<valuetype>* singlylinkedlist< valuetype >::getFirst ( )

Returns the first node in the singlylinkedlist.

◆ getLast()

template<class valuetype >
singlylinkedlistnode<valuetype>* singlylinkedlist< valuetype >::getLast ( )

Returns the last node in the singlylinkedlist.

◆ getLength()

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

Returns the number of nodes in the singlylinkedlist.

◆ getNext()

template<class valuetype >
singlylinkedlistnode<valuetype>* singlylinkedlist< valuetype >::getNext ( singlylinkedlistnode< 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.

◆ heapSort()

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

Sorts the singlylinkedlist 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 singlylinkedlist< valuetype >::insertAfter ( singlylinkedlistnode< valuetype > *  node,
valuetype  value 
)

Creates a new singlylinkedlistnode containing "value" and inserts it into the singlylinkedlist after "node".

◆ insertAfter() [2/2]

template<class valuetype >
void singlylinkedlist< valuetype >::insertAfter ( singlylinkedlistnode< valuetype > *  node,
singlylinkedlistnode< valuetype > *  newnode 
)

Inserts already created singlylinkedlistnode "node" into the singlylinkedlist after "node".

◆ insertionSort()

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

Sorts the singlylinkedlist 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 singlylinkedlist< valuetype >::moveAfter ( singlylinkedlistnode< valuetype > *  node,
singlylinkedlistnode< valuetype > *  nodetomove 
)

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

Note that this operation requires a search and is expensive in both execution time and code size. Consider using the linkedlist class.

◆ prepend() [1/2]

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

Creates a new singlylinkedlistnode containing "value" and prepends it to the singlylinkedlist.

◆ prepend() [2/2]

template<class valuetype >
void singlylinkedlist< valuetype >::prepend ( singlylinkedlistnode< valuetype > *  node)

Prepends already created singlylinkedlistnode "node" to the singlylinkedlist.

◆ print() [1/2]

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

Prints out a representation of the linkedlist.

◆ print() [2/2]

template<class valuetype >
void singlylinkedlist< 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 singlylinkedlist< valuetype >::remove ( valuetype  value)

Deletes the first singlylinkedlistnode containing "value".

Note that this operation requires a search and is expensive in both execution time and code size. Consider using the linkedlist class.

Returns true on success and false on failure.

◆ remove() [2/2]

template<class valuetype >
bool singlylinkedlist< valuetype >::remove ( singlylinkedlistnode< valuetype > *  node)

Removed singlylinkedlistnode "node" from the singlylinkedlist.

Note that this operation requires a search and is expensive in both execution time and code size. Consider using the linkedlist class.

Returns true on success and false on failure.

◆ removeAll()

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

Deletes all singlylinkedlistnodes containing "value".

Note that this operation requires a search and is expensive in both execution time and code size. Consider using the linkedlist class.

Returns true on success and false on failure.