Sign in to follow this  

linked lists

This topic is 4377 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

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?

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Your first code should read

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

while (temp != 0)
{
coutxnext;
}
}


Otherwise it will repeatedly print the head's value.

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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.



*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.

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites

This topic is 4377 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.

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