Lab 1: Linked Lists (100 pts)
Due Tuesday, January 16 by 9:20am on Canvas

Before you begin!
  • Install Eclipse for C++ on your home computer (if needed)
    • You are required to use Eclipse for C++ in this class (Yes, really!).
    • You can use the Eclipse installed on lab computers in the ATC for assignments in this class or install it at home.
    • See my tutorial for help installing and creating a new project, and for a trouble shooting guide

Step 1: Project Set Up & Pre and Post Conditions
  • Create a new C++ project in Eclipse named List (Notice the capitalization. Please name it accordingly) by following the instructions in my tutorial.
  • Once you have built and run this project and verified that you get the Hello World message to display, then you will need to add a header file.
  • Right click on your project and add a new header file named List.h (again notice the capitalization). Please refer to the tutorial if you encounter any problems.
  • Copy and paste the following code into your header file between the tags for the #ifndef


#ifndef LIST_H_
#define LIST_H_

#include <cstddef> //for NULL
using namespace std;

class List {

private:
    struct Node {
        int data;
        Node* next;

        Node(int newData){
            data = newData;
            next = NULL;
        }
    };

    Node* first;
    Node* last;
    int length;

public:

    /**Constructors and Destructors*/

    List();
    //Default constructor; initializes and empty list
    //Postcondition:

    ~List();
    //Destructor. Frees memory allocated to the list
    //Postcondition:

    /**Accessors*/

    int getFirst() const;
    //Returns the first data in the list
    //Precondition:

    int getLast() const;
    //Returns the last data in the list
    //Precondition:

    bool isEmpty() const;
    //Determines whether a list is empty.

    int getLength() const;
    //Returns the size of the list

    /**Manipulation Procedures*/

    void removeFirst();
    //Removes the value stored in first node in the list
    //Precondition:
    //Postcondition:

    void removeLast();
    //Removes the value stored in the last node in the list
    //Precondition:
    //Postcondition: 

    void insertFirst (int data);
    //Inserts a new data at the beginning of the list
    //If the list is empty, the new data becomes both first and last
    //Postcondition:

    void insertLast(int data);
    //Inserts a new data at the end of the list
    //If the list is empty, the new data becomes both first and last
    //Postcondition:
   
    /**Additional List Operations*/

    void printList() const;
    //Prints to the console the value of each data in the list sequentially
    //and separated by a blank space
    //Prints nothing if the list is empty
    //Prints a empty newline character if it's empty..
};
#endif /* LIST_H_ */


  • Update the comments for each prototype by filling in the pre and postconditions.
    • Remember that preconditions indicate what conditions must be met BEFORE the user calls the function. The function will not work properly unless the preconditions are met.
    • Postconditions indicate what will be the result of the function call. In other words, what conditions will exist after the function is called.
    • See class notes from Thursday on pre and postconditions for some examples and further explanation.
    • You can also watch these short video explanations of pre and postconditions here and here (in Java but ideas still the same)
  • Next, right click the project folder and add two new source files to the project - one called List.cpp and one called ListTest.cpp.
  • You will write all of your functions in List.cpp and test them in ListTest.cpp.
  • You will be using ListTest.cpp to test your functions as you write them in Step 2 of this lab.
  • Copy and paste the below starter code into ListTest.cpp:


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

int main() {
/*
    //instantiate two lists for testing purposes
    List L1;
    List L2;

    //Testing insertFirst() and printList()
    cout << "**Testing InsertFirst**\n\n";
    cout << "Should print out an empty line: \n";
    L1.printList(); //Should not print any message to the screen, just an empty line

          
    L1.insertFirst(0);
    cout << "Should print out 0 and then move to a new line: \n";
    L1.printList();
   
    for (int i = 1; i <= 10; i++) { //inserting the the values 1-10 into L1
        L1.insertFirst(i);
    }

    cout << "Should print out 10 9 8 7 6 5 4 3 2 1 0 and then move to a new line: \n";
    L1.printList();

   
*/
}


  • Note that the starter code is commented out. You can uncomment it after you have written your constructor, printList and insertFirst functions.
  • Once these three functions are working, you should write your next function, and then immediately test it in ListTest.cpp. After you write each function, test your function before you move on to write the next function.


