// The question looks big because I am giving all the stuffs that you will need to do a small portion of it. The answer should actually be small. I only need the task 5-8 of this problem.. This problem has to be done in C++, and strictly follow the instructions. It should run with the main(), and the printlistinfo function provided below.. I am providing the first 4 tasks of this problem so the task 5-8 should compliment, and work with the tasks 1-4. Thanks in advance. Our goal is to make a linked list class.

Singly or doubly linked? We will go with doubly linked. Why? It will simplify issues like how or where to add or remove a given item.

Some of our considerations will be to make it compatible with various C++ features, e.g. the ranged for and the STL (Standard Template Library) algorithms library. Providing begin() and end() methods that return iterators will buy us a lot.

However, we will also provide some functionality that the STL list class does not. After all, this is our class.

Sentinels: I am not specifying whether or not to use sentinel(s). I will leave that up to you. Likely you will choose to do whatever you did back in your data structures course. Please note, that your code will generally be easier to write if you do use sentinels.

Task One

This class will naturally have a private struct Node. If we are constructing a doubly linked list, then the Node type will have not only data and next fields, but also a prior field. Be sure that all fields get properly initialized.

We will start by providing a simple class that supports:

push_back(int data)

pop_back()

front()

back()

size()

An output operator

Note that modifying the list, whether adding or removing, will take a little more work than with a singly linked list. Don't be surprised if you have some segmentation faults...

Test out your functions. You should create a few lists, adding and removing items verifying that the contents are correct. (I have attached some test code. But perhaps you can come up with additional tests!)

Task Two

Now that you have a reliable list class, add the following methods and test them:

push_front(int data)

pop_front()

Task Three

Naturally it is necessary for a list to have clear method. Implement a clear method and test it.

Task Four

It is nice that we can see what's in the list, using the output operator, but we still can't access any of the items, other than the first and the last.

Let's solve that first with an index operator. With that and our size method, we can write a loop to print out the contents of a list, Write another loop to modify the value of each element and finally print out the list again.

Of course those loops are horrendously expensive!

Task Five

Ok, but wouldn't it be cool to be able to use a ranged for? We did that fairly easily when we implemented the Vector class. It will take a bit more work with a list. Why?

First, remember that we need to provide methods begin() and end(), and that their return values have to support, among other things, operator++. That was easy with Vector's because we could just return the address of the first element for begin() and the address just past the last element for end(). However with the Node objects in our list, they are not laid out contiguously as the items in a Vector are. That has the result that incrementing the address of one Node does not take us to the next.

What can we do?

[Heads up, this is a bit of a big one...]

We will create [yet] another type, called an iterator.

Iterators can be really pretty simple. They will need a single field, a Node*. It is possible to also have them "know" what list instance they belong to, but we will leave that out for now.

In addition, iterators should support a few operations:

++ You can stick with just a pre-increment operator, if you like.

-- Again, you can stick with just a pre-decrement operator.

== Iterators will be equal if they are pointing to the same Node.

!=

* The dereference operator.

The Iterator also needs to provide suitable constructor(s).

Copy constructor: While discussing constructors, we should consider the copy constructor. Our iterator type has a pointer to an item, a Node, that exists on the heap. What does that suggest? Not that we need copy control. Why not? Because the iterator does not own the Node. So we will not be doing a deep copy, and in fact do not need to implement a copy constructor. The one the system provides is good enough.

We can't really test or use this class unless we have a way to get hold of an iterator for a list. The main way to do that will be through two methods in our list class begin() and end(). [You may remember that the STL's vector type supports those methods.]

The iterator that the begin method returns will obviously have a pointer to the first Node. What about the iterator returned by end? Given the use cases we have discussed so far, a simple design that can work would be to have the end iterator have a nullptr. We may see later that there could be useful reasons to do otherwise, but this will certainly work for now.

What can we do with our list class now? Repeat the activities you did with the index operator, but this time using iterators.

Task Six

We still haven't done much to justify defining a list, let alone a list class. What's missing?

Provide an insert method for the list class. What should it be passed? The data item, certainly. And how do we know where to put the data item? Also pass in an iterator! Given an iterator for the class it should be easy enough to insert an item. But we first need to agree on where we are going to put something, given the provided iterator. Do we put it before or after?

