Sign in to follow this  
slayemin

Template Linked List Question

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


Link to post
Share on other sites
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


Link to 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


Link to 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


Link to 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


Link to 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


Link to post
Share on other sites
Quote:
Original post by slayemin
what 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


Link to 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:


// includes

struct 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


Link to 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


Link to 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


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this