Шаблон отсортированного списка реализован с использованием двусвязного списка

Я работаю над этой программой, где мне нужно написать шаблон отсортированного списка, реализованный с использованием двусвязного списка. Мне предоставлен файл SortedList.cpp, в котором находится основной тестовый стенд. Я должен реализовать шаблон в файле SortedList.h.

Шаблон имеет функцию вставки, удаления и печати, конструктор по умолчанию и большой 3. Скопируйте содержимое функции печати в свой собственный шаблон:

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

Я написал SortedList.h, но когда я сравнил свой вывод с правильным выводом, я обнаружил, что он не совпадает.

Вот SortedList.h:

// SortedList.h list template implemented using doubly linked list.
#ifndef SORTEDLIST_H_
#define SORTEDLIST_H_
# include <iostream>
using namespace std;
// struct defining the node of the linked list
template <typename T>
struct Node {
T data;
Node<T> *next, *pre;
};
// class which defines the linked list
template <typename T>
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

Вывод получаю:

   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

Вот правильный вывод, который я должен получить:

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

Кто-нибудь сможет сказать мне, что я делаю неправильно?

Спасибо