Thread: Linked Lists aaaugggh

Okay, all this compiles fine, but I probably have some bugs.

Code:

template< typename T_ >
class Linked_List
{
public:

	Linked_List<T_>()
	{
		start_ptr = NULL;
		current = NULL;
	}
	T_ * data;
    Linked_List<T_> * nxt;// Pointer to next node

	void add_node(T_)
	{
		Linked_List<T_> *temp, *temp2;   // Temporary pointers
		// Reserve space for new node and fill it with data
		temp = new Linked_List<T_>;
		temp->data = T_;
		temp->nxt = NULL;
		// Set up link to this node
		if (start_ptr == NULL)
		{
			start_ptr = temp;
			current = start_ptr;
		}
		else
		{
			temp2 = start_ptr;
			// We know this is not NULL - list not empty!
		    while (temp2->nxt != NULL)
			{
				temp2 = temp2->nxt;
                // Move to next link in chain
            }
			temp2->nxt = temp;
		}
	}

	void display_list()
	{
		Linked_List<T_> *temp;
		temp = start_ptr;
		cout << endl;
		if (temp == NULL)
			cout << "The list is empty!" << endl;
		else
		{
			while (temp != NULL)
			{
				// Display details for what temp points to
				if (temp == current)
					cout << " <-- Current node";
				cout << endl;
				temp = temp->nxt;
			}
			cout << "End of list!" << endl;
		}
	}

	void delete_start_node()
	{
		Linked_List<T_> *temp;
		temp = start_ptr;
		start_ptr = start_ptr->nxt;
		delete temp;
	}

	void delete_end_node()
	{ 
		Linked_List<T_>  *temp1, *temp2;
		if (start_ptr == NULL)
			cout << "The list is empty!" << endl;
		else
		{ 
			temp1 = start_ptr;
			if (temp1->nxt == NULL)
			{
				delete temp1;
				start_ptr = NULL;
            }
			else
			{
				while (temp1->nxt != NULL)
				{
					temp2 = temp1;
					temp1 = temp1->nxt;
                }
				delete temp1;
                temp2->nxt = NULL;
			}
		}
	}
	 
	void move_current_on ()
	{
		if (current->nxt == NULL)
			cout << "You are at the end of the list." << endl;
		else
			current = current->nxt;
    }

	void move_current_back ()
	{ 
		if (current == start_ptr)
			cout << "You are at the start of the list" << endl;
		else
		{ 
			 node *previous;     // Declare the pointer
			 previous = start_ptr;
			 while (previous->nxt != current)
			 {
				 previous = previous->nxt;
			 }
			 current = previous;
		 }
	 }

	 Linked_List<T_> * start_ptr;
	 Linked_List<T_> *current;		 // Used to move along the list
};

It compiles fine like I said, I'm gonna try to add some stuff.

Looks like the first error to come to my attention is with the add function.
I need to pass it a T, if T has been declared as an std::string why can't I give it "hello" as a parameter?
Like this:

Code:

	Linked_List<std::string> list;
	list.add_node("Hello!");

This produces an error in the add function that looks like this

Code:

------ Build started: Project: Blackjack, Configuration: Debug Win32 ------
Compiling...
Card_Game.cpp
c:\documents and settings\jcoleman\desktop\blackjack\blackjack\linked_list.h(23) : error C2275: 'T_' : illegal use of this type as an expression
        c:\documents and settings\jcoleman\desktop\blackjack\blackjack\card_game.cpp(11) : see declaration of 'T_'
        c:\documents and settings\jcoleman\desktop\blackjack\blackjack\linked_list.h(19) : while compiling class template member function 'void Linked_List<T_>::add_node(T_)'
        with
        [
            T_=std::string
        ]
        c:\documents and settings\jcoleman\desktop\blackjack\blackjack\card_game.cpp(11) : see reference to class template instantiation 'Linked_List<T_>' being compiled
        with
        [
            T_=std::string
        ]
Build log was saved at "file://c:\Documents and Settings\jcoleman\Desktop\Blackjack\Blackjack\Debug\BuildLog.htm"
Blackjack - 1 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

I'll paste the function and bold the lines causing the errors:

Code:

	void add_node(T_)
	{
		Linked_List<T_> *temp, *temp2;   // Temporary pointers
		// Reserve space for new node and fill it with data
		temp = new Linked_List<T_>;
		temp->data = T_;
		temp->nxt = NULL;
		// Set up link to this node
		if (start_ptr == NULL)
		{
			start_ptr = temp;
			current = start_ptr;
		}
		else
		{
			temp2 = start_ptr;
			// We know this is not NULL - list not empty!
		    while (temp2->nxt != NULL)
			{
				temp2 = temp2->nxt;
                // Move to next link in chain
            }
			temp2->nxt = temp;
		}
	}

But I thought data was a T_ and so was the parameter for add_node...

So if I make a linked list of T_ and have a pointer to T_ in there, if I pass it a string which is a T_ then data = T_ sounds feasable to me...

Theyre all T_'s!!!

I'm missing something.

Oh, I'm a dufus

Code:

	void add_node(const T_ & t)
	{
		Linked_List<T_> *temp, *temp2;   // Temporary pointers
		// Reserve space for new node and fill it with data
		temp = new Linked_List<T_>;
		temp->data = t;
		temp->nxt = NULL;
		// Set up link to this node
		if (start_ptr == NULL)
		{
			start_ptr = temp;
			current = start_ptr;
		}
		else
		{
			temp2 = start_ptr;
			// We know this is not NULL - list not empty!
		    while (temp2->nxt != NULL)
			{
				temp2 = temp2->nxt;
                // Move to next link in chain
            }
			temp2->nxt = temp;
		}
	}