Step 2: Linked List Operations 


  • For this lab, you are going to write the following constructors:
      1. Constructor (not the copy constructor)
      2. Destructor
  • You will also write the following list access functions:
  1. getFirst()
  2. getLast()
  3. getLength()
  4. isEmpty()
  • Additionally, you will write the following manipulation procedures:
  1. insertFirst()
  2. insertLast()
  3. removeFirst()
  4. removeLast()
  • You will also write the following "additional list operation:"
  1. printList()



Self Check:
  • You should now have three files:List.h, List.cpp, ListTest.cpp
  • List.h contains the class definition and prototypes
  • List.cpp contains the function definitions
  • ListTest.cpp is where you will test all of your functions (i.e. call them to see if they are working as intended)

Default Constructor
  • For the default constructor, our goal is simply to initialize the fields inside the list class with a starting value.
  • We have 3 fields inside our list class:
    • Node* first
    • Node* last
    • int length
  • What are the appropriate default values for each of these fields?

List::List() {
    first = NULL;
    last = NULL;
    length = 0;
}


Destructor

  • A destructor is a special member function of a class. The destructor is called at the end of the object's life to free its resources. 
  • In C++ the compiler creates a destructor for a class implicitly, so it is not always necessary to write your own.
  • However, in some cases the implicitly-created destructor is insufficient.
  • TIP: As a rule-of-thumb, any time that you allocate memory dynamically using the word new, you are going to need to write your own destructor (call delete on this dynamic memory).
  • For more information about new, delete and dynamic memory, see the link here
  • Note that inside of a our List class we will be calling the Node constructor to create new nodes, e.g:
Node* N = new Node(5);
  • Notice the use of new in the statement above, indicating that we are allocating memory dynamically.
  • We will be allocating memory dynamically each time we add a new Node into the List.
  • The destructor generated by the compiler will not know to free the memory for these Nodes.
  • Thus, we will need to call delete to free this dynamic memory by writing a destructor.
  • The pseudocode for the List destructor is as follows:
  1. Set a temporary Node to point to first (called b below).
  2. Create a temporary Node (called a below) to store the information of the next Node after b
  3. Using a loop, repeatedly advance both a and b, keeping b one Node behind a in the list
  4. Call delete on b (in other words free the node right before a)
  5. Set the current Node b equal to the contents of Node a (let b catch up to a)
  6. Stop the loop when b goes off the list (no more nodes left to delete)
List::~List()
{
    Node* b = first;
    Node* a = NULL; //a stands for "after" (i.e. after b)
    while (b != NULL)
    {
        a = b->next; //move a to node after b
        delete b; //remove b (you know it is not NULL from if)
        b = a; //b "catches up" with a (both point to same place in list)
    }
}
  • Note that destructors are easy to recognize as they always have a ~ in front of the class name.
  • Make sure you understand: Why do I need both the a and b Nodes here?
  • Hint: Draw out the sequence of events in the above function. Will it work properly to free memory in list?



Additional List Operations - The printList() Function

  • The printList() function is a VERY IMPORTANT function and should be one of the very first that you write.
  • Why?
    • You should be testing your code as you go along, and if you cannot print out the contents of the list, you will be unable to determine whether your functions are working properly, as you will not be able to display any changes to the List after each function is called.
  • Therefore, we are going to skip to writing the print function next.
  • Additionally, the printList function is important because it determines how you are going to display the list information to your user.
  • For example, are you going to display it with [ ] and a , separating each piece of data, like so: [1,2,3,4]?
  • Are you going to display each piece of data on its own line or simply separated by a blank space?
  • For the purposes of this Lab, we will simply have the data items displayed on a single line, each separated by a blank space.
  • We will also have the list print to the console rather than a file, as we are mainly using the print function for debugging purposes in this exercise.
  • The idea behind the print function is straightforward:
  1. Create a temporary iterator to point to the first
  2. Using a loop, print the data for the current node
  3. Advance the temporary iterator
  4. Stop the loop when the iterator has gone off the end of the List
  • For this lab, fill in the 2 missing lines of code below to complete the printList function.
  • Note: Please do not cout any additional messages when the list is empty

