Welcome to Week 2!

Learning Objectives

By the end of today's class, you should know...

  • How to handle preconditions when writing your access functions for the List 
  • What is an iterator and how is it used as part of the linked list class
  • The difference between a deep and shallow copy
  • How to write a copy constructor


Announcements
  • Quiz 1 on Thursday
    • Answer 6 questions in 10 minutes
    • Will need to write simple linked list function(s) and answer conceptual questions from content of Lesson 1-3
    • From video "Things Top Performing Students Know...", what is the best way to study for this quiz?
  • Please check in with me at break if you are still waiting to get in the class


Review Activity
  • What are the advantage of a linked list compared to an array?
    • An array compared to a linked list?
  • With a partner, write the insertLast function for the linked list.
  • What might be the precondition for this function: getLast()?
  • Is the getLast() function an access function, manipulation procedure or constructor?


The List Iterator

  • So far, the List class we have written has not been very functional.
  • We have only been able to insert data at the beginning and end of the List, but not in the middle.
  • We have only been able to access data at the beginning and end of the List, but not in the middle.
  • We need an iterator!


Iterators

  • An iterator is a special pointer that allows us to traverse a container.
  • The list iterator is a Node pointer that allows us to traverse the nodes in our List.
  • Our list iterator can move from one node to the next in the list.
  • It can thus be used to access data in the middle of the list or insert (and remove) data in the middle of the list.
  • The list iterator will be useful not only to us as the programmers, but to the users of our list.
  • Therefore, we need to write special functions to control the iterator.


The List Iterator and Its Functions

  • Let's add to our class definition to include an iterator as one fields of the list class.

class List
{

private:
         ...
       Node* first;
       Node* last;    
       Node* iterator;
       int length;
}
  • We then initialized it to be NULL inside of our default constructor

List::List(){

    first = NULL;

    last = NULL;

    iterator = NULL;

    length = 0;

}

  • Notice that the iterator is just a pointer to a Node. We will be moving this pointer around the List, which will allow us to access and manipulate the interior nodes.
  • We will need functions to define the behavior of the iterator.
  • These operations are as follows:
startIterator: moves the iterator to the beginning of the list
removeIterator: removes the element currently pointed to by the iterator
getIterator: returns the element currently pointed at by the iterator
insertIterator: inserts an element after the node currently pointed to by the iterator
             advanceIterator: moves the iterator up by one node towards the last node
              reverseIterator: moves the iterator back one node towards the first node
             offEnd: returns whether the iterator is off the end of the list, i.e. pointing to NULL

Writing the startIterator Function
  • After the List constructor is called, the iterator is defined as being "off the end of the List" (i.e. pointing to NULL).
Image depicting a linked list with an iterator that is off end

In the above image, the iterator is considered to be "off the end" of the List.

  • As we add and remove elements in our list using functions such as insertFirst or insertLast, the position of the iterator should NOT change.
  • In fact, the ONLY way that the iterator should "move onto" the List (i.e. point at a node in the List), is when a call is made to the startIterator function.
  • The purpose of the startIterator function is to make the iterator point to the first node of the List.
  • The user can call this function whenever he or she wishes to return the iterator to the beginning of the List.
  •  It is implemented as follows:
void List::startIterator()
{
    iterator = first;
}

  • We can visualize the effect of this function with the below diagram (compared to the diagram above).
image depicting a linked list after calling startIterator function (iterator point to first)

With a Partner Discuss
  • How would you write the following 3 functions:
    • getIterator: returns the element currently pointed at by the iterator
    • advanceIterator: advances the iterator by one node in the List
    • offEnd: returns whether or not the iterator is off the end of the List, i.e. NULL
  • Which of the above 2 functions have preconditions?
    • What are the preconditions and why?

   


Class Activity: Writing getIterator, advanceIterator and offEnd
  • Open your List.h, List.cpp and ListTest.cpp from your Lab 1
  • Add the startIterator function as provided in the notes above.
  • Now, write the above three functions.
  • Make sure to test each function inside your ListTest.cpp file.
  • For example:
