Jump to content
• Advertisement

Public Group

Template Linked List Question

This topic is 5007 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I created my own templatized linked list which acts as both a stack and queue (when reverse is invoked). This is the first time I've used templates, so I'm having a few concerns. I'm using visual studio 6.0. When I create my template class and then assign the class member functions like this: template <class Type> int LinkedList<Type>::Pop(Type &Value) {} The member function disappears from the left panel on the class browser! What is happening? am I doing something wrong? why isn't it being recognized as a part of the class by the IDE environment?? The code still compiles and my linked list structure works very nicely. Next issue: This is probably more to do with code design or lack of knowledge on my part. My linked list class needs something to track where the head and tail of the datastructures are currently located. Before I started using templates, my class looked like this: class LinkedList { ... }*Head, *Tail; But now after I converted my class to a templatized format (much better! no overloaded member functions for different datatypes), I am not allowed to have *Head and *Tail where they used to be. Instead I have to declare them as global variables with a defined type like this: LinkedList<int> *Head, *Tail; Which, I really don't want to do if I can avoid it. I also don't think I want to put the head & tail into the actual class itself because then every instance of the linked list will have a head and tail variable, and it'd be insanely crazy trying to manage (not to mention that its a compile error). :P Anyone's input is very welcome!

Share this post

Share on other sites
Advertisement
I'm afraid I can't answer your first question, I don't use VS6.

For the second question: this is how I would implement a templatised linked list - this is off the top of my head, so please forgive any syntax misses:

template<class T> struct Node{  T data;  Node<T>* nextNode;  Node<T>* previousNode;};template<class T> class LinkedList{private:  Node<T>* front;  Node<T>* back;public:  LinkedList() {front = NULL; back = NULL;}    void push_front(T x);  etc.};public:  void push_front(T x);    etc.}template<class T> void LinkedList<T>::push_front(T x){// This could be much more neatly done with a Node ctor  Node<T>* thisNode = new Node<T>;  thisNode->data = x;  thisNode->previousNode = NULL;  thisNode->nextNode = front;  front->previousNode = thisNode;}etc.

All the data is stored in Node class, and the Linked list itself just handles the pointers to the head and tail. List traversal is done just by starting with the head (or tail) from the LinkedList class and then traversing the Node* nextNode (or previousNode) pointers).

Hope this helps with your question.
Jim.

Share this post

Share on other sites
I've got a working parameterized linked list here, if you want it, PM me your email, and I'll zip up the source and send it to you?

Share this post

Share on other sites
ah, very interesting. I never thought about seperating the data from the linked list. So interesting, I think I'm going to restructure my whole linked list class to model your concept (to a degree). I don't know what exact benefits that has, but I'll probably see it later on. probably easier to implement different datastructures on the same data...
Its important for me to get something this important perfectly right. thanks! :)

Share this post

Share on other sites
Quote:
 Original post by slayemin...I also don't think I want to put the head & tail into the actual class itself because then every instance of the linked list will have a head and tail variable, and it'd be insanely crazy trying to manage (not to mention that its a compile error).

Could you explain your reasoning for this? Each instance of a linked list is [should be] a totally separate list, with different elements, and thus, a different head and tail. If you want to be able to reference the same linked list from various places, then use references when you can, and pointers otherwise.

On a related note, though, you can always have static member variables in classes/structs. There will only be one instance of each of these variables, no matter how many instances of the class/struct there are, and yet they aren't technically global, either. I don't think this is what you really want in this situation (all though it might be what you think you want).

Share this post

Share on other sites
I don't know how to create the neat little code box, but here is what my current linked list class looks like:

template <class Type>class LinkedList{protected:	Type Data;	LinkedList *Next;	LinkedList *Prev;public:	LinkedList();	~LinkedList();	LinkedList(Type &Value);		int GetNext(Type &Value);	int SetValue(Type &Value);	int GetValue(Type &Value);	int Pop(Type &Value);	int Push(Type &Value);	int GetSize();	int Reverse();	int PrintAll();	int ClearList();};LinkedList<char> *Head;//<---this sucks!

