Implementing a Generic Doubly Linked List

[myk45]

Hello,
im trying to implement a generic double linked list, and i have added just one function(insert).
But im getting some errors. Here is the code:

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

template <typename T>
class doubleList {
	private:						
		struct Node {
			T info;
			Node *leftPtr;
			Node *rightPtr;
		};

		// head and tail of the list.
		static Node* head;
		static Node* tail;


		Node* getNode();
	public:			
		void addNode(T var);
		void traverseList();
};

template<typename T>
Node* doubleList<T> :: getNode()
{
	Node* ptr = new Node();
	return ptr;
}

template<typename T>
void doubleList<T> :: addNode(T var)
{
	Node *temp = getNode();

	if (head == NULL) {
		// First element.
		temp->info = var;
		head = temp;
		tail = temp;
		temp->leftPtr = temp->rightPtr = NULL;
	} else {
		temp->info = var;
		temp->rightPtr = NULL;
		temp->leftPtr  = head;
		head = temp;
	}
}


int main()
{
	string s[5] = {"hello", "world", "bye", "wirld", "hey!"};
	int    a[5] = {1, 2, 3, 4, 5};

	doubleList<string> ob1;
	doubleList<int>    ob2;

	// add all elements into the linked list.
	for (int i = 0; i < 5; i++) {
		ob1.addNode(s[i]);
		ob2.addNode(a[i]);
	}
	
	getchar();
	return 0;
}

Can anyone please help?
Thanks.

[Fbody]

>>Can anyone please help?
Not unless you elaborate on the nature of the errors you are getting. Unless you share more information, all we can really do is take wild guesses.

I don't think your getNode() is correct. I think you're missing a template argument in the line where you instantiate a new Node. But that's just a guess...

[griswolf]

• What are the errors?
• Why do you make the head and tail nodes static? Don't you want distinct instances of doubleList to have distinct head and tail? (also, see note below)
• The normal way to name a class is CapitalCamelCase , not lowerCamelCase , so I prefer that your class be named DoubleList

(the note below): You need an actual sentinel node at each end to avoid problems with iteration over the list. Just a "null" will cause a lot of extra code to deal with the ends. (for extra credit: Is it possible to create a single sentinel node that can be used as both the head and tail node?)

[myk45]

Thanks for the reply,

Well, the errors are as follows

1)syntax error : missing ';' before '*'
2)missing type specifier - int assumed. Note: C++ does not support default-int
3)'T' : undeclared identifier

These are the ones reported on VC++ 2008. i tried it on another online compiler, and i got this:
error: expected constructor, destructor, or type conversion before ‘*’ token

all errors pointing to the getNode() function, but i did not get what they mean in this context ie, im not able to understand why im getting these errors.

[myk45]

@griswolf

>> Why do you make the head and tail nodes static? Don't you want distinct instances of doubleList to have distinct head and tail? (also, see note below)

Ah, got your point, i need to change that.

>> The normal way to name a class is CapitalCamelCase , not lowerCamelCase , so I prefer that your class be named DoubleList

Will do that.

>> for extra credit: Is it possible to create a single sentinel node that can be used as both the head and tail node?

Hmm i did not get you. How may i do that?

Thanks for the reply.

[myk45]

@@griswolf
Here is the results by the online compiler:

http://ideone.com/y5EQK

i made the head and tail members non-static now, and also, changed the class name, and im getting the same error even now.

[Fbody]

template<typename T>
Node* doubleList<T> :: getNode()
{
	Node* ptr = new Node();
	return ptr;
}

Node is defined inside a templatized class relative to the template dataType. It is therefore templatized as well, try giving the new statement a template argument.

[myk45]

im sorry, i did not get you. What did you exactly mean by

"try giving the new statement a template argument".

PS: Could the error be because i have a templated variable inside the Node structure?

[griswolf]

two points:

In a double linked list, you have a structure like this: leftSentinel <=> node <=> node <=> ... <=> rightSentinel In your code, leftSentinel and rightSentinel are merely NULL not full nodes. That means that when you are following pointers from one node to another, you have to be careful every time to avoid dereferencing the NULL on the end. If, instead, you have full-featured (but empty) nodes on the ends, your code is simpler: There is no special case for dealing with an empty list, there is no difference between iterating from one node to another and iterating from or to one end or the other.

When your compiler issues an error, you can usually figure out what it means. Rules of thumb:

• The problem is probably on or before the line the compiler mentions
• After the first error, the compiler is confused. Ignore any errors except the first reported
• If the problem is a syntax error, look on the line(s) above for a missing semi-colon, a missing curly brace or parenthesis, etc.
• If the error message is too large for you to easily parse, break it apart and read it carefully: The compiler writers are trying to be helpful, so the information is probably there, even if well hidden.

[griswolf]

I think maybe the Node declaration is scoped, so at lines 37 through 42 of the online compier's code you linked above, you may want DoubleList::Node where you now have Node . Not sure this is the problem, just thinking about the error message.

[myk45]

Well, would this be ok then?

[ lptr = NULL Left_sentilel rptr] <-> [lptr Node1 rptr] <-> [lptr Node2 rptr] ....... [ lptr right_sentilel rptr = NULL ]

So, now,my left and right sentinels will be normal nodes, with the rptr, lptr being NULL.

Is this what you meant?

[griswolf]

Yes, that would be better, easier. And it brings us back to the "extra credit" question in my first post: Can (should) you use a single sentinelNode to handle both ends of the list? Note that leftSentinel isn't using its lptr ...

One other thing I've thought about is a 'roll of film' list (picture: "O___O") where leftSentinel->lptr = &leftSentinel and similarly on the right. Now you can iterate forever without ever running off the end. There are pros and cons (mostly cons, I decided, in the end).

[myk45]

Solved. This was the problem: had to put "typename"

template<typename T>
typename doubleList<T>::Node* doubleList<T> :: getNode()
{
        Node* ptr = new Node();
        return ptr;
}

@griswolf

Well, about using the lefPtr of the left sentinel, best i could think of is, make a circular list. But i did not intend to make one.

So, im not sure how we can use the left sentinel for both ends. Any ideas?
Thanks.

[griswolf]

It looks circular, but it is not (exactly) because you are using it as a 'straight' list. The advantage is one fewer nodes to allocate,so smaller size and quicker constructor. If you want to implement a circular queue based on this, it would be pretty easy, though.