Problem Description

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 by linkedlist, and if we implement everything correctly, the code should compile and produce the same results.

Purpose

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.

Design

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.

Implementation

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.

Test and evaluation

In the main program, demonstrate the functionalities of the implemented func- tions or operators to be similar to that of list class.

Report and documentation

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.

Academic Honesty!
It is not our intention to break the school's academic policy. Posted solutions are meant to be used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly complete the form. Please provide a valid email address and we will get back to you within 24 hours. Payment is through PayPal, Buy me a Coffee or Cryptocurrency. We are a nonprofit organization however we need funds to keep this organization operating and to be able to complete our research and development projects.