int main() {

    List L; //calling the default constructor

    L.insertFirst(5);
    L.insertLast(8);
    L.insertFirst(2);

    cout << "The list should contain: 2 5 8:" << endl;
    L.printList();
    cout << endl;
   
    cout << "Iterator should be off the end of the list" << endl;
    if (L.offEnd())
        cout << "Iterator is off the end of the list" << endl;
    else
        cout << "Iterator is not off the end of the list" << endl << endl;

    L.startIterator();
    cout << "The data at the first node is 2: " << L.getIterator() << endl;
    L.advanceIterator();
    cout << "The data in the second node is 5: " << L.getIterator() << endl;
    L.advanceIterator();
   
cout << "The data at the last node is 8: " << L.getIterator() << endl << endl;

           cout << "Iterator should NOT be off the end of the list" << endl;
    if (L.offEnd())
        cout << "Iterator is off the end of the list" << endl;
    else
        cout << "Iterator is not off the end of the list" << endl << endl;

    L.advanceIterator();   
cout << "Iterator should be off the end of the list" << endl;
    if (L.offEnd())
        cout << "Iterator is off the end of the list" << endl;
    else
        cout << "Iterator is not off the end of the list" << endl;
    
    return 0;


}


List Access Functions & Their Preconditions


  • Access functions provide information about the current state of the data structure.
  • For example, the following access function tells us whether the list is currently empty:

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

  • Access functions typically have preconditions that we must account for as part of the function.
  • We will look at how to handle preconditions in the following section.


Handling Preconditions When Writing Access Functions

  • Recall that preconditions specify what conditions must exist for a function to be executed
  • Often, access functions will have preconditions.
  • For example, the getBegin function cannot return a value for the data stored at the first node, if the list is empty.

int getFirst();
//Returns the first element in the list
//Precondition: the list cannot be empty
  • But, what should be done when the precondition is violated?
  • Our functions must handle violated preconditions, as these situations arise often.
  • Let's examine several approaches and select the best one:
Option 1: Alert the user to this situation, by printing an error message
  • For example, for the getFirst() function:

if (isEmpty())
    cout << "getFirst(): List is empty. No first element." << endl;

  • Thus, the function would now be written as follows:
int List::getFirst() const
{
    if (isEmpty()){
        cout << "getFirst(): List is empty. No first element" << endl;
        //What is wrong with this approach???
    
    } else {
            return first -> data;
        }
    }
  • If we write the function as above, the compiler should complain to us. Why?
    • If the precondition is not met, the function will not return a value.
    • There is no return statement inside the if
    • This function MUST return a value in either case (if or else).


Option 2: Return a Dummy Value

  • One approach to solve this problem is to return a dummy value such as -1.
int List::getFirst() const
{
    if (isEmpty()){
        cout << "getFirst(): List is empty. No first element" << endl;
        return -1; //What is wrong with this approach???
    
    } else {
            return first -> data;
        }
    }
  • Why might the above approach be a poor one?
    • -1 could be a possible value contained in the List
    • There is no suitable dummy value for a list of integers


Option 3: Print an error message and halt the program using assert

  • I am going to recommend that we use the assert macro to halt our program whenever a precondition is violated.

        assert(length != 0); //#include <assert.h>

  • Calling assert will automatically give us a descriptive error message about what precondition was violated, in which function and on what line number. For example:

Assertion failed: (length != 0), function getFirst, file ../src/List.cpp, line 62.

  • For the getStart function, we could use it like this:
#include <assert.h>
....

int List::getFirst() const
{
assert(!isEmpty());
return first -> data;
}
  • There are problems with this approach as well. However, we are going to use it for the time being.
  • When you take the Advanced C++ Course next quarter, you will learn about exceptions, which are a better approach to handling preconditions that have been violated.


Class Activity: Handling Preconditions for Your List Access Functions

  • Open up your List.h, List.cpp and ListTest.cpp from your Lab 1.
  • For each of the access functions you wrote for your lab, you will need to add code to handle the preconditions.
  • Check with your neighbor if you need help, or raise your hand and ask the instructor.



List Copy Constructor

The Rule of Three

  • For your lab, you had to write the List constructor and default constructor.
  • Now, we are going to write our own copy constructor.
  • There is a famous rule-of-thumb in C++ called The Rule of Three. It specifies that if you explicitly define one or more of the following, you likely need to define all three:
    • constructor
    • copy constructor (Note: we will write the copy constructor next class.)
    • destructor