Well, how will we insert something at the beginning of the list? The only way we have to get there is the method begin() which hands us an iterator pointing at the first item. So if we want to add something to the head of the list using these iterators, we will need to have our insert method insert before the iterator.

Insert should return an iterator to the new item.

One last point!!! The insert code will need to access the Node that the iterator is pointing at. Should iterators have some method to return the Node? Remember that iterators are used by code outside the List class and that code doesn't want to / shouldn't have to know about Nodes. But the List sure does! What's the point? List methods need to be able to know what Node an iterator "points" to. How? One way is to have the iterator class make the List class a friend. Yes, you can make a whole class a friend!

Task Seven

Add an erase method to the class. What should it be passed? Again, an iterator! This time, there isn't any question about "where" to remove, as we will remove the Node that the iterator is pointing to.

Erase should return an iterator to the item that came after the one you erased.

Task Eight

Copy control! Yes, it we should be able to pass a list by value and have that result in a copy. We should also not have to worry about all those Node objects getting lost and creating a memory leak. And it should be possible to assign one list, the source, to another, the target, causing the target to be replaced by a copy of the source.

Implement the usual big three and demonstrate that they work.

//Given functions and main().. The code should run with the main(), the functions and tasks(1-4).. You just have to do tasks 5-8. void printListInfo(List& myList) { cout << "size: " << myList.size() << ", front: " << myList.front() << ", back(): " << myList.back() << ", list: " << myList << endl; }

// Task 8 void doNothing(List aList) { cout << "In doNothing "; printListInfo(aList); cout << endl; cout << "Leaving doNothing "; }

int main() {

// Task 1 cout << " ------Task One------ "; List myList; cout << "Fill empty list with push_back: i*i for i from 0 to 9 "; for (int i = 0; i < 10; ++i) { cout << "myList.push_back(" << i*i << "); "; myList.push_back(i*i); printListInfo(myList); } cout << "=================== "; cout << "Remove the items with pop_back "; while (myList.size()) { printListInfo(myList); myList.pop_back(); } cout << "=================== ";

// Task2 cout << " ------Task Two------ "; cout << "Fill empty list with push_front: i*i for i from 0 to 9 "; for (int i = 0; i < 10; ++i) { cout << "myList2.push_front(" << i*i << "); "; myList.push_front(i*i); printListInfo(myList); } cout << "=================== "; cout << "Remove the items with pop_front "; while (myList.size()) { printListInfo(myList); myList.pop_front(); } cout << "=================== ";

// Task3 cout << " ------Task Three------ "; cout << "Fill empty list with push_back: i*i for i from 0 to 9 "; for (int i = 0; i < 10; ++i) { myList.push_back(i*i); } printListInfo(myList); cout << "Now clear "; myList.clear(); cout << "Size: " << myList.size() << ", list: " << myList << endl; cout << "=================== ";

// Task4 cout << " ------Task Four------ "; cout << "Fill empty list with push_back: i*i for i from 0 to 9 "; for (int i = 0; i < 10; ++i) myList.push_back(i*i); cout << "Display elements with op[] "; for (size_t i = 0; i < myList.size(); ++i) cout << myList[i] << ' '; cout << endl; cout << "Add one to each element with op[] "; for (size_t i = 0; i < myList.size(); ++i) myList[i] += 1; cout << "And print it out again with op[] "; for (size_t i = 0; i < myList.size(); ++i) cout << myList[i] << ' '; cout << endl;

// Task 5 cout << " ------Task Five------ "; cout << "Fill empty list with push_back: i*i for i from 0 to 9 "; myList.clear(); for (int i = 0; i < 10; ++i) myList.push_back(i*i); printListInfo(myList); cout << "Now display the elements in a ranged for "; for (int x : myList) cout << x << ' '; cout << endl; cout << "And again using the iterator type directly: "; for (List::iterator iter = myList.begin(); iter != myList.end(); ++iter) { cout << *iter << ' '; } cout << endl; cout << "WOW!!! (I thought it was cool.) "; // Task 6 cout << " ------Task Six------ "; cout << "Filling an empty list with insert at end: i*i for i from 0 to 9 "; myList.clear(); for (int i = 0; i < 10; ++i) myList.insert(myList.end(), i*i); printListInfo(myList); cout << "Filling an empty list with insert at begin(): " << "i*i for i from 0 to 9 "; myList.clear(); for (int i = 0; i < 10; ++i) myList.insert(myList.begin(), i*i); printListInfo(myList); // ***Need test for insert other than begin/end*** cout << "=================== ";

// Task 7 cout << " ------Task Seven------ "; cout << "Filling an empty list with insert at end: i*i for i from 0 to 9 "; myList.clear(); for (int i = 0; i < 10; ++i) myList.insert(myList.end(), i*i); cout << "Erasing the elements in the list, starting from the beginning "; while (myList.size()) { printListInfo(myList); myList.erase(myList.begin()); } // ***Need test for erase other than begin/end*** cout << "=================== ";

// Task 8 cout << " ------Task Eight------ "; cout << "Copy control "; cout << "Filling an empty list with insert at end: i*i for i from 0 to 9 "; myList.clear(); for (int i = 0; i < 10; ++i) myList.insert(myList.end(), i*i); printListInfo(myList); cout << "Calling doNothing(myList) "; doNothing(myList); cout << "Back from doNothing(myList) "; printListInfo(myList);

cout << "Filling listTwo with insert at begin: i*i for i from 0 to 9 "; List listTwo; for (int i = 0; i < 10; ++i) listTwo.insert(listTwo.begin(), i*i); printListInfo(listTwo); cout << "listTwo = myList "; listTwo = myList; cout << "myList: "; printListInfo(myList); cout << "listTwo: "; printListInfo(listTwo); cout << "=================== "; } //Tasks 1-4 and the output that should be generated. Tasks1-4 :

