Trouple Creating Custom Templated Doubly Linked List

I need to create a templated doubly linked list, with an iterator class within the list class. This program is to function just like the STL list class but I only need to implement functions that I am using, My trouble is I am kind of clueless on the iterator part and the fact that the list is templated is giving me syntax grief. I have pasted the code I have done so far. I need major help:
1. On the syntax implementing the list and iterator functions outside of the class
2. I am not sure when to deference the iterator in the functions, but think I have it right so far
3. For the reverse function can I copy the list into a new list in reverse then re add them to the original list overwriting the same values? I have the code I have so far there
4. For the iterator erase function, I am not sure if I am deleting the node correctly.
5. I am not sure if I need template <typename T> above the iterator functions. Does the iterator class need to be a template? Right now it is not.

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
// Templated doubly linked list class

#include <iostream>
using namespace std;

template <typename T>
class list
{
private:
	Node *head;
	Node *tail;
	class Node
	{
		T createNode;
		Node *next;
		Node *prev;
		Node(T data)
		{
		createNode = data;
		prev = next = NULL;
		}
	};
	
	friend class iterator;
	friend class Node;
public:
	class iterator
	{
		Node *iter;
		iterator() {}
		iterator operator++();
		iterator operator--();
		typename begin() const;
		typename end() const;
		typename erase(Node *eraseIter);
	};
	list()
	{  head = tail = NULL; }
	~list(){ destroylist();}
	void destroylist();
	void push_back(const T& x);
	void reverse();
};


template <typename T>
void list<T>::destroylist()
{
    Node *iterNode = tail;
    while(iterNode != NULL)
    {
        Node *deleteNode = T;
        iterNode = iterNode->prev;
        delete deleteNode;
    }
    head = NULL;
    tail = NULL;
}

// Creates a node of intended size
// and adds it to the back of the list
template <typename T>
void list<T>::push_back(const T& data)
{
	Node<T> *temp;
	//temp = new Node<T>(data, tail, NULL);
	temp = new Node<T>(data);
	tail->next = data;
	data->prev = tail;
	tail = data;
	tail->next = NULL;
	if(head = NULL)
	{
		head = tail;
	}
}

// Revereses the order of the
// items in the list
template <typename T>
void list<T>::reverse()
{
	list<Pixel> tempList;
	list<Pixel>::iterator iter = pixelList.end();
	while (iter != pixelList.begin())
	{
		tempList.push_back(*iter);
		--iter;
	}
	list<Pixel>::iterator tempIter = tempList.begin();
	while (iter != pixelList.end())
	{
		pixelList.push_back(*tempIter);
		++iter;
	}
}

template <typename T>
typename list<T>::iterator iterator operator++()
{
	iter = *iter->next;
	return *this;
}

template <typename T>
typename list<T>::iterator operator--()
{
	iter = *iter->prev;
	return *this;
}

template <typename T>
typename list<T>::iterator begin() const
{
	iter = head;
	return iter;
}

template <typename T>
typename list<T>::iterator end() const
{
	iter = *tail->next;
	return iter;
}

template <typename T>
typename list<T>::iterator erase(Node *eraseIter)
{
	if (iter == head)
	{
		head = head->next;
		head->prev = NULL;
		delete iter;
		Node* newIter = head;
		return newIter;
	}
	if (iter == tail)
	{
		tail = tail->prev;
		tail->next = NULL;
		delete iter;
		Node* newIter = tail;
		return newIter;
	}
	else
	{
		*iter->next->prev = *iter->prev;
		*iter->prev->next = *iter->next;
		Node* newIter = *iter->next;
		delete *iter;
		return newIter;
	}
}





Any help on any of my questions would be GREATLY appreciated!
Last edited on
Please try to compile your code.
If the templates are bothering you then try
1
2
3
4
//template<class T>
class list{
   typedef int value_type;
   //typedef T value_type; 

1)
1
2
3
4
5
6
7
8
9
10
11
void 
list::push_back(const value_type& x){} //non template
template<class T>
void 
list<T>::push_back(const value_type& x){} //template

list::iterator&
list::iterator::operator++(){} //non template (note that iterator is an inner class)
template<class T>
typename list<T>::iterator& //dependent name
list<T>::iterator::operator++(){} //template 
You've got several member functions in the wrong place. By instance, `erase()' should be a function of list, no of iterator, and it is weird that `iterator' can give you begin() and end().

2) You don't have a dereference operator yet.

3) For reverse you could simply do
1
2
traverse(node, list)
   swap(node.prev, node.next)


4) `erase()' should ask for an iterator. The client has no way to send it a Node*.
You could avoid especial cases, simplifying your functions, by making a `circular' list with a header `cell' (that has no data)

You shouldn't dereference in line 147,148. You need to handle the pointers.


To make your iterator work with `std::algorithm' check out `iterator_traits'
Also, you may want to drop using namespace std; it could give you conflict

By the way
1
2
3
4
Node(T data):
   createNode(data) //copy constructor
{
   //createNode = data; //assignment operator 
Last edited on
Thank you! I have fixed up a lot of the problems.

1) As far the headers go our teacher told us to use typename instead of class for:

template<class T>
void list<T>::push_back(const value_type& x){} //template

Will what I have now work using typename?

2) When creating a node, since it is in the list class, what do I have to do to create it? It's giving me an error when I make one. Do I need list<T>::Node or something like that?

