a) Draw a sketch of a doubly-linked list, specifically of class DLinkedList in DLinkedList.h, containing the first four words of your favorite song (one word in each 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

#include

#include "DLinkedList.h"

using namespace std;

int main()

{

DLinkedList lyrics;

// YOUR CODE TO CREATE THE LIST GOES HERE

cout

}

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().

Include a screen capture of the output of your program

 DLinkedList.h // 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; }