In a doubly-linked list, individual data elements are stored within a node structure, which contains both a pointer to the next list element as well as another pointer to the previous element in the list. The previous element pointer at the front of the list and the next element pointer at the back of the list are NULL. With such a doubly-linked structure, the list can be traversed towards the back by following the chain of next element pointers, and traversed towards the front by following the chain of previous element pointers.

A doubly-linked list can be visualized as follows:

You must implement the DLinkedList template class to store data of any type; this includes a Node template class implemented for you in the DLinkedList class DLL.h file. Please refer to the documentation in the provided DLL.h file for the class definition and functional requirements.

ElementAt, InsertAt, RemoveAt example

Consider a linked list storing integers:

Front 16- 76-21 -53-back

Demonstrating 0-indexed access, ElementAt (1) returns 76. Likewise, InsertAt (81, 2) will result in the list, where 81 now occupies index 2:

Front 16-76-81 -21-53-back

Subsequently, RemoveAt (0) returns 16 and results in the list:

Front-76-81-21-53-back

Implementing testing and submission

Each of the member function including constructors should be implemented in DLL.cpp file and tested in the DLL_test.cpp the testing should also include at least three data types for int, float, and string

Submit DLL.cpp and DLL_test.cpp to C4

// File: DDL.h // Student name: // Date: // Description: Definition of a doubly-linked-list class using template

#ifndef _DLL_H_ #define _DLL_H_

#include #include #include #include using namespace STD;

// template class for doubly-linked list node template class Node { public: T data; //string data; Node* prev; Node* next;

// default constructor //template Node (T value) { data = value; prev = NULL; next = NULL; } };

// DLinkedList class definition template class DLinkedList { private: // DLinkedList private members int size; // number of items stored in list Node* front; // references to the front Node* back; // and back of the list

// helper function for deep copy // Used by copy constructor and operator= void Copyist (const DLinkedList& ll);

// helper function for deep delete // Used by destructor and copy/assignment void Delete List ();

Public: // default constructor DLinkedList (); // constructor with array argument DLinkedList (T array [], int size); // copy constructor, performs deep copy of list elements DLinkedList (const DLinkedList& ll);

// destructor ~DLinkedList ();

// Print the element data of the list // Output \"The list is empty\" if there is no element void printDLL (); //MUTATORS // Inserts an item at the front of the list // POST: List contains item at position 0 // PARAM: item = item to be inserted void Insert Front (T item);

// Inserts an item at the back of the list // POST: List contains item at back // PARAM: item = item to be inserted void InsertBack (T item);

// Inserts an item in position p (0-indexed) // Throws exception for invalid index // PRE: 0 =>=> // POST: List contains item at position p // PARAM: item = item to be inserted, p = position where item will be inserted void InsertAt (T item, int p);

// Removes and returns an item from position p (0-indexed) // Throws exception if list is empty or index invalid // PRE: 0 => // POST: Item is removed from list // PARAM: p = position from where item will be removed T RemoveAt (int p);

// Removes duplicates from the list, preserving existing order of remaining items. // the first occurrence of any duplicate (relative to the front of the list) // is the one which remains. // we have not yet learned about efficiency so you may implement this in any way // as long as the resulting list satisfies the requirement above. // PRE: // POST: List contains no duplicates, front and back point to the appropriate nodes // PARAM: void Remove Duplicates ();

// ACCESSORS

// Returns size of list int Size () const;

// Returns whether the list is empty bool Is Empty () const;

// Returns existence of item bool Contains (T item) const;

// Returns item at index (0-indexed) // Throws exception for invalid index T ElementAt (int p) const;

// OVERLOADED OPERATORS

// overloaded assignment operator // must work in the following cases: // list2 = list1 -> general case // list2 = list2 -> should do nothing DLinkedList& operator= (const DLinkedList& ll); };

#include \"DLL.cpp\" #endif

------------------------------------------------------------------------

// File: DLL_test.cpp // Student name: // Date: // Description: testing doubly-linked-list class

#include \"DLL.h\" int main () { //In this section you test integer type //In this section you test float type

//In this section you test string type

Return 0; }