Skip to main content
GameDev.net gamedev.net
🔒 Locked

linked lists

Started by subflood Dec 17, 2005 at 12:09 PM 10 replies 1.5k views
Original Post
subflood
subflood
Hello, I have programmed two very similar programs that should produce the same output but they do the very opposite. The difference between the two, as far as I can tell, is that one has functions inside its structure while the other doesn't. functions in structures: When I call the Print function only the last structure gets printed in the list. 

#include <iostream>

using namespace std;

struct List
{
	int x;
	struct List *next;

	void Create(int length);
	void Print();
};

void List::Create(int length)
{
	List *temp = this;

	for (int i = 0; i < length; i++)
	{
		if (i == length - 1)
		{
			x = i;
			next = 0;
			break;
		}

		x = i;
		next = new List;
		temp = next;
	}
}

void List::Print()
{
	List *temp = this;

	while (temp != 0)
	{
		cout<<x<<endl;
		temp = temp->next;
	}
}

int main(void)
{
	List *list = new List;

	list->Create(20);
	list->Print();

	return 0;
}
functions outside structures: All the structures get printed in the list. 

#include <iostream>

using namespace std;

struct intStack
{
	int x;
	struct intStack *next;
};

void CreateList(intStack *list, int length);
void Print(intStack *list);

int main(void)
{
	intStack *List = new intStack;

	CreateList(List, 20);
	Print(List);

	return 0;
}

void CreateList(intStack *list, int length)
{
	intStack *temp;

	for (int i = 0; i < length; i++)
	{
		if (i == length - 1)
		{
			list->x = i;
			list->next = 0;
			break;
		}

		list->x = i;
		
		temp = new intStack;
		list->next = temp;
		list = list->next;
	}
}

void Print(intStack *list)
{
	while (list != 0)
	{
		cout<<list->x<<endl;
		list = list->next;
	}
}
My question to you guys is: why are the two programs acting differently? What can I do to fix this?
Aryabhatta
Aryabhatta
In the first program, you should do a cout << temp->x << endl;
You also have made the same mistake in List::Create.
subflood
subflood
I fixed it and now it works. Thanks!

One more question though, why is that after I create the linked list the pointer in the main function still points to the first node? I would think it would point to the last node because in the Create function I assign it a new address each iteration of the loop.
iMalc
iMalc
Easy. Each node only points to the next one, so somthing has to point to the first one, otherwise you'd have no way of getting back to thee start of the list, since you don't have previous pointers.
Often, linked list classes have a pointer to the start of the list, and the end of the list, so you can add to either end, or remove from the start, in constant time.
Typically, they would also differentiate between the list nodes, and the list container. Your Print function, and pointer(s) to the list should ideally be in the list's container class because it iterates over the nodes. The node itself, should only be concerned with itself and not it's neighbouring node.
But there's more than one way to code it, that's for sure.
subflood
subflood
I'm still not understanding this.

The original pointer is in the main function

List *list = new List;


The Create function then gets executed

temp is assigned the address of the original pointer.

Finally this line comes along:

temp = temp->next; //Temp is assigned a new address


By the end temp will be pointing to the last data structure in the list but when control goes back to the main function list is now pointing to the beginning of the linked list. I don't understand this, why is it not pointing to the last structure in the list?
subflood
subflood
Quote:


*list, *temp, this
these three pointers are seperate pointers. all 3 point to your list. Moving one of the pointers doesn't move any of the others.


Ok I understand now. Thanks a lot!
Enigma
Enigma
Quote:
Original post by Anonymous Poster
Also, it's NULL, not 0.
Usually you can get away with it, but the 4 values have specific meanings for those reading it.
0 - integer value - count of zero items
0.0f - float value - is part of a floating point expression
'\0' - null character - specifically the end of a string
NULL - a null pointer - ends of lists, pointers to nothing, etc.

in x86, these different names all seem to do the same thing, but seperating them out enhances clarity for you and for others.

In C++ it's quite common to see 0 used instead of NULL, since NULL is just a #define of 0. While using NULL can increase readability it can also result in confusion if you have a function overloaded on a pointer and int on compilers that do not specially handle NULL, i.e.:
#include <iostream>class Thing{};void func(int){	std::cout << "int\n";}void func(Thing *){	std::cout << "Thing *\n";}int main(){	func(NULL); // prints "int\n";}

Enigma
iMalc
iMalc
[razz][razz][razz]
int main(){	func((Thing*)NULL); // prints "Thing *\n";}
Hehe[wow][smile][cool]
Zahlman
Zahlman
Quote:
Original post by iMalc
But there's more than one way to code it, that's for sure.


Fortunately, there is also one highly-recommended way to avoid coding it (as I'm sure you're aware) :D

#include <iostream>#include <list>using namespace std;list<int> create(int count) {  list<int> results;  for (int i = 0; i < count; ++i) { results.push_back(i); }  return results;}void printList(const list<int>& l) {  std::copy(l.begin(), l.end(), std::ostream_iterator<int>(std::cout, "\n"));}int main() {  printList(create(20));}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.