Why does this not work?

I am making a deque with dummy head and tail pointers. Everything works until after I call the copy constructor and try to add something on the list. I have stepped though multiply times and am completely clueless on why this is not working. Here is some code.

Main:
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
void main()
{
	Deque deque;
	Deque::nodePtr iter;

	// Test the class to see if it works correctly.
	iter = deque.InsertFront(10);
	iter = deque.InsertBack(13);
	iter = deque.Insert(12, iter);
	iter = deque.Insert(11, iter);

	// List deque in forward order.
	cout << "Original deque forward:" << endl;
	iter = deque.GetHead();
	while (iter != NULL) {
		cout << iter->item << endl;
		iter = deque.GetNext(iter);
	}

	cout << endl
		 << "Original deque backward:" << endl;
	iter = deque.GetTail();
	while (iter != NULL) {
		cout << iter->item << endl;
		iter = deque.GetPrevious(iter);
	}
	// Test the copy constructor.
	Deque deque2(deque);
	// Add a value to deque2 and verify it is not in deque.
	deque2.InsertBack(14);//works until here 


Only important parts of the .h file if you need to see it.
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
namespace DequeNS {
	typedef int DequeItemType;

	/* Class: Deque
	 *
	 * Represents a double ended queue, i.e. a doubly linked list. The class
	 * will make use of dummy nodes, one at each end of the list (head, tail).
	 */
	class Deque {
	public:
		class Node;
		typedef Node* nodePtr;

		/* Class: Node
		 *
		 * Nested class represents a node on the list.
		 */
		class Node {
		public:
			DequeItemType item;
			nodePtr previous;
			nodePtr next;

			Node(const DequeItemType& item, const nodePtr previous, const nodePtr next) 
				: item(item), previous(previous), next(next)
			{}
		};// end Node

	private:
		nodePtr head;
		nodePtr tail;
		nodePtr iter;


copy constructor
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
Deque::Deque(const Deque& copy)
	{
		CopyNodes(copy.head->next);
		
	}

void Deque::CopyNodes(const nodePtr& copyHead)
	{
		Node* tail = head;
		
		head = tail = CreateNode(DequeItemType(), NULL, NULL);
		Node* copyIter = head;
		Node* copy = copyHead;

		while(copy->next != NULL)
		{
			copyIter->next = CreateNode(copy->item, copyIter, tail);
			copyIter = copyIter->next;
			tail->previous = copyIter;
			copy = copy->next;
		}
	}
Deque::nodePtr Deque::CreateNode(const DequeItemType& item, const nodePtr previous, const nodePtr next)
	{
		Node* newNode;
		try 
		{
			newNode = new Node(item, previous ,next);
		}
		catch (bad_alloc ba)
		{
			cerr << "Unable to allocate sufficient memory. Exiting!" << endl;
			exit(1);
		}

		return newNode;
	}


And this is where it breaks:
1
2
3
4
5
6
Deque::nodePtr Deque::InsertBack(const DequeItemType& item)
	{
		tail->previous = CreateNode(item, tail->previous, tail);//here
		tail->previous->previous->next = tail->previous;
		return tail->previous;
	}

If you need to see anything else please let me know and I will post it, thanks.
You haven't posted all your code. But from what you've posted, the Deque copy constructor does not initialise the class members. I'd imagine they'd start off as NULL.

Deque::CopyNodes has local variable called tail which hides the member variable tail.

I'd expect the compiler to tell you this stuff though.

The really means that tail is uninitialised when the copy constructor completes. Use of it in InsertBack is meaningless.

You don't need to catch the exception in CreateNode, that's the whole point of exceptions (rather than error codes). And if you do catch it, you probably should catch a const reference.
Would it be easier for me to just do the copying in the assignment operator? Then just call the assignment operator in the copy constructor. Initializing the head and tail in the copy constructor did not do anything. When the teacher did a example with single linked list in class he did essentially the same thing as what I have now and his worked, but I have no idea how.
Last edited on
You still have to initialise members in all constructors.
Okay here is all the code.
Main
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
#include "Deque.h"
#include <iostream>

using namespace std;
using namespace DequeNS;

void main()
{
	Deque deque;
	Deque::nodePtr iter;

	// Test the class to see if it works correctly.
	iter = deque.InsertFront(10);
	iter = deque.InsertBack(13);
	iter = deque.Insert(12, iter);
	iter = deque.Insert(11, iter);

	// List deque in forward order.
	cout << "Original deque forward:" << endl;
	iter = deque.GetHead();
	while (iter != NULL) {
		cout << iter->item << endl;
		iter = deque.GetNext(iter);
	}

	cout << endl
		 << "Original deque backward:" << endl;
	iter = deque.GetTail();
	while (iter != NULL) {
		cout << iter->item << endl;
		iter = deque.GetPrevious(iter);
	}
	// Test the copy constructor.
	Deque deque2(deque);
	// Add a value to deque2 and verify it is not in deque.
	deque2.InsertBack(14);     //breaks here

	cout << endl
		 << "deque2 forward (includes 14):" << endl;
	iter = deque2.GetHead();
	while (iter != NULL) {
		cout << iter->item << endl;
		iter = deque2.GetNext(iter);
	}
	cout << endl;
	cout << "Original deque forward (should not include 14):" << endl;
	iter = deque.GetHead();
	while (iter != NULL) {
		cout << iter->item << endl;
		iter = deque.GetNext(iter);
	}

	// Testing the assignment operator.
	Deque deque3 = deque2;

	iter = deque3.RemoveFront();
	cout << endl
		 << "deque2 forward (should include 14):" << endl;
	iter = deque2.GetHead();
	while (iter != NULL) {
		cout << iter->item << endl;
		iter = deque2.GetNext(iter);
	}
	cout << endl;
	cout << "deque3 forward (should not include 10):" << endl;
	iter = deque3.GetHead();
	while (iter != NULL) {
		cout << iter->item << endl;
		iter = deque3.GetNext(iter);
	}

}

.h
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
#ifndef DEQUE_H
#define DEQUE_H

namespace DequeNS {
	typedef int DequeItemType;

	/* Class: Deque
	 *
	 * Represents a double ended queue, i.e. a doubly linked list. The class
	 * will make use of dummy nodes, one at each end of the list (head, tail).
	 */
	class Deque {
	public:
		class Node;
		typedef Node* nodePtr;

		/* Class: Node
		 *
		 * Nested class represents a node on the list.
		 */
		class Node {
		public:
			DequeItemType item;
			nodePtr previous;
			nodePtr next;

			Node(const DequeItemType& item, const nodePtr previous, const nodePtr next) 
				: item(item), previous(previous), next(next)
			{}
		};// end Node

	private:
		nodePtr head;
		nodePtr tail;
		nodePtr iter;

		// Deletes all the nodes and sets head, tail, iter to NULL.
		void DeleteNodes();
	
		// Duplicates all the nodes on the deque referenced by copyHead.
		void CopyNodes(const nodePtr& copyHead);

		// Creates a new node and populates it. If unable to allocate, it returns NULL.
		nodePtr CreateNode(const DequeItemType& item, const nodePtr previous, const nodePtr next);

	public:	
		// Creates an empty list consisting of the two dummy nodes 
		// (head, tail). iter is set to NULL.
		Deque();
	
		// Creates a duplicate of the copyDeque.
		Deque(const Deque& copyDeque);

		// Destroys the deque.
		~Deque();
	
		// Deletes the existing deque and creates a duplicate of assignDeque.
		Deque operator =(const Deque& assignDeque);

		// Returns a rererence to the first data node or NULL if it does not exist.
		nodePtr GetHead() const;
	
		// Returns a reference to the last data node or NULL if it does not exist.
		nodePtr GetTail() const;

		// Returns a reference to the node after iter if it exists, NULL otherwise.
		nodePtr GetNext(nodePtr iter) const;
	
		// Returns a reference to the node before iter if it exists, NULL otherwise.
		nodePtr GetPrevious(nodePtr iter) const;

		// Inserts a new node before the node referenced by iter, and returns a 
		// reference to the added node.
		nodePtr Insert(const DequeItemType& item, nodePtr iter);
	
		// Inserts a new node at the front of the deque, and returns a 
		// reference to the added node.
		nodePtr InsertFront(const DequeItemType& item);

		// Inserts a new node at the back of the deque, and returns a reference
		// to the added node.
		nodePtr InsertBack(const DequeItemType& item);

		// Removes the node referred by iter and returns the node following if
		// it exists, NULL otherwise.
		nodePtr Remove(nodePtr iter);

		// Removes the first node and sets iter to the next node if it exists,
		// NULL otherwise.
		nodePtr RemoveFront();

		// Removes the last node and sets iter to the previous node if it exists,
		// NULL otherwise.
		nodePtr RemoveLast();
	};// end Deque
}// end namespace DequeNS
#endif 
.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
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
#include "Deque.h"
#include <iostream>
#include <new>
#include <cstdlib>

using namespace std;

namespace DequeNS
{
	void Deque::DeleteNodes()
	{
		Node* del = head;

		while(del->next != tail)
		{
			head = head->next;
			del->next = NULL;
			delete del;
			del = head;
		}
		iter = NULL;
	}

	void Deque::CopyNodes(const nodePtr& copyHead)
	{
		Node* tail = head;
		
		head = tail = CreateNode(DequeItemType(), NULL, NULL);
		Node* copyIter = head;
		Node* copy = copyHead;

		while(copy->next != NULL)
		{
			copyIter->next = CreateNode(copy->item, copyIter, tail);
			copyIter = copyIter->next;
			tail->previous = copyIter;
			copy = copy->next;
		}
	}

	Deque::nodePtr Deque::CreateNode(const DequeItemType& item, const nodePtr previous, const nodePtr next)
	{
		Node* newNode;
		try 
		{
			newNode = new Node(item, previous ,next);
		}
		catch (bad_alloc ba)
		{
			cerr << "Unable to allocate sufficient memory. Exiting!" << endl;
			exit(1);
		}

		return newNode;
	}

	Deque::Deque()
	{
		head = CreateNode(DequeItemType(), NULL, NULL);
		tail = CreateNode(DequeItemType(), NULL, NULL);
		head->next = tail;
		tail->previous = head;
		iter = NULL;
	}

	Deque::Deque(const Deque& copy)
	{
		head = tail = CreateNode(DequeItemType(), NULL, NULL);
		CopyNodes(copy.head->next);
	}

	Deque::~Deque()
	{
		DeleteNodes();
	}

	Deque Deque::operator=(const Deque& assignDeque)
	{
		if(this != &assignDeque)
		{
			DeleteNodes();
			CopyNodes(assignDeque.head);
		}
		return *this;
	}

	Deque::nodePtr Deque::GetHead() const
	{
		if(head->next != tail)
			return head->next;
		else
			return NULL;
	}

	Deque::nodePtr Deque::GetTail() const
	{
		if(tail->previous != head)
			return tail->previous;
		else
			return NULL;
	}

	Deque::nodePtr Deque::GetNext(nodePtr iter) const
	{
		if(iter->next != tail)
			return iter->next;
		else
			return NULL;
	}

	Deque::nodePtr Deque::GetPrevious(nodePtr iter) const
	{
		if(iter->previous != head)
			return iter->previous;
		else
			return NULL;
	}

	Deque::nodePtr Deque::Insert(const DequeItemType& item, nodePtr iter)
	{
		if(iter == head)
			return InsertFront(item);
		else if(iter == tail)
			return InsertBack(item);
		else 
		{
			iter->previous = CreateNode(item, iter->previous, iter);
			iter->previous->previous->next = iter->previous;
			return iter->previous;
		}
	}

	Deque::nodePtr Deque::InsertFront(const DequeItemType& item)
	{
		head->next = CreateNode(item, head, head->next);
		head->next->next->previous = head->next;
		return head->next;
	}

	Deque::nodePtr Deque::InsertBack(const DequeItemType& item)
	{
		tail->previous = CreateNode(item, tail->previous, tail);
		tail->previous->previous->next = tail->previous;
		return tail->previous;
	}

	Deque::nodePtr Deque::Remove(nodePtr iter)
	{
		Node* del = iter;
		if(del->next = tail)
		{
			del->previous->next = tail;
			tail->previous = del->previous;
			return NULL;
		}
		else
		{
			del->previous->next = del->next;
			del->next->previous = del->previous;
			return del->next;
		}
		del = NULL;
		delete del;
	}

	Deque::nodePtr Deque::RemoveFront()
	{
		Node* del = head->next;
		if(del->next = tail)
		{
			head->next = tail;
			tail->previous = head;
			return NULL;
		}
		else
		{
			head->next = del->next;
			del->next->previous = head;
			return del->next;
		}
		del = NULL;
		delete del;
	}

	Deque::nodePtr Deque::RemoveLast()
	{
		Node* del = tail->previous;
		if(del->previous = head)
		{
			tail->previous = head;
			head->next = tail;
			return NULL;
		}
		else
		{
			tail->previous = del->previous;
			del->previous->next = tail;
			return del->previous;
		}
		del = NULL;
		delete del;
	}
}//end namespace DequeNS 
Okay I got the copy constructor to work, all I had to do was remove this -_-
1
2
3
Node* tail = head;
		
		head = tail = CreateNode(DequeItemType(), NULL, NULL);
Topic archived. No new replies allowed.