#include

#include

using namespace std;

//declaring a structure of node

class LinkedList{

private ://private frilds

struct Node{

int data;

Node* prev;

Node* next;

};

int _size;

Node *head;

Node *tail;

public:

LinkedList()

{

_size=0;

head=NULL;

tail=NULL;

}

//push back method

void push_back(int data){

_size++;//increment the size

//create a location for node on heap

Node *node=(struct Node*)malloc(sizeof(struct Node));

//initialise the node

node->data=data;

node->prev=NULL;

node->next=NULL;

//list is empty

if(head==NULL)

{

head=node;

tail=node;

}

else{

//list is not empty

tail->next=node;

node->prev=tail;

tail=node;

}

}

void pop_back()

{

if(head==NULL)

{//list is empty

cout<<"NOTHING TO POP:THE LIST IS EMPTY!"<

return;

}

else if(head==tail)

{

//only one element

free(tail);//free the node

tail=NULL;

head=NULL;

}

else{

//more than one element

tail=tail->prev;

free(tail->next);

tail->next=NULL;

}

_size--;//decrementing the list size

}

//return pointer to first node

Node* front()

{

return head;

}

//return pointer to tail node

Node* back()

{

return tail;

}

//return list size

int size()

{

return _size;

}

//printing the linked list

void printList()

{

//print all the elements of the list

Node *trav=head;//a trav. node

while(trav!=NULL)//while there are nodes in the list

{

cout<data<<" ";

trav=trav->next;//point the trav to next node

}

cout<

}

//information about the list

friend void listInfo(LinkedList *list)

{

cout<<"SIZE: "<_size<<" FRONT : ";

if(list->front()==NULL)

cout<<"NULL";

else

cout<front()->data;

cout<<" BACK: ";

if(list->back()==NULL)

cout<<"NULL";

else

cout<back()->data;

cout<<" LIST: "<

}

//overload << operator

friend ostream &operator<<(ostream &output,LinkedList *list)

{

Node *trav=list->head;

while(trav!=NULL)

{

output<data<<" ";

trav=trav->next;

}

output<

return output;

}

//push at front of the list

void push_front(int data)

{

_size++;//increment the size of the list

Node *node=(struct Node*)malloc(sizeof(struct Node));//make memory reserve for node

//initialise the node

node->data=data;

node->prev=NULL;

node->next=NULL;

if(head==NULL)

{//no element

head=node;

tail=node;

}

else{//atleast one element

node->next=head;

head->prev=node;

head=node;

}

}

//pop fromfront method

void pop_front()

{

if(head==NULL)

{

//no element in list

cout<<"NOTHING TO POP:THE LIST IS EMPTY!"<

return;

}

else if(head==tail)

{

//only one element to pop

free(tail);//free the node

tail=NULL;

head=NULL;

}

else{

//more than one element in the list

Node *temp=head;

head=head->next;

head->prev=NULL;

free(temp);//free the removed node's memory from heap

}

_size--;//decrementing the list size

}

//add to all method, to add an inetegerto all the elements in the list

void addToAll(int add)

{

Node *trav=head;

while(trav!=NULL)

{

trav->data=trav->data+add;

trav=trav->next;

}

}

//clear the list method

void clear()

{

while(front()!=NULL)

pop_front();

}

};

