In our previous homework, we have developed mystring class that is similar to C++ standard library class string. In this homework, we will develop linkedlist class that is similar to C++ standard library class list, where like vector class we used in homework two list is a template class. However, our linkedlist class is not a template class.
C++ standard library class list is implemented using a doubly linked list. So we will use a doubly linked list to implement the linkedlist class. We have gained some experience in Labs 6 and 7 to manipulate a doubly linked list structure. The Node structure introduced in Labs 6 and 7 can be used as the basic data structures to implement linkedlist. Note that in the labs, we have an element_type that is introduced through typedef and is equivalent to int. We will keep the same set up here.
Since we are going to implement C++ library class list, we need to under- stand the list better. So we will first use list class and see how each member functions that we will implement work, which is similar in spirit to what we have done in lab 4 before we implement the string class. Then we will replace list
Understand class, member function and field, constructor, operator overloading as member functions or basic functions, memory management, doubly linked list, and C++ list class. To gain experience and understanding related to how a complex and useful class such as C++ list may be designed and implemented using basic C++ language features, data structures, and algorithms.
Since we have had several experience of using the .cpp and .h files in previ- ous Labs and Homework, for this assignment we will have a single file, where the code that belongs to the .h file will be after the #include statements and typedef element_type int statement; the code that belongs to the .cpp file then follows; finally the main function.
In the design, the Node structure should be part of the linklist, that is it is introduced inside the class as private stuff. Since struct is a class where all its members are public, so we will have a class inside another class here. To really mimic the list, we also need a iterator class inside linklist class. However, the design and implementation of iterator class and related methods will not be part of this homework. You will get extra credit if you implement them!
The linkedlist class has the following public methods and types (these are also called interface), the behavior of which is the same as in the list class: See image.
Since iterator class is not part of the homework, we will have the following additional public methods that are not in C++ list: See image.
For those who are interested in the extra credit of adding the iterator, linkedlist will have additional public methods that are same as C++ list See image.
The iterator class need to at least overload the dereference operator * (re- ferring to elem of the Node), increment operator ++ (next node in the linked list), and decrement operator – (previous node in the linked list). The iterator class is another class introduced inside the linkedlist class.
Complete the declaration of linkedlist, the implementation of the linkedlist, before main function in the main.cpp file. In the main function, first use C++ list member functions to be implemented (you are welcome to try other member functions as well), then test linkedlist in a similar way and test other member functions of linkedlist not in C++ list.
In the main program, demonstrate the functionalities of the implemented func- tions or operators to be similar to that of list class.
A short report about things observed and things learned and understood. The report should also describe the test cases used in the main program and the reasons for each test case selected. Properly document and indent the source code. The source code must include the author name and as well as a synopsis of the file.