Welcome to Week 2!Learning ObjectivesBy 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 classThe difference between a deep and shallow copyHow to write a copy constructorAnnouncementsQuiz 1 on WednesdayAnswer 6 questions in 10 minutesWill need to write simple linked list function(s) and answer conceptual questions from content of Lesson 1-3From 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 classNext Women in Computer Science Club meeting this Wednesday from 12:30-1:30pm in ATC 202This meeting featuring a speaker from Amazon!Review ActivityWhat are the advantage of a linked list compared to an array?An array compared to a linked list?With a partner, write the insertStop function for the linked list.What might be the precondition for this function: getStop()?Is the getStop() function an access function, manipulation procedure or constructor?The List IteratorSo 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!IteratorsAn 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 FunctionsLet's add to our class definition to include an iterator as one fields of the list class.class List {private:         ...       Node* start;       Node* stop;           Node* iterator;       int length; }We then initialized it to be NULL inside of our default constructorList::List(){    start = NULL;    stop = 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 listremoveIterator: removes the element currently pointed to by the iteratorgetIterator: returns the element currently pointed at by the iterator insertIterator: inserts an element after the node currently pointed to by the iterator             moveIterNext: moves the iterator up by one node towards the stop node              moveIterPrevious: moves the iterator back one node towards the start node             offEnd: returns whether the iterator is off the end of the list, i.e. pointing to NULLWriting the startIterator FunctionAfter the List constructor is called, the iterator is defined as being "off the end of the List" (i.e. pointing to NULL).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 insertStart or insertStop, 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 = start;}We can visualize the effect of this function with the below diagram (compared to the diagram above).With a Partner DiscussHow would you write the following 3 functions:getIterator: returns the element currently pointed at by the iteratormoveIterNext: advances the iterator by one node in the ListoffEnd: returns whether or not the iterator is off the end of the List, i.e. NULLWhich of the above 2 functions have preconditions?What are the preconditions and why?    Class Activity: Writing getIterator, moveIterNext and offEndOpen your List.h, List.cpp and ListTest.cpp from your Lab 1Add 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.insertStart(5);    L.insertStop(8);    L.insertStart(2);    cout << "The list should contain: 2 5 8:" << endl;    L.displayList();    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.moveIterNext();    cout << "The data in the second node is 5: " << L.getIterator() << endl;    L.moveIterNext();    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.moveIterNext();    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 PreconditionsAccess 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 FunctionsRecall that preconditions specify what conditions must exist for a function to be executedOften, access functions will have preconditions.For example, the getStart function cannot return a value for the data stored at the first node, if the list is empty.int getStart() const;//Returns the first element in the list//Precondition: the list cannot be emptyBut, 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 messageFor example, for the getStart() function:if (isEmpty())    cout << "getStart(): List is empty. No first element." << endl;Thus, the function would now be written as follows:int List::getStart() const{    if (isEmpty()){         cout << "getStart(): List is empty. No first element" << endl;        //What is wrong with this approach???         } else {            return start -> 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 ifThis function MUST return a value in either case (if or else).Option 2: Return a Dummy ValueOne approach to solve this problem is to return a dummy value such as -1.int List::getStart() const{    if (isEmpty()){         cout << "getStart(): List is empty. No first element" << endl;        return -1; //What is wrong with this approach???         } else {            return start -> data;        }    }Why might the above approach be a poor one?-1 could be a possible value contained in the ListThere is no suitable dummy value for a list of integersOption 3: Print an error message and halt the program using assertI am going to recommend that we use the assert macro to halt our program whenever a precondition is violated.        assert(length != 0); //#include 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 getStart, file ../src/List.cpp, line 62.For the getStart function, we could use it like this:#include ....int List::getStart() const{ assert(!isEmpty()); return start -> 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 FunctionsOpen 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 ConstructorThe Rule of ThreeFor 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:constructorcopy constructor (Note: we will write the copy constructor next class.)destructorCopy ConstructorCopy 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 constructorIn 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 CopiesA shallow copy simply sets all fields in the new object equal to the fields in the original object://pseudocodeList2.head = List1.head;List2.tail = List1.tail;    List2.length = List1.length;Do you see how shallow copies could result in dangling pointers if one of the lists is deleted but not the other? Image SourceThe 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 start and stop 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 SourceHow to Write a Copy ConstructorIn 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 ConstructorHere 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 start node        //Copy contents of original start 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 stop to point at the stop 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.start == NULL) //If the original list is empty, make an empty list for this list    {        start = stop = iterator = NULL;    }    else    {        start = new Node(list.start->data); //calling Node constructor        Node* temp = list.start; //set a temporary node pointer to point at the start of the original list        iterator = start; //set iterator to point to the start 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        }        stop = 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 ConstructorBelow is an example of calling the List copy constructor:int main() {     List L_original; //calling the default constructor    L_original.insertStart(5);    L_original.insertStop(8);    L_original.insertStart(2);    cout << "The list should contain: 2 5 8:" << endl;    L_original.displayList();     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.displayList();     return 0;}Wrap Up With a Partner, answer the questions from our learning objectivesHomeworkStudy for Quiz 1 next classLab 2 due one week from today~See You Wednesday!~