In this assignment you will be creating a double-linked list (unordered) and an ordered double-linked list. You can will also be updating the phoneBook application to use the ordered linked list.
In part 1 (this part) you will be creating a double-linked list.
You will implement all of the code in file linkedList.h. A starter version of this is included in this assignment. You will be using this linkedList class in parts 2, 3, and 4 of this assignment. The orderedLinkedList class will be created in part 2 and used in parts 3 and 4.
In part 2 you will be creating an ordered linked list. This will not inherit from linkedList, but will use a linkedList to do most of the work for the ordered linked-list. You will be creating all of your code in file orderedLinkedList.h. A starter version of this is included in part 2.
In part 3 you will update your phoneBookEntry class to be used with the orderedLinkedList.
In part 4 you will have to update your assignment 2 code and change the phoneBook to make use of the orderedLinkedList. You will also need the updated phoneBookEntry class from part 3.
Part 1 directions
In this part you will create three classes listNode, linkedList, and linkedListIterator. All of the listNode class and most of the linkedListIterator class has been provided for you. These are all template classes. This started code for the linkedList.h file can be downloaded from zyBooks Linked list (Part 1) .
You can inline the remaining member functions needed for the listNode class. Only inline trivial member functions in the linkedList and ilinkedListIterator classes (trivial being 1 to 5 lines of code).
The non-inline member functions need to be after the class definitions but before the #endif at the end of the linkedList.h file.
Class listNode
The listNode class is similar to the listNode class we used in the linkedList class we created in class (that code is on eLearning).
The linkedList class needs to implement a double linked list. Your program cannot use any existing C++ collections to implement this, you need to create the code from scratch or by adapting the code in the text book. Note the interface for your class will be different from the one used in the text book.
The listNode class is going to make the linkedList and linkedListIterator class friend classes. That way the linkedList and linkedListIterator classes can call the private next and previous member functions that update the next and previous pointers. To make this work we are going to have a forward declaration of the linkedList and linkedListIterator template class. See the sample header file for details.
Class linkedListIterator
Class linkedListIterator has mostly been implemented for you. The iterator is an abstraction of a pointer. There are a number of typedef statements in the class that map words like iterator to the actual class name of linkedListIterator< DataType>. Here are some of the typedef statements from the class:
typedef DataType& reference;
typedef const DataType& const_reference;
typedef DataType* pointer;
typedef const DataType* const_pointer;
typedef linkedListIterator iterator;
typedef const linkedListIterator const_iterator;
So reference is actually an alias for DataType& and const_reference is an alias for const DataType&.
The iterator type we have is a bidirectional iterator, so the operations we can do with an iterator are:
iterator iter = list.begin(); // this is an iterator to the first element in the list
iter is NOT a pointer, it is an instance of a class, but it behaves like a pointer. I can get access to the data in the linked list via:
data = *iter;
The above is the dereference operator, note that linkedListIterator implements this.
We can also move to the next item in the list via prefix or postfix ++
iter++; // get the next item in the list (the 2nd one).
Tote if the iterator iter is invalid it will have a value of list.end(). This is the iterator version of nullptr.
If the data in the list is a class it may have member functions we can call the data's name member function as follows:
iter->name(); // again, the iterator behaves like a pointer, even though it is an instance of a class
or we can do the following:
(*iter).name();
look at the implementation of operator-> in the linkedListIterator class. it simply returns the address of the data. With a bidirectional iterator you can also move to a previous item with the prefix or postfix -- operator.
The operator-- member functions (there are 2) are defined for you but you need to implement them. See the prefix and postfix ++ operators for guidance. The operator== and operator!= need to compare the values pointed to by the iterator, not the data in the nodes.
You can even update a value in the linked list via the iterator.
Assume we have a list of int values and that iter is a valid iterator for an element in the list that has a value of 9:
std::cout << *iter << std::endl;
*iter = 12;
std::cout << *iter << st::endl;
The first cout will output 9 and the second will output 12.
Class linkedList
Note that the member functions that add to the list (push_front, push_back, insert_before and insert_after) take references of type DataType. You need to create a listNode for this and add the listNode to the list.
You have to create the data members in the linkedList class in the linkedList.h file. This includes the first and last node pointers. The starter code calls these firstNode and lastNode. You can either use these names or use your own names. If you use your own names you will have to change the starter code to your new names.
If you push or insert DataType values that contain the same values as other list nodes you will end up with duplicate values in the list. Also note that the list items are not going to be sorted in any way. They are going to be in the order you add them
The erase, pop_front, and pop_back member functions will remove the listNode entry from the list. Make sure you delete the listNode. Do not allow any memory leaks in your program. If the list is empty after the erase or pop_xxxx functions you need to set the first and last pointers to nullptr. Make sure your destructor removes all of the remaining entries from the list.
The push_front, pop_front, push_back, and pop_back member functions need to work if there are no entries in the list. The pushxxxx functions need to add the entry to the list if it is currently empty. The popxxxx functions need to just return when the list is empty.
The insert_before and insert_after member functions need to insert the item into the list based on the iterataor value passed to the insert functions. If the iterator is the end iterator (list.end()), the insert_before member function needs to do a push_front. If the iterator is the end iterator, the insert_after member function needs to do a push_back. Assuming the iterator is a valid item (and not end) the insert_before operation should insert the new list item before the one the iterator refers to. For insert_after the new item is inserted after the one the iterator refers to. Once again we are using the iterator as if it were a pointer, even though it isn't.
Every insertion operation (push_front, push_back, insert_before and insert_after) needs to increment the counter you are using to keep track of the size of the list (size being the number of entries in the linkedList). You have a print member function that takes a std::ofstream & object as a parameter. Use the range based for loop to go through the list of entries and output them with the std::ofstream & parameter. Note this requires that the object in the list be printable with the << operator. Types like int, double and classes like std::string already have this support. If you want your own classes to have this support you need a stand alone function similar to the following:
std::ostream& operator<<(std::ostream &out, const < YourClassGoesHere> &rhs)
{
// write the contents of your class to out using the operator <<
return out;
}
See the sample program "Operator overloading and the myString class" on eLearning for an example of an operator<< implementation.
There are two different versions of the erase member function. The first one returns a value of type bool and takes a const DataType & parameter. If the item exists in the list it will be removed from the list and erase will return true. If the item does not exist the list is unchanged and erase returns false.
The second version of erase is more interesting. This version returns an iterator and takes an interator as a parameter. Note that the syntax of doing this is complex and I have included a dummy member function for you in linkedList.h. Here is the code:
template
typename linkedList< DataType>::iterator linkedList< DataType>::erase(linkedList::iterator iter)
{
}
Note on Visual Studio you may have to code the following (notice two uses of typename):
template< class DataType>
typename linkedList< DataType>::iterator linkedList< DataType>::erase(typename linkedList< DataType>::iterator iter)
{
}
The iterator parameter iter must either be a valid iterator or be equal to list.end() (it is valid if it is an iterator for a valid list item). If iter is not end() the item referred to by iter must be deleted from the list. If the value of iter is end() the erase member function should not remove any item and return end(). The returned iterator must be a new temporary iterator that erase must create. This new iterator will contain the next item in the list after the one being erased. If there are no more items after the one being erased the the iterator for end() should be returned. If the parameter iter is end() the new iterator must be set to end() and returned to the caller.
This logic allows us to do the following:
for (auto iter = list.begin(); iter != list.end(); iter++)
{
if (some_condition_happens)
{
iter = list.erase(iter);
}
}
The erase member functions must reduce the count of the number of entries if an item is actually removed from the list.
The find member function also returns an interator. Here is a dummy entry for it:
template
typename linkedList< DataType>::iterator linkedList< DataType>::find(const DataType &existingItem)
{
}
Your program will need to try and find the existingItem value in the list. If the entry is not in the list your find should return the end() value. Otherwise it should return an interator for the found item.
You will also need to implement the constructors, destructor, assignment operator, and the size and empty member functions.
The size returns the number of entries in the list. This show be a value stored as instance data. You will need to update this counter whenever an item is added to or removed from the list.
The empty member function returns true if there is at least one entry in the list and ``false``` if the list is empty.
The destructor must remove any remaining entries in the list. Don't forget to free up the listNode values.
The member functions being, and end have been written for you. These return back the appropriate iterator objects. There is also a back member function that returns the very last valid item in the list (or end() if there are no entries in the list).
This allows us to do the following (once you have written the prefix and postfix -- operators for the linkedListIterator class.
bool done = false;
for (auto iter = list.back(); !done ; iter--)
{
if (iter != list.end())
{
out << *iter << std::endl;
if (iter == list.begin())
{
done = true;
}
}
}
The copy constructor and assignment operator (operator=) need to do a deep copy. You may want to extract out any common code for these two operations into a private member function you create for your class.
See sample program "Deep copy" on eLearning for an example of a class that uses deep copy.
You should loop for areas of reuse in your program.
For example, you can have your destructor use other member functions to actually delete any remaining entries in the list.
In a similar way the copy constructor and assignment operation do similar operations, Try and reuse that code. Note that the assignment operator actually does more work than the copy constructor since it has to empty out the list being assigned into.
For example:
linkedList list2(list1);
The list2 above is new so it does not yet have any items in it.
On the other hand:
list2 = list1;
The list2 above may have items in it already. These need to be removed before you do the deep copy from list1.
More on the linkedListIterator class
Take a look at the linkedListIterator class. It has one data member a listNode< DataType> * called current.
To create an iterator you pass a listNode pointer on the constructor.
linkedListIterator(listNode< DataType> *current)
: current(current)
{
}
The iterator class is a thin wrapper around a pointer. Note the prefix ++ operator:
iterator operator++()
{
if (current != nullptr)
{
current = current->next();
}
return *this;
}
It "icrements" the iterator by going to the next listNode.
Using this design we can create an abstract pointer type for our list collection and we can use this with a range based for loop:
for (auto elem : list)
{
// do work here
}
The begin() and end() member function and the increment operator are called under the covers to implement the range based for loop.
Approach to development and testing
Do not try and implement everything at once.
Go through and implement stubs for all of the member functions and make sure that compiles. Then implement a member function or two and get those working.
Because some of the class definition has been give you to you will either have to comment out parts of the class until you write the associated member functions or you will have to create stubs for the member functions. Stubs are just enough code for a member function to allow it to compile.
For example, Start by implementing the constructor and test that. Implement the size and empty member functions. Test your program at this point. Create a list, check empty and size and make sure they are working. Also make sure your programming isn't getting an error when it ends.
Then implement push_front . Create your list, use debug to see the output. call pushfront to put something in the list and call debug. Do a couple more of the pushfront / debug calls. Make sure this is all correct before you go to the next step.
Next implement pop_front. Call debug before and after every call to pop_front.
After this is working implement "pushback", and then "popback". Follow that by insert_before and insert_after.
Keep adding additional member functions until you have everything working.
The key here is to write a little code and test and debug it before you move to the next step.
Running the tests
For part 1 I am only going to run unit tests. You will have to upload your assignment3part1.cpp file, but I will not actually be running it.
There are 10 units tests for part 1.
Here is some simple test code to get you started:
#include < iostream>
#include
#include "linkedList.h"
int main()
{
// test push_front followed by pop_front
std::cout << "Create list" << std::endl;
linkedListlist;
std::cout << "Print empty list" << std::endl;
list.debug(out);
std::cout << "push_front(12)" << std::endl;
list.push_front(12);
std::cout << "Print list" << std::endl;
list.debug(out);
std::cout << "push_front(13)" << std::endl;
list.push_front(13);
std::cout << "Print list" << std::endl;
list.debug(out);
std::cout << "push_front(14)" << std::endl;
list.push_front(14);
std::cout << "Print list" << std::endl;
list.debug(out);
std::cout << "pop_front" << std::endl;
list.pop_front();
std::cout << "Print list" << std::endl;
list.debug(out);
std::cout << "pop_front" << std::endl;
list.pop_front();
std::cout << "Print list" << std::endl;
list.debug(out);
std::cout << "pop_front" << std::endl;
list.pop_front();
std::cout << "Print list" << std::endl;
list.debug(out);
return 0;
}
In part 2 you will be creating a new template class orderedLinkedList in file orderedLinkedList.h.
This new class will make use of the linkedList class to implement a sorted linked list.
Since the public interface of the orderedLinkedList is not a superset of the public interface of the linkedList class we are NOT going to use inheritance. Instead we are going to use composition.
The ordering will depend on your DataType class supporting the comparison operators (<, <=, ==, !=, > and >=). This will be used to determine the order the items are being added.
You will create an instance variable in the orderedLinkedList class of type linkedList.
Many of the public member functions in the orderedLinkedList class will have the same signature as those in the linkedList class. Some of the member functions in the linkedList will not be in the orderedLinkedList (such as push_front, pop_front, push_back, push_front. insert_before and insert_after).
For the member functions in orderedLinkedList that map to member functions linkedList you will need to implement the member function in your orderedLinkedList class and then call the equivalent member function for the linkedList instance variable you created for your orderedLinkedList class.
Assume you have an instance variable of type linkedList< DataType> in your orderedLinkedList class called theList. You could implement the print member function as:
template < class DataType>
void orderedLinkedList< DataType>::print(std::ostream &out) const
{
theList.print(out);
}
The insert member function should check and see if the entry being inserted already exists. This is done my checking to see if there is an existing entry equal to the entry being inserted. If it is already in the collection the insert member function should do nothing. You should not end up with duplicate entries in the list.
The starter code for orderedLinkedList is on zyBooks.