COP$4530-0004.$su$24$

Assignment #$1$; Getting started with linked lists

Assignment #$1$; Getting started with linked lists

Due Friday by $11$:$59$pm Points $100$ Submitting a file upload Available until May $28$ at $11$:$59$pm

COP$4530$

ASSIGNMENT #$1$; GETTING STARTED WITH LINKED LISTS

Programming Assignment #$1$

Objective

This assignment will provide practice with a doubly$-$linked list, along with practice on the basic concept of an iterator over a container.

Task

For this assignment you will implement a templated doubly$-$linked list class, along with an associated iterator class for helping with generic list traversals. In a doubly$-$linked list, each node has a pointer to the next node AND a pointer to the previous node. The following starter files are provided for you:

tnode.h $--$ fully defines a templated node class for use in a doubly$-$linked list.

Note that the member data includes a data element, as well as pointers to the

next and previous nodes.

tlist.h $--$ provides the declarations of the template classes TList $($the linked

list class$)$ and TListIterator $($an associated class to help with list traversal$).$

driver.cpp $--$ contains some sample test calls to the linked list, but should not

be considered a complete or thorough set of tests. You will need to create more

test cases to fully test your class features. This driver is provided to help

illustrate some of the basic class features and concepts, including the use of

iterators.

driver$\_$output.txt $--$ contains the output from running the above sample driver

program.

Your job will be to finish this templated set of classes by defining each of the

functions in the TList and TListIterator classes. These should be defined in a file

called: tlist.hpp

Note that there is already a #include at the bottom of tlist.h where your definition

file will be brought in$.$ This illustrates a pretty standard format for setting up a

templated class.

Iterators:

The small class called TListIterator is a helper class that can be used in conjunction

with the linked list class. This is a common feature used in container classes like this.

The purpose of an iterator is to provide a common and non$-$implementation$-$specific

way of traversing a container, so that multiple containers could potentially use

common algorithms $($like sorting and searching functions, for example$).$ This will be

explored more in the course. For the iterator class in this assignment, here is a brief

sample use:

$//$ suppose that L is a linked list storing ints, and it has

$//$ already been populated with the values $3,6,9,12,15,18,21$

$//$ this call would retrieve a list iterator over the container L

TListIterator itr $=$ L$.$GetIterator$()$;

$//$ at this point, itr currently is positioned at the first element in

$//$ the list $($the $3).$

int x $=$ itr.GetValue$()$; $//$ x would now store $3$

itr.Next$()$; $//$ itr has advanced to the $6$

int y $=$ itr.GetValue$()$; $//$ y would now store $6$

itr.Next$()$;

itr.Next$()$; $//$ we have now advanced to the $12$

int z $=$ itr.GetValue$()$; $//$ z now stores $12$

itr.Previous$()$; $//$ now we have moved backwards, to the $9$

int a $=$ itr.GetValue$()$; $//$ a stores $9.$ etc.

This class essentially helps us walk through the linked list in a fairly easy way, with

calls to Next$()$ and Previous$()$ to move around.

Program Details

Here are general descriptions of the two classes you are to define, along with a general

description of each function's task.

$1)$ class TList

The member data of this class consists of pointers to the first and last nodes, a size

variable, and a dummy variable of type T that can be used for error$-$checking situations. Specifically, some of the functions specify to return a stored data item, but if you encounter a situation like an empty list or other situation where there would not BE a valid data item, you can return a reference to the dummy object instead. This is needed because some such functions are pass$-$by$-$reference $($so that the retrieved item can be modified by the caller under normal situations$).$

Function Descriptions:

Default constructor $--$ creates an empty linked list

TList$($T val, int num$)--$ creates a linked list containing "num" copies of the data element "val"

Clear $--$ clear out the list, resetting it to an empty list

Big Five

Destructor $--$ appropriate clean$-$up of list, no memory leaks

Copy constructor $--$ deep copy

Copy assignment operator $--$ deep copy

Move constructor $--$ constructor with standard move semantics

Move assignment operator $--$ assignment with standard move semantics

Accessors

IsEmpty $--$ returns true if the list is empty, false otherwise

GetSize $--$ returns the size $($number of data elements$)$ in the list

GetFirst $--$ returns the data element in the first node $($by reference$)$

GetLast $--$ returns the data element in the last node $($by reference$)$

Note that error situations in the last two functions would occur if the list was

empty $($this what the "dummy" item is for$).$

Endpoint insert$/$removes

InsertFront $--$ insert the dat