Due to the existence of the Previous pointer, we also need to refactor the inserting operation in the LinkedList data type. For the InsertHead() operation, the Previous pointer of the former Head must point to the new Head, so that we can have the new InsertHead() operation as follows:
template <typename T>void DoublyLinkedList<T>::InsertHead(T val){ // Create a new Node DoublyNode<T> * node = new DoublyNode<T>(val); // The current Head will no longer become a Head // so the Next pointer of the new Node will // point to the current Head node->Next = Head; // If the current Head is exist, // the Previous pointer of the current Head // should point to the node if(Head != NULL) Head->Previous = node; // The new Node now ...