//main method

int main()

{

LinkedList *list=new LinkedList();

//TASK 1

cout<<"--------------TASK 1------------"<

for(int i=0;i<=9;i++)

{

list->push_back(i*i);

listInfo(list);

}

cout<<"----------------------"<

cout<<"----------------------"<

cout<<"Remove the items with POP_BACK()"<

for(int i=0;i<=9;i++)

{

listInfo(list);

list->pop_back();

}

cout<

cout<<"Fill emptylist with push_front() from i*i for i-> 0,9"<

for(int i=0;i<=9;i++)

{

list->push_front(i*i);

listInfo(list);

}

cout<<"----------------------"<

cout<<"----------------------"<

cout<<"Remove items with pop_back()"<

for(int i=0;i<=9;i++)

{

listInfo(list);

list->pop_back();

}

cout<

cout<<"Fill emptylist with push_back() from i*i for i-> 0,9"<

for(int i=0;i<=9;i++)

{

list->push_back(i*i);

listInfo(list);

}

cout<<"NOW CLEAR"<

list->clear();

listInfo(list);

//list->printList();

cout<<"--------------------------"<

cout<<"--------------------------"<

cout<

cout<<"Fill emptylist with push_back() from i*i for i-> 0,9"<

for(int i=0;i<=9;i++)

{

list->push_back(i*i);

}

//list->printList();

cout<<"adding 1 to each element"<

list->addToAll(1);

list->printList();

cin.get();

return 0;

}

Output :

------Task One------ Fill empty list with push_back: i*i for i from 0 to 9 myList.push_back(0); size: 1, front: 0, back(): 0, list: 0 myList.push_back(1); size: 2, front: 0, back(): 1, list: 0 1 myList.push_back(4); size: 3, front: 0, back(): 4, list: 0 1 4 myList.push_back(9); size: 4, front: 0, back(): 9, list: 0 1 4 9 myList.push_back(16); size: 5, front: 0, back(): 16, list: 0 1 4 9 16 myList.push_back(25); size: 6, front: 0, back(): 25, list: 0 1 4 9 16 25 myList.push_back(36); size: 7, front: 0, back(): 36, list: 0 1 4 9 16 25 36 myList.push_back(49); size: 8, front: 0, back(): 49, list: 0 1 4 9 16 25 36 49 myList.push_back(64); size: 9, front: 0, back(): 64, list: 0 1 4 9 16 25 36 49 64 myList.push_back(81); size: 10, front: 0, back(): 81, list: 0 1 4 9 16 25 36 49 64 81 =================== Remove the items with pop_back size: 10, front: 0, back(): 81, list: 0 1 4 9 16 25 36 49 64 81 size: 9, front: 0, back(): 64, list: 0 1 4 9 16 25 36 49 64 size: 8, front: 0, back(): 49, list: 0 1 4 9 16 25 36 49 size: 7, front: 0, back(): 36, list: 0 1 4 9 16 25 36 size: 6, front: 0, back(): 25, list: 0 1 4 9 16 25 size: 5, front: 0, back(): 16, list: 0 1 4 9 16 size: 4, front: 0, back(): 9, list: 0 1 4 9 size: 3, front: 0, back(): 4, list: 0 1 4 size: 2, front: 0, back(): 1, list: 0 1 size: 1, front: 0, back(): 0, list: 0 ===================