(I noticed don't actually use the *Tail, so I removed it.)

wait, whoa...static member variables? whats that? one instance? so its possible to have a single instance of *Head?

My explanation for not putting the *Head inside the linkedlist class: (with ascii art)
(with *head included in each node)
+----+    +----+    +----+|data| +->|data| +->|data|+----+ |  +----+ |  +----+|head| |+-|head| |+-|head|+----+ || +----+ || +----+|next|-+| |next|-+| |next|--||+----+  | +----+  | +----+  ^-----+---------+(head)

with that, every node would have a head which points to the *head node. I don't think it would be necessary at all to have that many heads all pointing at the same object in memory...though, heh, I just realized that if *head is a pointer to a place in memory, each node would know where the *head is at, not that it needs to though. If I add another node, I'd have to traverse the entire linked list and reset all the heads to point at the new head.
what do you think is best?

Share this post

Share on other sites
Quote:
 Original post by slayeminwhat do you think is best?

Well unless your learning data structures & algorithms, then focus on learning & using the standard library instead, this will give you a start.

Other than that from what i glanced at your code it looks like you can only have one list & your mixing list nodes & list + operations together in one type & you have global instance of the head of the list! not good at all, clients dont need/care to know about the internals of a list to use one.

Share this post

Share on other sites
I'll have a go again!

Quote:
 I don't know how to create the neat little code box, but here is what my current linked list class looks like:

You can find this, and other useful bits of information in the FAQ section, near the top of the forum pages.

Quote:
 //LinkedList code

Hmm, OK, I can see what you're up to. Basically your LinkedList class is the same as my Node class (although why protected for your data?). I'm intrigued as to how many of your functions work, but thinking about it, I can see why you think you need the head pointer at every node - ahh, that's it, when you call GetSize (for example) on a given Node, it first uses it's head pointer to get to the start and then traverses using each LinkedLists prev pointer. Was I close?

I think your list will improve by seperating out the data and the functionality (into Nodes and LinkedLists). If you do want to continue like you are, I think you'd need to have each LinkedList contain a head pointer as a data-member - I mention this only in passing, because I don't think many folks would use this kind of construction - it's a good start, and I can sort of see how it would work, but I think you'd be using both extra memory (as you've already identified) and possibly be marginally slower, because I think you'd have to make another pointer jump when iterating over the list.

Quote:
 wait, whoa...static member variables? whats that? one instance? so its possible to have a single instance of *Head?

Yup, a static data-member (and bear in mind there are other uses of static) is a data-member that exisits at a class-level, and not an instantiated object level. From some code I answered a question with recently:

// includesstruct ob{static int x;};int ob::x = 0;int main(){  ob ob1, ob2;  ob1.x = 1;// Note could also use ob.x, as it's a static member  std::cout << ob2.x;// This will output 1 and not 0}

A fulller explanation is near the end of this topic.

Quote:
 My explanation for not putting the *Head inside the linkedlist class: (with ascii art)(with *head included in each node)

Not sure I understand what's going on here, but I think you're alluding to the extra head pointers (oh yeah, reading your later text suggests that this is the case). OK - I answered that above - and this is why I think you'll see most implementations of LinkedLists seperate out the dataNodes from the functionality.

HTH,
Jim.

Share this post

Share on other sites
if you were curious about my current implementation of my linked list structure, here it is.
enum ERROR_CODE { FAIL, SUCCESS, EMPTY, FULL, OUTOFSPACE};//template <class Type>class LinkedList{protected:	Type Data;	LinkedList *Next;	LinkedList *Prev;public:	LinkedList();	~LinkedList();	LinkedList(Type &Value);		int GetNext(Type &Value);	int SetValue(Type &Value);	int GetValue(Type &Value);	int Pop(Type &Value);	int Push(Type &Value);	int GetSize();	int Reverse();	int PrintAll();	int ClearList();};LinkedList<char> *Head;//template <class Type>LinkedList<Type>::~LinkedList(){	Data = 0;	Next = NULL;	Prev = NULL;}//template <class Type>LinkedList<Type>::LinkedList(){	Data = 0;	Next = NULL;	Prev = NULL;}//template <class Type>LinkedList<Type>::LinkedList(Type &Value){	Data = Value;	Next = Head;	Prev = NULL;}//template <class Type>int LinkedList<Type>::GetSize(){	if(Head==NULL)	{		return(0);	}	int Counter = 1;	LinkedList *Temp = Head;	while(Temp->Next!=NULL)	{		Counter++;		Temp = Temp->Next;	}	return(Counter);}//template <class Type>int LinkedList<Type>::Pop(Type &Value){	if(Head!=NULL)	{		LinkedList *Temp = Head;		Value = Head->Data;		Head = Head->Next;		delete Temp;		return(SUCCESS);	}	else	{		return(EMPTY);	}}//template <class Type>int LinkedList<Type>::Push(Type &Value){	LinkedList *Temp = new LinkedList();	Temp->Data = Value;	if(Head!=NULL)	{		Head->Prev = Temp;	}	Temp->Next = Head;	Head = Temp;	return(SUCCESS);}//template <class Type>int LinkedList<Type>::Reverse(){	/*	What this does(theory):	It takes the stack and reverses the order of it, converting it into a Queue datastructure.	Note, that pushing an item onto this reversed structure will still put it on top, not in 	the rear like a true queue. Instead, just reverse the linked list to add to the stack.	Process:	Create a temporary linked list (LL) to hold our data as an intermediary (avoid data loss)	Switch the next and prev values in the temp LL.	Check to ensure that we don't break the condition of our while loop (if statement)	tricky part: set the head to the "current", but I have to access it in a round-about way.	*/	if(Head!=NULL)	{		LinkedList *Current = Head;		LinkedList Temp;		while(Current!=NULL)		{			Temp = *Current;			Temp.Prev = Current->Next;			Temp.Next = Current->Prev;			Current->Next = Temp.Next;			Current->Prev = Temp.Prev;			if(Temp.Prev!=NULL)			{Current = Temp.Prev;}			else			{Current = &Temp; break;}		}		Head = Current->Next->Prev;		return(SUCCESS);	}	else	{		return(EMPTY);	}}//template <class Type>int LinkedList<Type>::PrintAll(){	if(Head==NULL)	{		return(EMPTY);	}	LinkedList *Temp = Head;	while(Temp!=NULL)	{		cout << Temp->Data << "";		Temp = Temp->Next;	}	return(SUCCESS);}//template <class Type>int LinkedList<Type>::ClearList(){	if(Head==NULL)	{		return(EMPTY);	}		while(Head!=NULL)	{		LinkedList *Temp;		Temp = Head->Next;		delete Head;		Head = Temp;	}	return(SUCCESS);		}

note: theres a weird part in the reverse section where I have to do a reference by "Current->Next->Prev"
I'm going to keep working on this. (I want to know this stuff inside and out)

Share this post

Share on other sites
Quote:
 Well unless your learning data structures & algorithms, then focus on learning & using the standard library instead, this will give you a start.

/me discovers the STL and figures out how it works, then commences the jumping for joy.

Wow, I'm in awe...heh, shoot. Now I don't have to program this stuff, though it was a fun exercise.

Share this post

Share on other sites

• Advertisement
• Advertisement

• Popular Contributors

1. 1
2. 2
3. 3
4. 4
frob
15
5. 5
• Advertisement

• 12
• 20
• 12
• 13
• 14
• Forum Statistics

• Total Topics
632146
• Total Posts
3004437

×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!