template class . DList { friend . class .UnitTests_Lab3; + // .Giving access to test . code struct Node . { // . NOTE: . Values . set . to -1 for unit test . purposes Type data; Node* .next .= reinterpret_cast(-1) ; Node* prev .= reinterpret_cast(-1); Node(const . Type& _data, Node* _next = nullptr, Node* _prev = nullptr) { // . TODO: Implement . this .method 9 3i public: class . Iterator { public: Node* mCurr = reinterpret_cast(-1) ; - Iterator& operator+ +() .{ - 7- // . TODO: Implement . this method Iterator operator++(int) .{ // . TODO: Implement . this method98 99 Iterator& operator--() .{ 100 // . TODO: Implement . this method 101 102 103 104 Iterator operator--(int) { 105 // . TODO: Implement . this method 106 107 108 109 Type& operator*() .{ 110 // . TODO: . Implement . this .method 111 112 113 114 115 bool operator != (const . Iterator& _iter) const .{ 116 return mCurr != _iter . mCurr; 117 118 3; 119 120 // . Data . members 121 // . NOTE: All . values . set to -1 . for unit test . purposes 122 Node* mHead .= reinterpret_cast(-1); 123 Node* mTail .= reinterpret_cast(-1); 124 size_t mSize . =.-1; 125 126 public: 127 128 DList() { 129 // . TODO: Implement . this method 130 131 132~DList() { // . TODO: Implement . this method DList (const . DList& _copy) .{ 7/ . TODO: Implement . this method DList& operator=(const . DList& _assign) { // . TODO: Implement . this method void . AddHead (const . Type& _data) { - 7- // . TODO: Implement . this . method - 7.- void . AddTail (const . Type& _data) { // . TODO: Implement . this method void Clear() { // . TODO: . Implement . this method - - Iterator Insert (Iterator& _iter, const Type& _data) { // . Implement . this method Iterator Erase(Iterator& _iter) { // . TODO: Implement . this .methodIterator Begin () - const { / / . TODO: Implement . this . method Iterator End () . const { // . TODO: Implement . this .methodLinked lists are the next data structure you will be creating. They are a non-contiguous sequence container, and will offer some advantages over vectors/DynArrays, namely a much more efficient way to remove data. You will be creating a doubly-linked list, which allows for bi-directional traversal, as well as a much more efficient way to insert and remove data at any point in the sequence. Because the data is stored non-contiguously, this will require a good understanding of pointers and dynamic allocations. Here is an illustration of a doubly-linked list with 5 nodes (A-E). A -> next B -> next C -> next D -> next E -> next Nothing B Nothing A -> prev B -> prev C -> prev D -> prev E -> prev As you can see, a node is represented by a circle and consists of three components. A pointer leading from it to the next node, one to the previous node, and the data itself stored in each node. The data can be anything from a single integer to an array of chars. Here, the data is a single character (char. A, B, C, etc.) You can also see that the first and last Nodes of a linked list each point to nothing. The pointers still exist in each node-they simply have nothing to point to. This is represented in C++ as a null pointer, or nullptr. To add a node between B and C, you would have to adjust B->next to point to the new node along with C->prev. The new node would also have to have its pointers set to point at B and C as well. i.e. newNode->next and newNode->prev. Linked lists can be hard to mentally visualize. Do not be afraid to diagram out the steps needed to perform the necessary steps needed for the various methods.Things to Review . Dynamic memory . Pointers . Pointers to classes/structs . Structs . Explicitly calling non-default constructors New Topics Advanced usage of pointers . Nested classes/structs Data Members This class has three user-defined types you will be working with. Make sure to familiarize yourself with what data members are in each type, and what they represent. Node data The value being stored (think of the "element" in an array) next A pointer to the next node in the list prev A pointer to the previous node in the listIterator mCurr A Node pointer representing the current position of the iterator DList mHead A pointer to the "front\" Node in the list mTail A pointer to the "hack\" Node 'In the list mSize The current number of Nodes allocated Methods Node Constructor ' Set the data members to the 1\"values of the parameters passed in DLi st Constructor - Set all data members to reect that no nodes are currentlyr allocated AddHead - Dynamically add a Node to the front of the list 0 Update the head to point to the newly added node 0 Update the size of the list - Don't forget to link the nodes together before updating the head AddTail - Dynamically add a Node to the hack of the list - Update the tail to point to the newly added node 0 Update the size of the list - Don't forget to link the nodes together before updating the toil Clear 0 Free up the memoryfor all dynamically allocated nodes 0 Set all of the data members back to their default state 0 Remember there are more nodes than just the head and toil o This will require some form of loop Destructor - Free up the memory for all dynamically allocated nodes (There's o method that does this) Begin - Creates and returns an Iterator that points to the head node End - Creates and returns an Iterator that points to the Node after the last valid node In the list Iterator Pre-Fix Increment [++] - Moves the Iterator to the next node in the list and returns it Iterator Post-Fix Increment (++) . Post-fix operators take in an int to allow the compiler to differentiate Moves the Iterator to the next node in the list and return an Iterator to the original position 3 . This will require a temporary variable Iterator Post-Fix Decrement (--) . Moves the Iterator to the previous node in the list and returns it Iterator Post-Fix Decrement (--) Post-fix operators take in an int to allow the compiler to differentiate . Moves the Iterator to the previous node in the list and return an Iterator to the original position . This will require a temporary variable Iterator Dereference (*) . Return the data of the node the Iterator is pointing toInsert 0 Do not be afraid to diagram this! - Dynamically allocate a Node and insert it in front of the position of the passedin Iterator - There are three special cases for this method, depending on what the Iterator is storing o Empty List ' Iterator will he storing a null pointer, so the list needs to be started ' There's a method to help with this o Head ' Iterator will he storing a pointer to the head of the list ' There's a method to help with this o Anywhere else ' Iterator is storing a pointer to another node {even the tail} ' Link the nodes before and after the inserted nodes ' This will require setting a total of four HEXUPFEV pointers - In all cases, the passedin Iterator should be updated to store the newly inserted node Erase - Do not be afraid to diagram this! Delete the node stored in the passed-in Iterator This will require some pointers to be adjusted before the deletion In most of these cases, a temporary pointer will he required iii. There are four special cases for this method; depending on what the Iterator is storing on Empty List I Iterator will he storing a null pointer ' Since there is nothing to remote the method can he exited :3: Head ' Iterator will be storing a pointer to the head of the list I Will need to update the head pointer CI Tail ' Iterator will be storing a pointer to the tail of the list I Will need to update the tail pointer :21 Anywhere else ' Iterator is storing a pointer to another node ' This will require linking the nodes before and after the node to erase together 0 In all cases, the passedin Iterator should be updated to store the node after the erased node Assignment Operator 1* Assigns all UElUE'S to match those of the object passed in 1* Clean up existing memoryr before the deep copy {There's a method that does this} 4' Deep copy the entire list .3. This requires some type of loop to move through the passedin list :3 took at your other methods, as there are some that can make this Iirery easy ' If the size has not already been updated, shallow copy it Copy Constructor - Creates a copy of the object passed in ' Deep copy the entire list CI This requires some type of loop to mate through the passedin list .3. took at your other methods, as there are some that can make this very easy it If the size has not already been updated, shallow copy it ' Remember that data members are not automatically initialized in C++ 243 244 245 Iterator Begin () . const { 246 return . Iterator (mHead) ; 247 248 249 Iterator End() const { 250 return Iterator (nullptr); 251 252 9% No issues found Ln: 250 Ch: 18 Col: 24 TABS CRLF or List q X ntire Solution * 1 Error 0 Warnings | 0 of 7 Messages 197 Build + IntelliSense Search Error List Code Description Project File Line Suppression State C2440 ' ': cannot convert from 'nullptr' to 'DList alterator' DSA Labs DList.h 250