MP3
Linked Lists
Classes | Public Member Functions | Private Member Functions | Private Attributes | List of all members
List< T > Class Template Reference

List: This is a templated linked list class (meaning it contains data of templated type T, which is a placeholder for a type). More...

#include <List.h>

Collaboration diagram for List< T >:
[legend]

Classes

class  ListNode
 The ListNode class is private to the List class via the principle of encapsulation—the end user does not need to know our node-based implementation details. More...
 

Public Member Functions

 List ()
 Default List constructor. More...
 
 List (const List< T > &other)
 Copy constructor for a List. More...
 
List< T > & operator= (const List< T > &rhs)
 Overloaded assignment operator for Lists. More...
 
int size () const
 Gets the size of the List. More...
 
void print (ostream &os) const
 Used to print the list. More...
 
bool empty () const
 Determines if the current List is empty. More...
 
 ~List ()
 Destroys the current List. More...
 
void insertFront (const T &ndata)
 Inserts a new node at the front of the List. More...
 
void insertBack (const T &ndata)
 Inserts a new node at the back of the List. More...
 
void reverse ()
 Reverses the current List. More...
 
void reverseNth (int n)
 Reverses blocks of size n in the current List. More...
 
void waterfall ()
 Modifies the List using the waterfall algorithm. More...
 
List< T > split (int splitPoint)
 Splits the given list into two parts by dividing it at the splitPoint. More...
 
void mergeWith (List< T > &otherList)
 Merges the given sorted list into the current sorted list. More...
 
void sort ()
 Sorts the current list by applying the Mergesort algorithm. More...
 
ListIterator begin () const
 Returns a ListIterator with a position at the beginning of the List. More...
 
ListIterator end () const
 Returns a ListIterator one past the end of the List. More...
 
template<class Iter >
 List (const Iter &start, const Iter &end)
 

Private Member Functions

void _copy (const List< T > &other)
 Copies the given list into the current list. More...
 
void _destroy ()
 Destroys all dynamically allocated memory associated with the current List class. More...
 
void reverse (ListNode *&startPoint, ListNode *&endPoint)
 Helper function to reverse a sequence of linked memory inside a List, starting at startPoint and ending at endPoint. More...
 
ListNodesplit (ListNode *start, int splitPoint)
 Helper function to split a sequence of linked memory at the node splitPoint steps after start. More...
 
ListNodemerge (ListNode *first, ListNode *second)
 Helper function to merge two sorted and independent sequences of linked memory. More...
 
ListNodemergesort (ListNode *start, int chainLength)
 Sorts a chain of linked memory given a start node and a size. More...
 

Private Attributes

ListNodehead_
 The head of the List. More...
 
ListNodetail_
 The tail of the list. More...
 
int length_
 The length of the current List. More...
 

Detailed Description

template<class T>
class List< T >

List: This is a templated linked list class (meaning it contains data of templated type T, which is a placeholder for a type).

You should not remove anything from this class definition, but you will find it helpful to add your own helper functions to this class, and are encouraged to add to it.

Constructor & Destructor Documentation

template<class T >
List< T >::List ( )

Default List constructor.

Creates an empty List. Implemented for you.

See also
List-given.hpp
template<class T >
List< T >::List ( const List< T > &  other)

Copy constructor for a List.

Since Lists allocate dynamic memory (i.e., they use "new", we must define the Big Three).

See also
List-given.hpp
Parameters
otherThe list we are copying.
template<typename T >
List< T >::~List ( )

Destroys the current List.

This function should ensure that memory does not leak on destruction of a list.

Todo:
Graded in MP3.1

Member Function Documentation

template<class T >
void List< T >::_copy ( const List< T > &  other)
private

Copies the given list into the current list.

See also
List-given.hpp
Parameters
otherThe List to be copied.
template<typename T >
void List< T >::_destroy ( )
private

Destroys all dynamically allocated memory associated with the current List class.

Todo:
Graded in MP3.1
template<typename T >
List< T >::ListIterator List< T >::begin ( ) const

Returns a ListIterator with a position at the beginning of the List.

template<class T >
bool List< T >::empty ( ) const

Determines if the current List is empty.

Const because it promises not to modify the current List.

See also
List-given.hpp
Returns
Boolean value of whether the current List is empty.
template<typename T >
List< T >::ListIterator List< T >::end ( ) const

Returns a ListIterator one past the end of the List.

template<typename T >
void List< T >::insertBack ( const T &  ndata)

Inserts a new node at the back of the List.

This function SHOULD create a new ListNode.

Parameters
ndataThe data to be inserted.
Todo:
Graded in MP3.1
template<typename T >
void List< T >::insertFront ( const T &  ndata)

Inserts a new node at the front of the List.

