Public Group

Linked Lists, help! [EDITED FOR CLARITY]

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

Recommended Posts

Share on other sites
First off, this is C/C++, right? If so you've got a problem right there in your node struct - it's a circular definition. A structure cannot contain an instance of itself. It can contain a pointer to its own type, or a reference (if this is C++), but not an object directly.

For the other part, I'm not quite sure what you're asking. A usual approach would be to define a set of functions that take a node pointer and perform some operation on the list. If the operation might change the root node, you could have the function return a pointer to the new root, which could then be assigned by the caller, or you could use a pointer to a pointer as the function's argument (probably less recommended).

EDIT: Wait, I think I get your question now. [smile] Are you asking how to avoid the "return-a-pointer-to-the-new-root" style? In that case you would need to use double pointers, as I mentioned above. Something like this:

void push(node** head_ptr, float value){   node* new_node = (node*)malloc(sizeof(node));   node->value = value;   node->next = *head_ptr;   *head_ptr = new_node;}

If you're using C++, encapsulating the linked list in a class might be a good idea, but I'm not sure what exactly your particular needs are. Could you give a little more information about what you want, maybe?

[Edited by - MrAccident on January 30, 2007 11:27:44 AM]

Share on other sites
Something like this?

node* n=new node;
n->data=1.0f;
}

EDIT: Hey Oranjoose, don't look at this... It's a bad code :D

[Edited by - DanyATK on January 30, 2007 11:32:20 AM]

Share on other sites
DanyATK: that won't work, since "head" is a parameter to your push_front function. Reassigning "head" only changes the value of the parameter within the function. To modify the value of a passed head pointer, the caller either has to reassign it using a provided return value, or the function has to use a double pointer.

Share on other sites
Argh, I didn't know this. Thank you!

struct node{
node* next;
data object;

Share on other sites
Quote:
 Original post by Crazyfoolstruct node{ node* next; data object;}; node head_of_list;

This is a global pointer, if I'm not mistaken. Thanks anyway though.

Share on other sites
Ok, well, I have only done linked lists with classes.

Here's my version:

class Node{	public:		Node(){}		~Node()		{			//needs to clean up everything		}		                //used in my game		Card card;		Node* next;};

Then I have:
class Deck{	public:		Deck()		{			size = 0;		}		~Deck()		{			// In here, you will want to release all the memory you allocated			// AKA, your linked list		}				Node* head;		int size;		void addToTop(Card card)		{			//checks to see if empty list			if(size == 0)			{				head = new Node(card);			}			else			{				Node* n = new Node(card, head);				head = n;			}			size++;		}		void clear()		{			head = NULL;			size = 0;			delete this;		}				void removeTop()		{			if(size > 1)			{				head = head->next;				size--;			}			else			{				head = NULL;				size = 0;			}		}		bool empty()		{			if(size == 0)				return true;			else				return false;		}		Card top()		{			return head->card;		}};

Edit:
Quote:
 n order to get it to work. I don't want this either.I want to be able to call like this:push(head, 10);

Well, that would be a global function. In my method(and the std::list I believe), you'd do:

list_name.addToTop(data); or push_back(), or push(), whatever.

Share on other sites
That looks good. I'm glad you could make linked lists work for your application. However, I really want to make this work with structs for now. Sorry for the inconvenience.
THanks.
Thanks.

Share on other sites
What you need to do is pass your head pointer by reference, so that your push function can modify the head pointer itself. Since I assume this is a learning exercise I'll give you an outline let you fill in the missing bits:
struct node{	float data;	node * next;};// Pass head by reference.  This means you can modify the pointer// directly, as well as what it points to and the calling code// will see the modifications.void push(node * & head, float value){	// create the new node and add it to the given list}void print_list(node * head){	// print the list}int main(){	node * list = null;	push(list, 8);	push(list, 9);	push(list, 10);	print_list(list);}

Once you've gotten that working you'll probably want to encapsulate your list a little more so that people can't make mistakes list:
int main(){	node * list; //oops, not null	push(list, 8); // off we go to the land of undefined behaviour}
Learning to write a linked list is a valuable exercise for any programmer, but remember that being able to write a linked list isn't everything. You also need to be able to decide when, where and how to use lists and when where and how to use the other data structures (i.e. vector, deque, map, etc.). Once you've written your own linked list and are happy with it throw it away and use std::list. Your own linked list will teach you the how of linked lists, but in order to learn the proper wheres and whys you really need to use a linked list designed and written by experts.

Σnigma

1. 1
2. 2
Rutin
21
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• Forum Statistics

• Total Topics
633736
• Total Posts
3013603
×