use this code for the double link list
( The material is Data structure )
( The material is Data structure )
( The material is Data structure )
# include <iostream>using namespace std;template <class T>class node { public: node *prev; T value; node *next; node(node *p, T v, node *n) { prev = p; value = v; next = n; } ~node() { cout << “node destroyed: “<<value<<endl; }};template <class T>class DLL { node<T> *tail, *head;public: DLL(); ~DLL(); void addToHead(T v); void addToTail(T v); void deleteHead(); void deleteTail(); void print(); bool DeleteNode(T val); void append(DLL &l2); void insertInOrder(T v); void MergeInOrder(DLL<T>& l2); bool Search(T v) { node<T> *p = head; while (p!=NULL) { if (p->value == v) return true; p = p->next; } return false; } void duplicate(DLL<T>& l2) { node<T> *p = head; while (p != NULL) { T v = p->value; if (l2.Search(v)) { node<T> *newNode = new node<T>(p, v, p->next); if (p != tail) { p->next->prev = newNode; p->next = newNode; } else { p->next = newNode; tail = newNode; } p = p->next; } p = p->next; } } void clear() { node<T> *temp = head; while (temp != NULL) { head = head->next; delete temp; temp = head; } head = tail = NULL; } void AddTwoLists(DLL<T> & l2, DLL<T> & R) { node<T> *p1, *p2; p1 = head; p2 = l2.head; while (p1!=NULL) { T v1 = p1->value; T v2 = p2->value; R.addToTail(v1 + v2); p1 = p1->next; p2 = p2->next; } }};template <class T>void DLL<T>::MergeInOrder(DLL<T>& l2){ DLL<T> l3; node<T> *p1, *p2; p1 = head; p2 = l2.head; while (p1 != NULL || p2!=NULL) { if (p1 == NULL) { l3.addToTail(p2->value); p2 = p2->next; } else if (p2==NULL) { l3.addToTail(p1->value); p1 = p1->next; } else if (p1->value < p2->value) { l3.addToTail(p1->value); p1 = p1->next; } else { l3.addToTail(p2->value); p2 = p2->next; } } // fill original list with values from l3; clear(); head = l3.head; tail = l3.tail; l3.head = l3.tail = NULL;}template <class T>void DLL<T>::insertInOrder(T v) { // if (head == NULL) { addToHead(v); } else if (head->value >= v) { addToHead(v); } else if(tail->value<= v){ addToTail(v); } else { node<T> * temp = head; node<T> *newNode = new node<T>(NULL, v, NULL); while (temp != NULL) { if (temp->value<v) { temp = temp->next; } else { node<T> *p = temp->prev; p->next = newNode; newNode->prev = p; newNode->next = temp; temp->prev = newNode; break; } } }}template <class T>void DLL<T>::append(DLL &l2) { node<T> *t = l2.head; while (t != NULL) { addToTail(t->value); t = t->next; }}template <class T>bool DLL<T>::DeleteNode(T v) { node<T> *temp = head; if (head->value == v) { deleteHead(); return true; } if (tail->value == v) { deleteTail(); return true; } while (temp != NULL) { if (temp->value == v) { node<T> *p = temp->prev; node<T> *n = temp->next; p->next = n; n->prev = p; delete temp; return true; /*temp->prev->next = temp->next; temp->next->prev = temp->prev;*/ } temp = temp->next; } return false;}template <class T>void DLL<T>::deleteHead() { node<T>*t = head; if (head == NULL) return; else if(head==tail){ delete t; head = tail = NULL; } else { head = head->next; delete t; head->prev = NULL; }}template <class T>void DLL<T>::deleteTail() { if (head == NULL) return; else if (head == tail) { delete head; head = tail = NULL; } else { node<T>*t = tail->prev; delete tail; tail = t; tail->next = NULL; }}template <class T>DLL<T>::DLL() { head = tail = NULL;}template <class T>DLL<T>::~DLL() { node<T> *temp = head; while (temp != NULL) { head = head->next; delete temp; temp = head; } head = tail = NULL;}template <class T>void DLL<T>::addToHead(T v) { node<T> *newNode = new node<T>(NULL, v, head); if (head == NULL) { head = tail = newNode; } else { head->prev = newNode; head = newNode; }}template <class T>void DLL<T>::print() { node<T> * t = head; //tail cout << “NULL <–“; while (t != NULL) { cout << t->value << “<=>”; t = t->next; //prev } cout << “NULL n”;}template <class T>void DLL<T>::addToTail(T v) { node<T>* newNode = new node<T>(tail, v,NULL ); if (head == NULL) head = tail = newNode; else { tail->next = newNode; tail = newNode; }}int main() { DLL<int> mylist; mylist.addToTail(5); mylist.addToTail(7); mylist.addToTail(9); /*mylist.addToTail(10); mylist.addToTail(5); mylist.addToTail(5); mylist.addToTail(4);*/ mylist.print(); DLL<int> mylist2; mylist2.addToTail(5); mylist2.addToTail(5); mylist2.addToTail(5); mylist2.print(); DLL<int> list3; mylist.AddTwoLists(mylist2, list3); list3.print(); //mylist.MergeInOrder(mylist2); //mylist.duplicate(mylist2); //mylist.print(); /*mylist.insertInOrder(0); mylist.print(); mylist.insertInOrder(20); mylist.print(); mylist.insertInOrder(5); mylist.print(); mylist.insertInOrder(5); mylist.print();*/ /*DLL<int> mylist2; mylist2.addToTail(11); mylist2.addToTail(12); mylist2.addToTail(13); mylist2.addToTail(14); mylist2.addToTail(15); mylist2.print(); mylist.append(mylist2); mylist.print(); mylist2.print();*/ /*mylist.DeleteNode(1); mylist.print(); mylist.DeleteNode(32); mylist.print(); mylist.DeleteNode(3); mylist.print(); mylist.DeleteNode(5); mylist.print();*/ /* node<int> *newNode = new node<int>(NULL, 1, NULL); cout << newNode->value << endl;*/ system(“pause”); return 0;}
to implement the following functions ( The material isData structure )
(a) (20 points) Write C++ code to implement the voidDLL<T>:: RemoveAllDuplicatesOf (T& x) function, whichdelete all the occurrences of x (but one) in a sorted DLL. Forexample: if the current list is {5 7 7 7 10 15 25 25}, and the x is7, then RemoveAllDuplicatesOf will change the current list to {5 710 15 25 25}. For full credit, your implementation should dosearching efficiently and no use extra space.
(b) (20 points) Update the above function to void DLL<T>::RemoveAllDuplicates() which remove all the duplications from thesorted list. For the above example the current list become { 5 7 1015 25}.
(c) (20 points) Write the member function int DLL<T>::Replace(T&old, T&new) which replace all the occurrences ofold values with new values in the current list. The functionreturns the number of replacements.
(d) (20 points) Write a function DLL[] split(int x, int y) whichsplit the current list into 3 lists: all values less than x, allvalues greater than y and the remaining values. The output shouldbe stored in an array of DLL. The current list is not necessarysorted.
(e)(20 points) Write a main function that tests the abovefunctions
:
please solve it ASAP ?!?! if it needs more details just tell mewhat you exactly need
Expert Answer
Answer to use this code for the double link list ( The material is Data structure ) ( The material is Data structure ) ( The mate…