void List::printList() const
{
    Node* temp = first; //create a temporary iterator
    while (temp != NULL) {

        //Add two lines of code here

        //Hint: One statement should contain a cout

    }
    cout << endl; //What does this do?

}


Manipulation Procedure: insertFirst

  • Now let's write the insertFirst function so we can start adding data to our list.
  • Remember that insertFirst inserts a new Node IN FRONT OF the first node in the list each time it is called, effectively creating a new front of the list.
  • Therefore, if I were to call insertFirst(6); and then call insertFirst(4); 4 will be the data at the start of the list after those two calls.
  • We need to consider two cases here:
  1. The list is empty
  2. The list has one or more Nodes
  • Why do I need to treat the empty List differently?
  • Remember: when writing your List procedures, it is very important to take into account the "edge" cases, such as an empty list.
  • If the List is empty, we simply need to make a new Node and then ensure that both the first and last pointers point to this new Node. After all, if there is just a single Node in the list, this Node is both first and last node of the list.
  • However, if there is already one or more Nodes in the list, we will need to adjust the first pointer to point to this new Node and also set the new Node's next pointer to point to the former first node of the list.
  • The pseudocode is as follows:
  1. If the list is empty,
    1. Create a new Node 
    2. Set first and last to point to this Node.
  2. Otherwise:
    1. Create a new Node
    2. Set the next pointer of the new Node to point to the beginning of the list
    3. Set the first pointer to point to the new Node
  3. Increment the length of the list (this will happen in either case)
Image representing the actions of insertFirst

Depiction of insertFirst. Notice how insertFirst requires updating the pointer of the first node to point to the new node and the new node to point to the former first node of the list. The red arrows and lightening bolts indicate the updated pointers after calling the function.


void List::insertFirst(int data)
{
    Node* N = new Node(data);
    if (length == 0)
    {
        first = N;
        last = N;
    }
    else
    {
        N->next = first;
        first = N;
    }
    length++;
}
  • Now, test your function. See the Testing your list section below.
  • Make sure to test the edge case : insertion when the List is empty
  • Also test the general case: insertion when the List has one or more elements in it
  • For these test you can simply uncomment the starter code in ListTest.cpp.


Manipulation Procedure: insertLast

  • Write the insertLast function.
  • Hint: it should be similar to insertLast, but not identical.
  • Hint 2: Don't simply update some of the names, but think about what is happening, using the diagram below to help yourself.
  • Which pointers will need to be updated?
  • You might try re-drawing the diagram on a sheet of paper and then manually updating the necessary arrows.
  • When you are finished, test your function inside of main
  • See the Testing your list section below.
  • Make sure you test both cases


Manipulation Procedure: removeFirst

  • Now let's write the removeFirst function so we can remove data from the list.
  • Remember that removeFirst removes the data at the front of the list. After a call to removeFirst, the second node in the list will now become the first.
  • We will temporarily handle the precondition using a print statement, until we cover assertions next lecture
  • We need to consider three cases here:
  1. The list is empty <-- nothing to remove
  2. The list has only one node
  3. The list has more than one node
  • Why do I need to treat a List with one node differently?
  • The pseudocode is as follows:
  1. If the list is empty,
    1. print a message to the user that there is nothing to remove
  2. If the list has one node
    1. Call delete on the first node to deallocate its memory
    2. Return the list to its empty state, where first and last are Null and the length is 0
  3. If the list has more than one node
    1. Create a temp node to temporarily store a pointer the first node
    2. Advance the first pointer to point to the second node in the list (i.e. first->next)
    3. Call delete on the temp node to deallocate its memory
    4. decrement the length of the list
  • The below image depicts the third case of removeFirst, where there are multiple nodes in the list.
Image depicting the actions of removeFirst

  • Below is the code for removeFirst:
void List::removeFirst()
{
    if(length == 0)
    {
        cout << "removeFirst : List is empty, no data to remove." << endl;
        return;
    }
    else if(length == 1)
    {
        delete first;
        first = last = NULL;
        length = 0;
    }
    else
    {
        Node* temp = first;
        first = first->next;
        delete temp;
        length--;
    }
}
  • Now, make sure you test all three cases (if, else if, and else) in ListTest.cpp


Manipulation Procedure: removeLast

  • Write the removeLast function.
  • Hint: it should be similar to removeFirst, but not identical.
  • Make sure you test all three cases.
  • However, removeLast is trickier to write than removeFirst as there is no easy way to access the second to last node in the list. Do you see why?
  • I have written part of removeLast below to help you get started.

void List::removeLast()
{
    if (????){

        //fill in the line here

    } else if (???) {

        //fill in the missing lines here

    } else {
        Node* temp = first;
        while(temp->next != last) //move temp to second to last node in list
        {
            temp = temp->next;
        }
        delete last;
        last = temp; //set last to be the former second to last node stored in temp
        last->next = NULL; //set pointer to point at NULL rather than deallocated memory

        length--;

    }

}

Writing the List Access Functions


  • Access functions provide information about the current state of the data structure.
  • Access functions typically have preconditions that we must account for as part of the function. We will discuss this concept more during the next class.
  • For this lab, you do not need to worry about handling the preconditions in your code.


Access Function: isEmpty

  • Writing access functions is generally pretty straightforward, involving just a few lines of code at most.
  • For example, let's look at the isEmpty() function, whose purpose is to return whether the list is empty using a boolean.
  • This function doesn't require a precondition. It is thus possible to write this function in a single line of code.
  • Here is the pseudocode:
  1. Return the whether the length is 0


bool List::isEmpty() const
{
    return length == 0;
}

  • Now test this function. You should test it twice as there are two possible cases. What are they?


getLength()

  • Given the code for empty above, now try to write the getLength function.
  • This function can also be written in just one line of code.
  • Its purpose is to return the current length of the list.
  • Now test this function. Try writing a test for when the list is empty and when it is not. Note that when the list is empty getLength should simply return 0.


getFirst()

  • The purpose of the getFirst access function is to return the data value that is currently stored at the first of the list.
  • Below is a partial version of this function.
  • It does not take into account the precondition when the List is empty.
  • We will discuss how to handle this precondition during the next class.
  • At that time, we will add some code to this function.
  • For now, you can use this version:

int List::getFirst() const
{      
    
return first -> data;


         }
  • Now test this function. What possible cases might there be? What will happen if the precondition is violated?

getLast()
  • Given the example above, it is your job to write the getLast function and test it properly.


Specifications for Submission
  • Please submit 3 files to Canvas before Tuesday's class:
  1. List.h (Header file given above with pre and post conditions filled in)
  2. List.cpp (File you created for this lab with your List functions)
  3. ListTest.cpp (Test file for each function you write. ALL functions must be tested here at least twice for full credit!!)
  • Important: You must name your files exactly as described above -- List.h, List.cpp and ListTest.cpp -- for full credit
    • -10 points for incorrect naming
  • Also, your code must compile using gcc on Eclipse for C++. Make sure to compile and run your files using Eclipse before submitting to make sure they compile and run properly. Note that Eclipse is now on the lab computers with a gcc compiler installed.
  • Note that you can find tutorials for installing Eclipse on Windows and Mac and for creating new C++ projects on my tutorials page here
  • You must use NULL, not nullptr


How You Will Be Graded:
  • You will receive 25 points for providing a test file that fully tests each function. Do not simply copy and paste my example test file. IMPORTANT: You must add to this file or I will deduct 25 points.
    • Also: You must copy and paste the results of running your tests into the comments at the bottom of this file
  • You will receive 25 points for a header file that is fully commented with both pre and post conditions filled in and provides the prototypes for all functions that will ultimately become part of your list. Do not delete any prototypes or add any additional prototypes. Also please do not add/remove any fields to the List class or alter the Node struct in any way (10 point deduction)
  • You will receive 7 points for each correctly written function as specified for this lab. These functions must be a working part of a List class that is written in the List.cpp file.
  • Stop! Did you read the comments for each function to make sure your function does exactly what the comments describe? Make sure before you submit!