C++

Forum

 
How do I instantiate a templated doubly linked list with strings?

aimh4wk (6)
I'm trying to create a doubly linked list filled with strings. It works with chars and ints but when I create a DLL of type std::string, it compiles with a black console output. It properly outputs when I remove the string list.

Main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
List<int> DoublyLinkedList = List<int>(); // Working
	List<char> DoublyLinkedList2 = List<char>(); // Working
	List<std::string> DoublyLinkedList3 = List<std::string>(); // Not 
// working

	DoublyLinkedList.InsertHead(43);
	DoublyLinkedList.InsertHead(76);
	DoublyLinkedList.InsertTail(15);
	DoublyLinkedList.InsertTail(44);
	DoublyLinkedList.InsertHead(100);

	DoublyLinkedList2.InsertHead('a');
	DoublyLinkedList2.InsertHead('b');
	DoublyLinkedList2.InsertTail('c');

	DoublyLinkedList3.InsertHead("Ally");
	DoublyLinkedList3.InsertHead("Alyssa");
	DoublyLinkedList3.InsertTail("Meghan");
	DoublyLinkedList3.InsertHead("Savannah");
	DoublyLinkedList3.InsertTail("Jenna");

	DoublyLinkedList.print();
	DoublyLinkedList2.print();
	DoublyLinkedList3.print();


List Class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
 
template <class T>
class List : public Node<T>
{
public:
	List<T>();
	~List<T>();
	Node<T>* Get(int index);
	void InsertHead(const T& Data);
	void InsertTail(const T& Data);
	void Insert(int index, const T& Data);
	int search(T Data);
	void RemoveHead();
	void RemoveTail();
	void Remove(int index);
	void print();
protected:
	Node<T>* head;
	Node<T>* tail;
	int size;
};

template<class T>
inline List<T>::List() :Node<T>()
{
	this->head = nullptr;
	this->tail = nullptr;
	int size = NULL;
}

template<class T>
inline List<T>::~List()
{
}

template<class T>
inline Node<T>* List<T>::Get(int index)
{
	if (index < 0 || index > size)
		return NULL;

	Node<T>* newNode = head;
	for (int i = 0; i < index; ++i)
	{
		newNode = newNode->Next;
	}
	Node<T>* Node = tail;
	for (int i = 0; i < index; ++i)
	{
		newNode = newNode->Prev;
	}

	return newNode;
}

template<class T>
inline void List<T>::InsertHead(const T& Data)
{
	Node<T>* newNode = new Node<T>(Data);
	newNode->Next = head;

	if (head != nullptr)
	{
		head->Prev = newNode;
	}

	head = newNode;

	if (size == NULL)
	{
		tail = head;
	}

	size++;
}

template<class T>
inline void List<T>::InsertTail(const T& Data)
{
	if (size == NULL)
	{
		InsertHead(Data);
		return;
	}

	Node<T>* newNode = new Node<T>(Data);

	tail->Next = newNode;
	newNode->Prev = tail;

	tail = newNode;
	size++;
}

template<class T>
inline void List<T>::Insert(int index, const T& Data)
{
	if (index < NULL || index > size)
	{
		return;
	}

	if (index == NULL)
	{
		InsertHead(Data);
		return;
	}
	else if (index == size)
	{
		InsertTail(Data);
		return;
	}

	Node<T>* prevNode = head;

	for (int i = 0; i < index - 1; ++i)
	{
		prevNode = prevNode->Next;
	}

	Node<T>* nextNode = prevNode->Next;
	Node<T>* newNode = new Node<T>(Data);

	newNode->Next = nextNode;
	newNode->Prev = prevNode;
	prevNode->Next = newNode;
	nextNode->Prev = newNode;
	size++;
}

template<class T>
inline int List<T>::search(T Data)
{
	if (size == NULL)
	{
		return -1;
	}

	int index = NULL;

	Node<T>* newNode = head;
	while (newNode->Data != Data)
	{
		index++;
		newNode = newNode->Next;

		if (newNode == nullptr)
		{
			return -1;
		}
	}

	Node<T>* newNode = tail;
	while (newNode->Data != Data)
	{
		index++;
		newNode = newNode->Prev;

		if (newNode == nullptr)
		{
			return -1;
		}
	}

	return index;
}

template<class T>
inline void List<T>::RemoveHead()
{
	if (size == NULL)
	{
		return;
	}

	Node<T>* newNode = head;
	head = head->Next;

	delete newNode;

	if (head != nullptr)
	{
		head->Prev = nullptr;
	}

	size--;
}

template<class T>
inline void List<T>::RemoveTail()
{
	if (size == NULL)
	{
		return;
	}

	if (size == 1)
	{
		RemoveHead();
		return;
	}

	Node<T>* newNode = tail;
	tail = tail->Prev;
	tail->Next = nullptr;
	delete newNode;
	size--;
}

template<class T>
inline void List<T>::Remove(int index)
{
	if (size == NULL)
	{
		return;
	}

	if (index < 0 || index >= size)
	{
		return;
	}

	if (index == NULL)
	{
		RemoveHead();
		return;
	}
	else if (index == size - 1)
	{
		RemoveTail();
		return;
	}

	Node<T>* prevNode = head;

	for (int i = 0; i < index - 1; ++i)
	{
		prevNode = prevNode->Next;
	}

	Node<T>* newNode = prevNode->Next;
	Node<T>* nextNode = Node->Next;

	prevNode->Next = nextNode;
	nextNode->Prev = prevNode;

	delete newNode;
	size--;
}

template<class T>
inline void List<T>::print()
{
	Node<T>* newNode = head;

	while (newNode != nullptr)
	{
		std::cout << newNode->Data << " -> ";
		newNode = newNode->Next;
	}

	std::cout << "NULL\n";
}


