// Template doubly linked list class using code from // Data Structures and Algorithms in C++, Goodrich, Tamassia, and Mount, 2nd Ed., 2011. // #pragma once #include  using namespace std; template  class DLinkedList; // forward declaration to be used when declaring DNode template  class DNode { // doubly linked list node private: E elem; // node element value DNode *prev; // previous node in the list DNode *next; // next node in the list friend class DLinkedList; // provide SLinkedList access }; template  class DLinkedList { // a doubly linked list public: DLinkedList(); // empty list constructor ~DLinkedList(); // destructor bool empty() const; // is list empty? E& front(); // get front element E& back(); // get back element void addFront(const E& e); // add to front of list void addBack(const E& e); // add to back of list void removeFront(); // remove from front void removeBack(); // remove from back int size() const; // list size private: // local type definitions int n; // number of items DNode* header; // header sentinel DNode* trailer; // trailer sentinel protected: void add(DNode* v, const E& e); // insert new node before v void remove(DNode* v); // remove node v }; template  DLinkedList::DLinkedList() { // constructor n = 0; // initially empty header = new DNode; // create sentinels trailer = new DNode; header->next = trailer; // have them point to each other trailer->prev = header; } template  bool DLinkedList::empty() const // is list empty? { return (header->next == trailer); } template  E& DLinkedList::front() // return front element { if (empty()) throw length_error("empty list"); return header->next->elem; } template  E& DLinkedList::back() // get back element { if (empty()) throw length_error("empty list"); return trailer->prev->elem; } template  DLinkedList::~DLinkedList() { // destructor while (!empty()) removeFront(); // remove all but sentinels delete header; // remove the sentinels delete trailer; } template  void DLinkedList::add(DNode* v, const E& e) { DNode* u = new DNode; // create a new node for e u->elem = e; u->next = v; // link u in between v u->prev = v->prev; // ...and v->prev v->prev->next = u; v->prev = u; n++; } template  void DLinkedList::addFront(const E& e) // add to front of list { add(header->next, e); } template  void DLinkedList::addBack(const E& e) // add to back of list { add(trailer, e); } template  void DLinkedList::remove(DNode* v) { // remove node v DNode* u = v->prev; // predecessor DNode* w = v->next; // successor u->next = w; // unlink v from list w->prev = u; delete v; n--; } template  void DLinkedList::removeFront() // remove from font { if (empty()) throw length_error("empty list"); remove(header->next); } template  void DLinkedList::removeBack() // remove from back { if (empty()) throw length_error("empty list"); remove(trailer->prev); } template  int DLinkedList::size() const { // list size return n; } 

c) Write the following new member function for the DLinkedList class. The member function must swap the first and second data nodes (not the sentinels) in the linked list (other data nodes stay as they are). Throw an exception if the list has fewer than two elements. Your code should go in only the indicated space (in DLinkedList.h) - do not change any other code.

template

void DLinkedList::swapFirstAndSecond(){

// YOUR CODE TO SWAP NODES GOES HERE

}

Test that your code works by again printing out the front of the list in your main function after calling lyrics.swapFirstAndSecond().

a) Draw a sketch of a doubly linked list specifically of dassDuinkeduistin Dunkedusth containing the first four words of your faworite song done word ineach node). Make sure to show the DLinkedList object, all node objects, and all objects' data members and pointers. b) Complete the following main function to create your linked list above (Your code should go in only the indicated space do not change any other code). include Kiost ream> f include f include DL inked List using name space std; int main D LinkedList lyrics; YOUR CODE TO cREATE THE LIST GoES HERE cout lyrics front endli