3) I think my erase should accept an iterator now. Will the actual function part work?

4) I put in a new reverse function. Does this look good?

5) I still think my function definition headings are wrong. I tried to fix them like you said.


Thanks for your help! I really appreciate it.


Updated code:

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
// Templated doubly linked list class

#include <iostream>
using namespace std;

template <typename T>
class list
{
private:
	Node *head;
	Node *tail;
	struct Node
	{
		T createNode;
		Node *next;
		Node *prev;
		Node(T data)
		{
		createNode(data);
		prev = next = NULL;
		}
	};
	
	friend class iterator;
	friend class Node;
public:
	class iterator
	{
	private:
		Node *iter;
	public:
		iterator() {}
		iterator operator++();
		iterator operator--();
		friend class list;
	};
	list()
	{  head = tail = NULL; }
	~list(){ destroylist();}
	void destroylist();
	void push_back(const T& x);
	void reverse();
	T begin() const;
	T end() const;
	T erase(Node *eraseIter);
};


template <typename T>
void list<T>::destroylist()
{
    Node *iterNode = tail;
    while(iterNode != NULL)
    {
        Node *deleteNode = T;
        iterNode = iterNode->prev;
        delete deleteNode;
    }
    head = NULL;
    tail = NULL;
}

// Creates a node of intended size
// and adds it to the back of the list
template <typename T>
void list<T>::push_back(const value_type& data)
{
	Node<T> *temp;
	//temp = new Node<T>(data, tail, NULL);
	temp = new Node<T>(data);
	tail->next = data;
	data->prev = tail;
	tail = data;
	tail->next = NULL;
	if(head = NULL)
	{
		head = tail;
	}
}

// Revereses the order of the
// items in the list
template <typename T>
void list<T>::reverse()
{
	Node *traversePtr;
	Node *temp;
	traversePtr = head;
	while (traversePtr != NULL)
	{
		temp = traversePtr->next;
		traversePtr->next = traversePtr->prev;
		traversePtr->prev = temp;
		if (temp == NULL)
		{
			tail = head;
			head = traversePtr;
		}
		traversePtr = temp;
	}

}

template <typename T>
T list<T>::begin()
{
	iter = head;
	return iter;
}

template <typename T>
T list<T>::end()
{
	iter = tail->next;
	return iter;
}

template <typename T>
T list<T>::erase(iterator eraseIter)
{
	if (iter == head)
	{
		head = head->next;
		head->prev = NULL;
		delete iter;
		Node* newIter = head;
		return newIter;
	}
	if (iter == tail)
	{
		tail = tail->prev;
		tail->next = NULL;
		delete iter;
		Node* newIter = tail;
		return newIter;
	}
	else
	{
		iter->next->prev = iter->prev;
		iter->prev->next = iter->next;
		Node* newIter = *iter->next;
		delete *iter;
		return newIter;
	}
}

template <typename T>
typename list<T>::iterator iterator operator++()
{
	iter = iter->next;
	return *this;
}

template <typename T>
typename list<T>::iterator operator--()
{
	iter = iter->prev;
	return *this;
}
Last edited on
Again, try to compile your code. There are a lot of snips that make no sense at all.
1
2
3
4
5
6
7
8
9
10
11
//void list<T>::destroylist()
        Node *deleteNode = T; //T=std::string, ¿what?
        iterNode = iterNode->prev;
        delete deleteNode; //¿what are you deleting?

//same for end()
T list<T>::begin() //T=double, you need to return an `iterator'
{
	iter = head; //¿what's iter? If it is an iterator, then you can't assign it a Node*
	return iter;
}
`list::end()' have other issue, iirc you seem to want to return an iterator that holds a NULL pointer. ¿How do you expect to advance that iterator?
It could be easily resolved with a circular list


> our teacher told us to use typename instead of class
Use `typename' then, the rest remain the same. Your operator{++,--} are wrong.


About `reverse()', please use `swap()', it'll make the code clearer.
I don't understand lines 94-98 ¿why don't just `swap(head, tail)' at the end?
Ok I fixed end. I did't realize I did tail->next instead of tail. And our teacher's assignment specified we could not do a circular list.

Ok. Why are those operators wrong? Isn't an iterator defined as a node pointer?

I did not know about that function. I'll change it.

And that destroy list is a mess I know. I need to change it.

Does my syntax for the iterator functions look right? That's my main problem.
As I already posted them
1
2
3
template<typename T>
typename list<T>::iterator& //dependent name
list<T>::iterator::operator++(){}
note that you need to qualify that `operator++' is a member function of iterator, and that iterator is an inner class of (the templated) list<T>


> Isn't an iterator defined as a node pointer?
Nope, an iterator is a class in it's own right
Ok I have done all the overloaded operators except not equal to, !=. I'm confused about what to compare in order to return a boolean.
Ughhh. Insert is returning wrong type. Thoughts?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Inserts a node at position 1 before
// the iterator
template <typename T>
void list<T>::insert(iterator position, iterator newNode)
{
	if (position == head) 
	{
		head->prev = newNode;
		newNode->next = head;
		newNode->prev = NULL;
		head = newNode;
	}
	else
	{
		newNode->prev = position->prev;
		newNode->next = position;
		position->prev = newNode;
		newNode->prev->next = newNode;
		position = newNode;
	}
}
Last edited on
Topic archived. No new replies allowed.