Trouple Creating Custom Templated Doubly Linked List

[tunalite]

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.

// 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!

[ne555]

Please try to compile your code.
If the templates are bothering you then try

//template<class T>
class list{
   typedef int value_type;
   //typedef T value_type; 

1)

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

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

Node(T data):
   createNode(data) //copy constructor
{
   //createNode = data; //assignment operator 

[tunalite]

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:

// 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;
}

[ne555]

Again, try to compile your code. There are a lot of snips that make no sense at all.

//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?

[tunalite]

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.

[ne555]

As I already posted them

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

[tunalite]

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.

[tunalite]

Ughhh. Insert is returning wrong type. Thoughts?

// 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;
	}
}