Copy Constructor
  • Copy constructors are used to create a copy of an existing object.
  • For example, in our linked list class, a copy constructor's job is to create a new list that is an identical copy of the original list.
  • We would call the copy constructor for a linked list by passing in the original list as a parameter:
List copy_list(original_list); //calling the copy constructor
  • In C++, the compiler automatically creates a copy constructor for your class. 
  • This happens for ALL classes that you write, not just the linked list class.
  • However, this default copy constructor will create a shallow copy of the List.


Deep vs Shallow Copies

  • A shallow copy simply sets all fields in the new object equal to the fields in the original object:
//pseudocode
List2.head = List1.head;
List2.tail = List1.tail;
    List2.length = List1.length;

enter image description here

Do you see how shallow copies could result in dangling pointers if one of the lists is deleted but not the other? Image Source

  • The important concept to understand here is that we need to make a deep copy rather than a shallow copy.
  • A deep copy will allocate new memory. This memory will contain a copy of the data in the original list.
  • A shallow copy will simply create new pointers to existing memory.
  • Here our goal is two separate lists containing the same data in the same order.


Why Are Deep Copies Necessary?

  • Let's say that we do not write our own copy constructor and simply call the predefined shallow copy constructor that your compiler automatically generates.
  • In this case, the shallow copy constructor will create new pointers to the first and last of the original list.
  • But, what will happen if I call my destructor on the first list, but not the second one?
  • The second list will be pointing at memory that has been freed, resulting in dangling pointers.
  • Big problem!
  • A deep copy will avoid this problem.
  • The difference between a deep and shallow copy is an important concept, and a favorite question of interviewers!
  • Therefore, if you are having trouble understanding the difference between a deep and shallow copy, I recommend that you watch this video.

With a deep copy, we allocate new memory and then copy the contents of the original object into these new memory locations. Image Source


How to Write a Copy Constructor

  • In C++ the copy constructor follows this standard format:
classname (const classname &obj) {
   // body of constructor
} 
  • Therefore, our copy constructor needs to look like the following:
List::List(const List &list)
{
    //body of constructor
}

  • Above, the variable list is what you are trying to make a copy of.
  • Why is list a constant here?


How to Write the List Copy Constructor

  • Here is the pseudocode for the List copy constructor:


List::List(const List &list): length(list.length)
{

   if(original list is empty)

        make the new list empty

   else
   {

        //Allocate memory for a new first node

        //Copy contents of original first node into new last node

        //Move through both lists with a while loop

        while (next is not NULL)
        {

            //Copy the contents of original node into new node
        }

        Create a node pointer called last to point at the last node in the new list


   }
}


  • Here is the code for the copy constructor. Make sure you understand it.
List::List(const List &list)
{
   

    if(list.first == NULL) //If the original list is empty, make an empty list for this list
    {
        first = last = iterator = NULL;
    }
    else
    {
        first = new Node(list.first->data); //calling Node constructor
        Node* temp = list.first; //set a temporary node pointer to point at the first of the original list
        iterator = first; //set iterator to point to first node of the new list

        while(temp->next != NULL)
        {

            temp = temp->next; //advance up to the next node in the original list
            iterator->next = new Node(temp->data); //using node constructor to create new node w/ copy of data
            iterator = iterator->next; //advance to this new node

        }

        last = iterator; //Why do I need this line of code?
        iterator = NULL;

    }
   

    length = list.length;
}

  • Why do I need to create the temp variable above?


Calling the List Copy Constructor
  • Below is an example of calling the List copy constructor:

int main() {

    List L_original; //calling the default constructor

    L_original.insertFirst(5);
    L_original.insertLast(8);
    L_original.insertFirst(2);

    cout << "The list should contain: 2 5 8:" << endl;
    L_original.printList();

    List L_copy(L_original); //calling the copy constructor to make a copy of the original list
    //Alternately: List L_copy = L_original; will also call copy constructor
    
    cout << "The copy of the list should contain: 2 5 8:" << endl:
    L_copy.printList();

    return 0;

}



Wrap Up

  • With a Partner, answer the questions from our learning objectives

Homework
  • Study for Quiz 1
  • Lab 2 due one week from today


~See You Thursday!~