Node Class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
template <class T>
class Node
{
public:
	Node<T>(T Data = NULL);
	void setData(T value);
	T getData();
	Node* getNext();
	Node* getPrev();
	void setNext(Node<T>* Data);
	void setPrev(Node<T>* Data);
	Node<T>* Prev;
	Node<T>* Next;
	T Data;
};

template<class T>
inline Node<T>::Node(T n):Data(n)
{
	this->Prev = nullptr;
	this->Next = nullptr;
}

template<class T>
inline void Node<T>::setData(T value)
{
	Data = value;
}

template<class T>
inline T Node<T>::getData()
{
	return Data;
}

template<class T>
inline Node<T>* Node<T>::getNext()
{
	return Next;
}

template<class T>
inline Node<T>* Node<T>::getPrev()
{
	return Prev;
}

template<class T>
inline void Node<T>::setNext(Node<T>* value)
{
	Next = value;
}

template<class T>
inline void Node<T>::setPrev(Node<T>* value)
{
	Prev = value;
}
Last edited on
Duthomhas (13214)
That code does not compile.

Make it compile, then try again.
aimh4wk (6)
It compiles when I remove
 
 
List<std::string> DoublyLinkedList3 = List<std::string>();

and
1
2
3
4
5
 
        DoublyLinkedList3.InsertHead("Ally");
	DoublyLinkedList3.InsertHead("Alyssa");
	DoublyLinkedList3.InsertTail("Meghan");
	DoublyLinkedList3.InsertHead("Savannah");
	DoublyLinkedList3.InsertTail("Jenna");


When I comment out those code segments, it compiles just fine and outputs;

100 -> 76 -> 43 -> 15 -> 44 -> NULL
b -> a -> c -> NULL


I edited to include the node class
Duthomhas (13214)
Ok, you have a few problems. They’re all easy to fix. :O)

(1)
You are abusing “NULL”.

In C++, use nullptr. But if you must use NULL, make sure it is only used to initialize pointers.

This is actually the reason for the failure. 

1
2
3
4
5
 
template <class T>
class Node
{
public:
	Node<T>(T Data = T()/*NULL*/);  // <-- when T is a std::string, you cannot assign it a value of NULL

When you run your program, the console should print something useful like:
terminate called after throwing an instance of 'std::logic_error'
  what():  basic_string::_M_construct null not valid

(You are running this stuff from the console, right?)


(2)
You are not properly initializing the List.

1
2
3
4
5
6
7
 
template<class T>
/*inline*/ List<T>::List() :Node<T>()
{
	this->head = nullptr;
	this->tail = nullptr;
	/*int*/ size = 0/*NULL*/;  // <-- a local variable is NOT the same as the class variable with the same name
}

Be sure to test for all possibilities... Every time you write a function, use it in every possible combination with the other functions, and make sure your list looks like it ought after every test.

Yep. I know it is a pain in the nose.


(3)
In List<T>::search(), you re-declare the variable “newNode”:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
template<class T>
/*inline*/ int List<T>::search(T Data)
{
	if (size == 0/*NULL*/)
	{
		return -1;
	}

	int index = 0/*NULL*/;

	Node<T>* newNode = head;
	while (newNode->Data != Data)
	{
		index++;
		newNode = newNode->Next;

		if (newNode == nullptr)
		{
			return -1;
		}
	}

	/*Node<T>* */newNode = tail;
	while (newNode->Data != Data)
	{
		index++;
		newNode = newNode->Prev;

		if (newNode == nullptr)
		{
			return -1;
		}
	}

	return index;
}

Either re-use the variable (as I did here) or give it a different name. (The current name does not really match what the variable is used for...)


(4)
You are abusing inline.

Modern compilers don’t really need the hint, but that is all it is — a hint.
Unless your function is very simple, and less than maybe two or three lines of code maximum, don’t use inline.

It doesn’t hurt to have it there, though.


Your code is otherwise very clean and well-organized.
Good job!
aimh4wk (6)
Alright. I removed all NULL comparisons and made them 0.

I am running it using this driver. So I think it's using the console.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
// Create DLL of Integers
	List<int> DoublyLinkedList = List<int>();
	// Create DLL of Characters
	List<char> DoublyLinkedList2 = List<char>();
	// Create DLL of Strings
	List<std::string> DoublyLinkedList3 = List<std::string>();

	// Add Integers
	DoublyLinkedList.InsertHead(43);
	DoublyLinkedList.InsertHead(76);
	DoublyLinkedList.InsertTail(15);
	DoublyLinkedList.InsertTail(44);
	DoublyLinkedList.InsertHead(100);


	// Add Characters
	DoublyLinkedList2.InsertHead('a');
	DoublyLinkedList2.InsertHead('b');
	DoublyLinkedList2.InsertTail('c');


	// Add Strings
	DoublyLinkedList3.InsertHead("Ally");
	DoublyLinkedList3.InsertHead("Alyssa");
	DoublyLinkedList3.InsertTail("Meghan");
	DoublyLinkedList3.InsertHead("Savannah");
	DoublyLinkedList3.InsertTail("Jenna");

	// Display Data
	DoublyLinkedList.Display();
	DoublyLinkedList2.Display();
	DoublyLinkedList3.Display();

	system("pause");
	return 0;



I used inline because that's what VS defaulted when I ask it to create a definition in the header file. I wasn't quite sure what It did anyway.

Implementing your fixes, I got it to work. Thanks!!!

100 -> 76 -> 43 -> 15 -> 44 -> NULL
b -> a -> c -> NULL
Savannah -> Alyssa -> Ally -> Meghan -> Jenna -> NULL
Press any key to continue . . .

Topic archived. No new replies allowed.