------Task Two------ Fill empty list with push_front: i*i for i from 0 to 9 myList2.push_front(0); size: 1, front: 0, back(): 0, list: 0 myList2.push_front(1); size: 2, front: 1, back(): 0, list: 1 0 myList2.push_front(4); size: 3, front: 4, back(): 0, list: 4 1 0 myList2.push_front(9); size: 4, front: 9, back(): 0, list: 9 4 1 0 myList2.push_front(16); size: 5, front: 16, back(): 0, list: 16 9 4 1 0 myList2.push_front(25); size: 6, front: 25, back(): 0, list: 25 16 9 4 1 0 myList2.push_front(36); size: 7, front: 36, back(): 0, list: 36 25 16 9 4 1 0 myList2.push_front(49); size: 8, front: 49, back(): 0, list: 49 36 25 16 9 4 1 0 myList2.push_front(64); size: 9, front: 64, back(): 0, list: 64 49 36 25 16 9 4 1 0 myList2.push_front(81); size: 10, front: 81, back(): 0, list: 81 64 49 36 25 16 9 4 1 0 =================== Remove the items with pop_back size: 10, front: 81, back(): 0, list: 81 64 49 36 25 16 9 4 1 0 size: 9, front: 64, back(): 0, list: 64 49 36 25 16 9 4 1 0 size: 8, front: 49, back(): 0, list: 49 36 25 16 9 4 1 0 size: 7, front: 36, back(): 0, list: 36 25 16 9 4 1 0 size: 6, front: 25, back(): 0, list: 25 16 9 4 1 0 size: 5, front: 16, back(): 0, list: 16 9 4 1 0 size: 4, front: 9, back(): 0, list: 9 4 1 0 size: 3, front: 4, back(): 0, list: 4 1 0 size: 2, front: 1, back(): 0, list: 1 0 size: 1, front: 0, back(): 0, list: 0 ===================

------Task Three------ Fill empty list with push_back: i*i for i from 0 to 9 size: 10, front: 0, back(): 81, list: 0 1 4 9 16 25 36 49 64 81 Now clear Size: 0, list: ===================

------Task Four------ Fill empty list with push_back: i*i for i from 0 to 9 Display elements with op[] 0 1 4 9 16 25 36 49 64 81 Add one to each element with op[] And print it out again with op[] 1 2 5 10 17 26 37 50 65 82

------Task Five------ Fill empty list with push_back: i*i for i from 0 to 9 size: 10, front: 0, back(): 81, list: 0 1 4 9 16 25 36 49 64 81 Now display the elements in a ranged for 0 1 4 9 16 25 36 49 64 81 And again using the iterator type directly: 0 1 4 9 16 25 36 49 64 81 WOW!!! (I thought it was cool.)

------Task Six------ Filling an empty list with insert at end: i*i for i from 0 to 9 size: 10, front: 0, back(): 81, list: 0 1 4 9 16 25 36 49 64 81 Filling an empty list with insert at begin(): i*i for i from 0 to 9 size: 10, front: 81, back(): 0, list: 81 64 49 36 25 16 9 4 1 0 ===================

------Task Seven------ Filling an empty list with insert at end: i*i for i from 0 to 9 Erasing the elements in the list, starting from the beginning size: 10, front: 0, back(): 81, list: 0 1 4 9 16 25 36 49 64 81 size: 9, front: 1, back(): 81, list: 1 4 9 16 25 36 49 64 81 size: 8, front: 4, back(): 81, list: 4 9 16 25 36 49 64 81 size: 7, front: 9, back(): 81, list: 9 16 25 36 49 64 81 size: 6, front: 16, back(): 81, list: 16 25 36 49 64 81 size: 5, front: 25, back(): 81, list: 25 36 49 64 81 size: 4, front: 36, back(): 81, list: 36 49 64 81 size: 3, front: 49, back(): 81, list: 49 64 81 size: 2, front: 64, back(): 81, list: 64 81 size: 1, front: 81, back(): 81, list: 81 ===================

------Task Eight------ Copy control Filling an empty list with insert at end: i*i for i from 0 to 9 size: 10, front: 0, back(): 81, list: 0 1 4 9 16 25 36 49 64 81 Calling doNothing(myList) List(List) In doNothing 0 1 4 9 16 25 36 49 64 81 Leaving doNothing ~List() Back from doNothing(myList) size: 10, front: 0, back(): 81, list: 0 1 4 9 16 25 36 49 64 81 Filling listTwo with insert at begin: i*i for i from 0 to 9 size: 10, front: 81, back(): 0, list: 81 64 49 36 25 16 9 4 1 0 listTwo = myList List::op=(List) myList: size: 10, front: 0, back(): 81, list: 0 1 4 9 16 25 36 49 64 81 listTwo: size: 10, front: 0, back(): 81, list: 0 1 4 9 16 25 36 49 64 81 =================== ~List() ~List()