sorted list template implemented using doubly linked list. C++

I am working on this program where I have to write a sorted list template implemented using doubly linked list. The SortedList.cpp is given to me, which contains the test bed main. I should implement the template in SortedList.h file.

The template has a Insert, Delete and Print Function, a default constructor and the Big 3. Copy the content of the Print function in your own template:

// Implementation of Print function
int i = 1;
Node * p = list;
while ( p != NULL )
{
    cout << "Node " << i << ": " << p->data << endl;
    p = p->next;
    i++;
}

I did write SortedList.h, but when I compare my output with the correct output, I find that it doesn't match.

Here is SortedList.h:

// SortedList.h list template implemented using doubly linked list.

ifndef SORTEDLIST_H_

define SORTEDLIST_H_

include

using namespace std;

// struct defining the node of the linked list

template

struct Node {

T data;

Node<T> *next, *pre;

};

// class which defines the linked list

template

class SortedList {

private:

Node<T> *head;

public:

// default constructor

SortedList<T>()

{

    head = NULL;

}

// fucntion Insert to insert the node at the end of the list

void Insert(T n)

{

    Node<T> *newNode = new Node<T>;

    newNode->data = n;

    newNode->next = NULL;

    newNode->pre = NULL;

    if (head == NULL)

    {

        head = newNode;

    }
    else if (head->data > n)
    {
        Node<T>* temp = head;
        head = newNode;
        newNode->next = temp;
        temp->pre = head;
    }
    else {

        Node<T> *temp = head;
        Node<T> *prev = NULL;
        bool inserted = false;
        while (temp != NULL)

        {
            if (temp->data > n)
            {
                //Node* _temp = temp;
                newNode->pre = temp->pre;

                newNode->next = temp;
                temp->pre = newNode;
                if (newNode->pre != NULL)
                {
                    newNode->pre->next = newNode;
                }

                inserted = true;
                break;
            }
            prev = temp;
            temp = temp->next;

        }
        if (!inserted)
        {
            newNode->pre = prev;

            prev->next = newNode;
        }


    }

}

// function to delete the node with the data n

void Delete(T n)

{

    if (head == NULL)

    {

        return;

    }

    else {

        if (head->data == n)

        {

            Node<T> *temp = head;

            head = head->next;
            if (head != NULL)
                head->pre = NULL;

            delete(temp);

        }
        else {

            Node<T> *temp = head->next;

            while (temp != NULL)

            {

                if (temp->data == n)

                {


                    {
                        temp->pre->next = temp->next;

                        if (temp->next != NULL)

                            temp->next->pre = temp->pre;
                    }
                    Node<T>* toDelete = temp;
                    temp = temp->pre;
                    if (toDelete != NULL)
                        delete(toDelete);

                }

                temp = temp->next;

            }

        }

    }

}

// function to print the list

void Print()

{

    if (head == NULL)

        cout << "\n Empty list ";

    else

    {

        int i = 1;

        cout << "\n List " << endl;

        Node<T> **temp = &head;

        while ((*temp) != NULL)

        {

            cout << " Node " << i << ":" << (*temp)->data << endl;

            temp = &((*temp)->next);

            i++;

        }

    }

}

};

endif /* SORTEDLIST_H_ */

// End of Sorted.h

the Output I get:

1: 2: List 3: Node 1: 4: Node 2: 5: Node 3: 6: Node 4: 7: Node 5: 8: Node 6: 9: Node 7: 10: Node 8: 11: Node 9: 12: Node 10:! 13: Node 11:a 14: Node 12:a 15: Node 13:e 16: Node 14:e 17: Node 15:e 18: Node 16:g 19: Node 17:g 20: Node 18:h 21: Node 19:h 22: Node 20:i 23: Node 21:i 24: Node 22:i 25: Node 23:i 26: Node 24:l 27: Node 25:n 28: Node 26:n 29: Node 27:o 30: Node 28:r 31: Node 29:r 32: Node 30:r 33: Node 31:s 34: Node 32:s 35: Node 33:s 36: Node 34:s 37: Node 35:s 38: Node 36:t 39: Node 37:t 40: Node 38:t 41: Node 39:t 42: Node 40:t 43: Node 41:t 44: Node 42:v 45: Node 43:v 46: Node 44:y 47: Node 45:y 48: Which one do you want to delete? 49: Which one do you want to delete? 50: Which one do you want to delete? 51: Which one do you want to delete? 52: Which one do you want to delete? 53: Which one do you want to delete? 54: 55: List 56: Node 1: 57: Node 2: 58: Node 3: 59: Node 4: 60: Node 5: 61: Node 6: 62: Node 7: 63: Node 8: 64: Node 9: 65: Node 10:! 66: Node 11:e 67: Node 12:e 68: Node 13:e 69: Node 14:g 70: Node 15:g 71: Node 16:h 72: Node 17:h 73: Node 18:l 74: Node 19:n 75: Node 20:n 76: Node 21:o 77: Node 22:r 78: Node 23:r 79: Node 24:r 80: Node 25:s 81: Node 26:s 82: Node 27:s 83: Node 28:s 84: Node 29:s 85: Node 30:t 86: Node 31:t 87: Node 32:t 88: Node 33:t 89: Node 34:t 90: Node 35:t 91: Node 36:v 92: Node 37:v 93: Node 38:y 94: Node 39:y 95: 96: List 97: Node 1:3.14

Here is the correct output I should get:

1: Node 1:
2: Node 2: ! 3: Node 3: a 4: Node 4: e 5: Node 5: g 6: Node 6: h 7: Node 7: i 8: Node 8: l 9: Node 9: n 10: Node 10: o 11: Node 11: r 12: Node 12: s 13: Node 13: t 14: Node 14: v 15: Node 15: y 16: Which one do you want to delete? 17: Which one do you want to delete? 18: Which one do you want to delete? 19: Which one do you want to delete? 20: Which one do you want to delete? 21: Which one do you want to delete? 22: Node 1:
23: Node 2: ! 24: Node 3: e 25: Node 4: g 26: Node 5: h 27: Node 6: l 28: Node 7: n 29: Node 8: o 30: Node 9: r 31: Node 10: s 32: Node 11: t 33: Node 12: v 34: Node 13: y 35: Node 1: 3.14

Would anyone be able to tell me what I am doing wrong?

Thank you