I guess I was trying to set data, which is a T_, = to a string, that won't work. Instead I needed to set an instance of T_ (which happens to be a string) t = to data, and that works just fine.

But now I'm having an issue setting my reference t = to a data pointer....

Code:

------ Build started: Project: Blackjack, Configuration: Debug Win32 ------
Compiling...
Card_Game.cpp
c:\documents and settings\jcoleman\desktop\blackjack\blackjack\linked_list.h(23) : error C2440: '=' : cannot convert from 'const std::string' to 'const std::string *'
        No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called
        c:\documents and settings\jcoleman\desktop\blackjack\blackjack\linked_list.h(19) : while compiling class template member function 'void Linked_List<T_>::add_node(const T_ &)'
        with
        [
            T_=std::string
        ]
        c:\documents and settings\jcoleman\desktop\blackjack\blackjack\card_game.cpp(11) : see reference to class template instantiation 'Linked_List<T_>' being compiled
        with
        [
            T_=std::string
        ]
Build log was saved at "file://c:\Documents and Settings\jcoleman\Desktop\Blackjack\Blackjack\Debug\BuildLog.htm"
Blackjack - 1 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

Hmmmmmm.... I'm not used to working with this many pointers! lol.

Wow, it works! Every function works fine!

Here is the completed code for my linked list (hacked together with examples)

Code:

#include <string>
#include <iostream>
using namespace std;

template< typename T_ >
class Linked_List
{
public:

	Linked_List<T_>()
	{
		start_ptr = NULL;
		current = NULL;
	}
	T_ data;
    Linked_List<T_> * nxt;// Pointer to next node

	void add_node(T_ & t)
	{
		Linked_List<T_> *temp, *temp2;   // Temporary pointers
		// Reserve space for new node and fill it with data
		temp = new Linked_List<T_>;
		temp->data = t;
		temp->nxt = NULL;
		// Set up link to this node
		if (start_ptr == NULL)
		{
			start_ptr = temp;
			current = start_ptr;
		}
		else
		{
			temp2 = start_ptr;
			// We know this is not NULL - list not empty!
		    while (temp2->nxt != NULL)
			{
				temp2 = temp2->nxt;
                // Move to next link in chain
            }
			temp2->nxt = temp;
		}
	}

	void display_list()
	{
		Linked_List<T_> *temp;
		temp = start_ptr;
		cout << endl;
		if (temp == NULL)
			cout << "The list is empty!" << endl;
		else
		{
			while (temp != NULL)
			{
				// Display details for what temp points to
				cout << temp->data;
				if (temp == current)
					cout << " <-- Current node";
				cout << endl;
				temp = temp->nxt;
			}
		}
	}

	void delete_start_node()
	{
		Linked_List<T_> *temp;
		temp = start_ptr;
		start_ptr = start_ptr->nxt;
		delete temp;
	}

	void delete_end_node()
	{ 
		Linked_List<T_>  *temp1, *temp2;
		if (start_ptr == NULL)
			cout << "The list is empty!" << endl;
		else
		{ 
			temp1 = start_ptr;
			if (temp1->nxt == NULL)
			{
				delete temp1;
				start_ptr = NULL;
            }
			else
			{
				while (temp1->nxt != NULL)
				{
					temp2 = temp1;
					temp1 = temp1->nxt;
                }
				delete temp1;
                temp2->nxt = NULL;
			}
		}
	}
	 
	void move_current_on ()
	{
		if (current->nxt == NULL)
			current = start_ptr;
		else
			current = current->nxt;
    }

	void move_current_back ()
	{ 
		if (current == start_ptr)
			cout << "You are at the start of the list" << endl;
		else
		{ 
			 node *previous;     // Declare the pointer
			 previous = start_ptr;
			 while (previous->nxt != current)
			 {
				 previous = previous->nxt;
			 }
			 current = previous;
		 }
	 }

	 Linked_List<T_> * start_ptr;
	 Linked_List<T_> *current;		 // Used to move along the list
};

Here is the main function:

Code:

int _tmain(int argc, _TCHAR* argv[])
{
	srand ( unsigned(time(NULL)) );
	Linked_List<std::string> list;
	std::string hello = "Hello!";
	list.add_node(hello);
	hello = "My";
	list.add_node(hello);
	hello = "name";
	list.add_node(hello);
	hello = "is";
	list.add_node(hello);
	hello = "Jonathan!";
	list.add_node(hello);
	list.display_list();
    return 0;
}

Sweet, cuz the output is correct too!!

Code:

Hello! <-- Current node
My
name
is
Jonathan!
Press any key to continue . . .

Nifty huh?

Just so you know, templates are used to accept a range of different types. You define the type T (or whatever name you choose) through the template declaration. However, T is a type, not a variable. So assigning something to T is illegal--you can't assign a type to something.
Just see T as a special type that the compiler only knows. You can, of course, as you've seen, create instance of variables with type T which works perfectly fine (and which is usually what templates are all about).

Great explanation, I think I understand now .

I decided that I don't want the linked list class to actually be a link in the linked list. I want to abstract it, I'll paint a picture for you:

http://img.photobucket.com/albums/v1...ewhatimean.jpg

I'm not sure if I should make a nested node structure, or a seperate node stucture all the time. I want them seperate because I want to create an abstract node class that I can derive subclasses from. I want to be able to recursively update the data for all the nodes in my list.

I'll have to remove the next pointer and the data T_ from the Linked_List class. Perhaps the only template should be the actual nodes themselves?

Any ideas?