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=std::cout) 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...

ListNode *	split (ListNode *start, int splitPoint)
	Helper function to split a sequence of linked memory at the node splitPoint steps after start. More...

ListNode *	merge (ListNode first, ListNode second)
	Helper function to merge two sorted and independent sequences of linked memory. More...

ListNode *	mergesort (ListNode *start, int chainLength)
	Sorts a chain of linked memory given a start node and a size. More...

Private Attributes
ListNode *	head_
	The head of the List. More...

ListNode *	tail_
	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

◆ List() [1/2]

template<class T >

List< T >::List

Default List constructor.

Creates an empty List.

See also: List.hpp

◆ List() [2/2]

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

other The list we are copying.

◆ ~List()

template<typename T >

List< T >::~List

Destroys the current List.

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

Member Function Documentation

◆ _copy()

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

other The List to be copied.

◆ _destroy()

template<typename T >

void List< T >::_destroy

private

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

Todo:: Graded in mp_lists part 1

◆ begin()

template<typename T >

List< T >::ListIterator List< T >::begin

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

◆ empty()

template<class T >

bool List< T >::empty

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.

◆ end()

template<typename T >

List< T >::ListIterator List< T >::end

Returns a ListIterator one past the end of the List.

◆ insertBack()

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

ndata The data to be inserted.

Todo:: Graded in mp_lists part 1

◆ insertFront()

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

ndata The data to be inserted.

Todo:: Graded in mp_lists part 1

◆ merge()

template<class 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

first	The starting node of the first sequence.
second	The starting node of the second sequence.

Returns: The starting node of the resulting, sorted sequence.

◆ mergesort()

template<class 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

start	Starting point of the chain.
chainLength	Size of the chain to be sorted.

Returns: A pointer to the beginning of the now sorted chain.

◆ mergeWith()

template<class T >

void List< T >::mergeWith ( List< T > & otherList )

Merges the given sorted list into the current sorted list.

Parameters

otherList List to be merged into the current list.

◆ operator=()

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

rhs	The right hand side of the assignment statement.

◆ print()

template<class T >

void List< T >::print ( ostream & os = std::cout ) const

Used to print the list.

Const because it promises not to modify the current List.

See also: List-given.hpp

Parameters

os	Output stream to print the list to (e.g. cout)

◆ reverse() [1/2]

template<class T >

void List< T >::reverse ( )

Reverses the current List.

◆ reverse() [2/2]

template<class 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

startPoint	A pointer reference to the first node in the sequence to be reversed.
endPoint	A pointer reference to the last node in the sequence to be reversed.

◆ reverseNth()

template<class 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

n	The size of the blocks in the List to be reversed.

◆ size()

template<class T >

int List< T >::size

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.

◆ sort()

template<typename T >

void List< T >::sort

Sorts the current list by applying the Mergesort algorithm.

◆ split() [1/2]

template<typename T >

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

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

Parameters

splitPoint Point at which the list should be split into two.

Returns: The second list created from the split.

◆ split() [2/2]

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

start	The node to start from.
splitPoint	The 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!

This function is also called by the public split() function located in List-given.hpp

Parameters

start	The node to start from.
splitPoint	The number of steps to walk before splitting.

Returns: The starting node of the sequence that was split off.

Todo:: Graded in mp_lists part 1

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 part 1

Reverses the current List.

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

startPoint	A pointer reference to the first node in the sequence to be reversed.
endPoint	A pointer reference to the last node in the sequence to be reversed.

Todo:: Graded in mp_lists part 2

Reverses blocks of size n in the current List. You should use your reverse( ListNode * &, ListNode * & ) helper function in this method!

Parameters

n	The size of the blocks in the List to be reversed.

Todo:: Graded in mp_lists part 2

Merges the given sorted list into the current sorted list.

Parameters

otherList List to be merged into the current list.

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

first	The starting node of the first sequence.
second	The starting node of the second sequence.

Returns: The starting node of the resulting, sorted sequence.

Todo:: Graded in mp_lists part 2

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

Called by the public sort function in List-given.hpp

Parameters

start	Starting point of the chain.
chainLength	Size of the chain to be sorted.

Returns: A pointer to the beginning of the now sorted chain.

Todo:: Graded in mp_lists part 2

◆ waterfall()

template<class 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.

Member Data Documentation

◆ head_

template<class T >

ListNode* List< T >::head_

private

The head of the List.

May be NULL if the List is empty.

◆ length_

template<class T >

int List< T >::length_

private

The length of the current List.

Do not forget to update it!

◆ tail_

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:

base/src/List.h
base/src/List-given.hpp
base/src/List.hpp

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<class T> class List< T >

Constructor & Destructor Documentation

◆ List() [1/2]

◆ List() [2/2]

◆ ~List()

Member Function Documentation

◆ _copy()

◆ _destroy()

◆ begin()

◆ empty()

◆ end()

◆ insertBack()

◆ insertFront()

◆ merge()

◆ mergesort()

◆ mergeWith()

◆ operator=()

◆ print()

◆ reverse() [1/2]

◆ reverse() [2/2]

◆ reverseNth()

◆ size()

◆ sort()

◆ split() [1/2]

◆ split() [2/2]

◆ waterfall()

Member Data Documentation

◆ head_

◆ length_

◆ tail_

template<class T>
class List< T >