Assignment 2 (100 pts) 
Due Wednesday 1/20 at midnight on Catalyst


Part 1: Templating Your List (25 pts)

  • For this activity, you will need to template your List class.
  • Step 1: Open up your List.h file and add the following line above your definition of the List class:

    template <class listitem> //note I used listitem for the class name here, not the commmon T
    class List {
  • Next, for EACH function in your list, you will need to alter it so it works with generic data. Make changes like so:
    void insert_first(listitem data); //this function now takes in generic data

    listitem get_first(); //this function now returns generic data
  • Alter all remaining functions prototypes inside your List.h to work with generic listitems, as show above.
  • Next, you will need to alter the functions inside your List.cpp file that we wrote for Part 1 of the Lab.
  • For EACH of these functions, you will need to template them and change the type of data that they return and take in so that it is generic.
  • Here is an example of how to alter one of these functions:

template <class listitem> //Step 1: template the function
void List<listitem>::insert_first(listitem data) //step 2 & 3: List is templated and takes in a generic param
{
    if (size==0)
    {
        first = new Node(data); //note that although data is of a generic type, we use it as before.
        last = first;

    }
    else
    {
        Nodeptr newNode = new Node;
        newNode->data = data;
        newNode->nextnode = first;
        first = newNode;
    }
    size++;
}

  • Now, build your List.cpp file and correct any errors that the compiler is giving you.
  • Important: Now copy and paste your main function inside of List.cpp, at the very bottom.
  • Alter any calls to your List constructor to specify that the list contains ints, by placing the word int inside of the <>. Please see below:

int main()
{
    List<int> L; //indicate the list holds ints
    L.insert_first(5);
}

  • Now, compile and run your code and verify that it works identically to the previous version without templates
  • Once you are sure it is still working properly, try testing your list with different types of data.
  • For example, make lists of strings, doubles, chars.
  • When you are certain all is working as it should, cut and paste your main function back inside ListTest.cpp, removing it from List.cpp
  • Important: If you compile and run your code now (with your main function inside of ListTest.cpp), your code may not work.
  • To solve this problem, you must cut and paste all of the code from your List.cpp and place it inside your List.h file. This code will go at the very bottom, outside of and below the List class definition. 
  • Compile and run your code again and make sure it is working.

Part 2: Creating a Doubly-Linked List (75 pts)
  • Your assignment is to alter the list that you wrote in class and lab to be a doubly-linked list.
  • The principle difference between the singly-linked list that you wrote in class and a doubly-linked list is that each node contains a pointer both to the next node and to the previous node in the list.
  • You can visualize a doubly-linked list likes so:

Image source.

  • Therefore, your inner Node struct will look like the following:


        struct Node
        {
            listitem data;
            Node* nextnode;
            Node* previousnode;

            Node(): nextnode(NULL), previousnode(NULL){}
            Node(listitem newdata): nextnode(NULL), previousnode(NULL), data(newdata){}
        };

        typedef struct Node* Nodeptr;

  • Additionally, bear in mind that the first Node of the list now has a previousnode pointer to NULL while the last Node has a nextnode pointer to NULL.
  • The advantage of the previous pointer is the ease with which we can traverse the list in both directions.
  • To account for the presence of this additional pointer, you will need to make updates to your code for many of the list operations.
  • Most of these updates are as simple as adding one line of code per function.
  • For example, let's look at the insert_first operation:

template <class listitem>
void List<listitem>::insert_first(listitem data)
{

    if (size==0)
    {
        Nodeptr newNode = new Node(data);
        first = last = newNode;
    }
    else
    {
        Nodeptr newNode = new Node(data);
        newNode->nextnode = first;
        first->previousnode = newNode; //Need to update the previous pointer of first
        first = newNode;
    }
    size++;
}

  • Important! Each time you update one of your functions, run your tests again to make sure your list is still working properly.
  • If you want more information on doubly-linked lists, you can watch this short video (4.5 min).


Required List Operations

  • Your doubly-linked list needs to be able to perform all of the same operations as your singly linked list.
  • Note: The only function that behaves differently between the doubly and singly linked list is the delete_current function. Please see below for more information.


Constructors:

constructor: constructs a new linked list object.
copy constructor: makes a copy of the list object
destructor: frees the memory associated with the linked list

Manipulation Procedures:


begin: moves the iterator to the head of the list
delete_current: removes the element currently pointed to by the iterator <<--- Different from singly-linked
insert_current: inserts an element at the position currently pointed to by the iterator
insert_last:
inserts an element at the end of the list

remove_last: removes the element at the end of the list
insert_first: inserts an element at the beginning of the linked list
remove_first: removes the element at the beginning of the list
scroll: moves the iterator up by one node  

Access Functions:

get_last: returns the last element
is_empty: tests whether the linked list is empty
get_first: returns the first element
off_end: returns whether the iterator is off the end of the list
get_size:
returns the current size of the list
get_current: returns the element currently pointed at by the iterator
==: returns whether this list is equal to another list <-- See lecture notes from Lesson 4 for this function


Additional Operations:

print: prints the contents of the linked list to the screen


Specifications for Submission
  • Please submit 3 files to Catalyst before Wednesday at midnight:
  1. List.h (header file as created in class - now with all of your full function definitions)
  2. List.cpp (everything commented out)
  3. ListTest.cpp (test file with multiple tests for each function you write - this should be the test file you write, not the one I provide you. Please copy and paste the results of running your test into the comments at the bottom of the file)
  • Important: You must name your files exactly as described above -- List.h, List.cpp and ListTest.cpp -- for full credit
  • Also, your code must compile using gcc. If you are using Visual Studio as your IDE, make sure to compile and run your files using gcc before submitting to make sure they compile and run properly. Note that CodeBlocks on the lab computers compiles with gcc, or you can use another IDE that uses the option to compile with gcc such as Eclipse or you can compile on the command line.
  • You must use NULL, not nullptr
  • Do not assume that you can use anything new from C++11 unless it was specifically provided in class.


How You Will Be Graded:

  • No credit if your List.h file is not identical to the one that was given in class as part of your Activity 2.1, except it should be updated to use templates.
  • Make sure that you test your list thoroughly!
  • I will be running a test file on your list to make sure that it is working correctly. I will provide this test to you before the assignment is due.
  • However, I want you to write your own tests first
  • Full credit if your List passes all of my tests and you correctly templated your List.
    • I will be testing it with a list of strings, chars, doubles, and ints.
  • 75% credit for part 2 if your List passes 75% of my tests.
  • 50% credit for part 2 if your List passes 50% of my tests.
  • and so on...
  • No credit if your List doesn't compile or run using gcc. Make sure to comment out the parts that aren't working (if any) before you submit.
  • Please include a block comment like the following at the top of each file you submit
    (5% deduction if missing these comments)

/**

* Firstname Lastname

* CIS 22C

* NameOfFile.cpp or .h

*/


Test File:

#include <iostream>
#include "List.h"
using namespace std;

int main() {
    List<int> Lint;
    List<char> Lchar;
    List<double> Ldouble;
    List<string> Lstring;

    cout << "Should print 3 error messages below iterator off end in pop_front, pop_back, current: \n";
//will need to test these one-by-one as they should each call the exit() function.
//comment out each one after it has been tested
    Lint.remove_first();
    Lint.remove_last();
    Lint.delete_current();

    Lint.insert_first(5);
    cout << "Should print 5:\n";
    Lint.print();
    Lint.insert_last(6);
    cout << "Should print 5 6:\n";
    Lint.print();
    Lint.begin();
    Lint.insert_current(7);
    cout << "Should print 5 7 6:\n"; //note these should all print on a single line separated by spaces
    Lint.print();

    List<int> Lint2(Lint); //copy constructor
    cout << "Should print 5 7 6:\n";
    Lint2.print();

    cout << "Should print lists are equal: " << endl;
    if (Lint==Lint2)
        cout << "Lists are equal" << endl;
    else
        cout << "Lists are not equal" << endl;

    cout << "Size of list should be 0: "<< Lchar.get_size() << endl;
    Lchar.insert_first('a');
    Lchar.remove_first();
    cout << "Size of list should be 0: "<< Lchar.get_size() << endl;
    cout << "List should be empty. Nothing printed to screen: "<< endl;
    //Should print nothing and move to a new line.
    //Should NOT print an error message or any other message
   
Lchar.print();

    cout << "Should print error message for scroll iterator is off the end of the list: \n";
    Ldouble.scroll();
    cout << "Should print error message that iterator off the end of list in insert: \n";
    Ldouble.insert_current(-8.9); //should not insert this value

    Ldouble.insert_last(8.8);
    Ldouble.insert_last(9.9);
    cout << "Should print 8.8 9.9:\n";
    Ldouble.print();

    cout << "Should print iterator is off the end of the List:\n";
    if(Ldouble.off_end())
    {
        cout <<"Iterator is off end\n";
    }
    else
    {
        cout << "Iterator is not off end\n";
    }
    Ldouble.begin();
    Ldouble.scroll();
    cout << "Should print 9.9:\n";
    cout << Ldouble.get_current() << endl;
    Ldouble.scroll();
    cout << "Should print error message when calling current iterator off end:\n";
    cout << Ldouble.get_current() << endl;
    Ldouble.remove_last();
    cout << "Should print 8.8:\n";
    Ldouble.print();
}