This function SHOULD create a new ListNode.

Parameters
ndataThe data to be inserted.
Todo:
Graded in MP3.1
template<typename T >
List< T >::ListNode * List< T >::merge ( ListNode first,
ListNode second 
)
private

Helper function to merge two sorted and independent sequences of linked memory.

The result should be a single sequence that is itself sorted.

This function SHOULD NOT create ANY new List objects.

Parameters
firstThe starting node of the first sequence.
secondThe starting node of the second sequence.
Returns
The starting node of the resulting, sorted sequence.
Todo:
Graded in MP3.2
template<typename T >
List< T >::ListNode * List< T >::mergesort ( ListNode start,
int  chainLength 
)
private

Sorts a chain of linked memory given a start node and a size.

This is the recursive helper for the Mergesort algorithm (i.e., this is the divide-and-conquer step).

Parameters
startStarting point of the chain.
chainLengthSize of the chain to be sorted.
Returns
A pointer to the beginning of the now sorted chain.
Todo:
Graded in MP3.2
template<typename T >
void List< T >::mergeWith ( List< T > &  otherList)

Merges the given sorted list into the current sorted list.

Parameters
otherListList to be merged into the current list.
template<class T >
List< T > & List< T >::operator= ( const List< T > &  rhs)

Overloaded assignment operator for Lists.

Part of the Big Three that we must define because the class allocates dynamic memory.

See also
List-given.hpp
Parameters
rhsThe right hand side of the assignment statement.
template<class T>
void List< T >::print ( ostream &  os) const

Used to print the list.

Const because it promises not to modify the current List.

See also
List-given.hpp
Parameters
osOutput stream to print the list to (e.g. cout)
template<typename T >
void List< T >::reverse ( )

Reverses the current List.

template<typename T >
void List< T >::reverse ( ListNode *&  startPoint,
ListNode *&  endPoint 
)
private

Helper function to reverse a sequence of linked memory inside a List, starting at startPoint and ending at endPoint.

You are responsible for updating startPoint and endPoint to point to the new starting and ending points of the rearranged sequence of linked memory in question.

Parameters
startPointA pointer reference to the first node in the sequence to be reversed.
endPointA pointer reference to the last node in the sequence to be reversed.
Todo:
Graded in MP3.1
template<typename T >
void List< T >::reverseNth ( int  n)

Reverses blocks of size n in the current List.

You should use your reverse( ListNode * &, ListNode * & ) helper function in this method!

Parameters
nThe size of the blocks in the List to be reversed.
Todo:
Graded in MP3.1
template<class T >
int List< T >::size ( ) const

Gets the size of the List.

Defined as a const function because it promises not to modify the current List in any way.

See also
List-given.hpp
Returns
The size of the current List.
template<typename T >
void List< T >::sort ( )

Sorts the current list by applying the Mergesort algorithm.

template<typename T >
List< T > List< T >::split ( int  splitPoint)

Splits the given list into two parts by dividing it at the splitPoint.

Parameters
splitPointPoint at which the list should be split into two.
Returns
The second list created from the split.
template<typename T >
List< T >::ListNode * List< T >::split ( ListNode start,
int  splitPoint 
)
private

Helper function to split a sequence of linked memory at the node splitPoint steps after start.

In other words, it should disconnect the sequence of linked memory after the given number of nodes, and return a pointer to the starting node of the new sequence of linked memory.

This function SHOULD NOT create ANY new List objects!

Parameters
startThe node to start from.
splitPointThe number of steps to walk before splitting.
Returns
The starting node of the sequence that was split off.

In other words, it should disconnect the sequence of linked memory after the given number of nodes, and return a pointer to the starting node of the new sequence of linked memory.

This function SHOULD NOT create ANY new List or ListNode objects!

Parameters
startThe node to start from.
splitPointThe number of steps to walk before splitting.
Returns
The starting node of the sequence that was split off.
Todo:
Graded in MP3.2
template<typename T >
void List< T >::waterfall ( )

Modifies the List using the waterfall algorithm.

Every other node (starting from the second one) is removed from the List, but appended at the back, becoming the new tail. This continues until the next thing to be removed is either the tail (not necessarily the original tail!) or NULL. You may NOT allocate new ListNodes. Note that since the tail should be continuously updated, some nodes will be moved more than once.

Todo:
Graded in MP3.1

Member Data Documentation

template<class T>
ListNode* List< T >::head_
private

The head of the List.

May be NULL if the List is empty.

template<class T>
int List< T >::length_
private

The length of the current List.

Do not forget to update it!

template<class T>
ListNode* List< T >::tail_
private

The tail of the list.

May be NULL if the List is empty.


The documentation for this class was generated from the following files: