Jump to content
  • Advertisement
Sign in to follow this  
Oranjoose

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.

If you intended to correct an error in the post then please contact us.

Recommended Posts

EDIT! My setup for this question was very unclear! I have reformatted it to ask exactly what I mean. Sorry. SO. I can get linked lists to work with a global head pointer. I don't want this. Here is the code I have for this method: #include <iostream> using namespace std; struct node{ //struct not class float data; node *next; }; node *head = NULL; //global head pointer void push(float dataIn){ //void, does not return pointer node *addNode; addNode = new node; //allocate for new node addNode->data = dataIn; if(head == NULL){ //testing for empty list addNode->next = NULL; head = addNode; } else{ addNode->next = head; head = addNode; } } void displayList(){ node *temp; temp = head; //setting to beginning of list while(temp->next != NULL){ cout << temp->data << ", "; temp = temp->next; } cout << temp->data << endl; //to get that last data point in there, without the comma } int main(int argc, char* argv[]){ int stay; push(8); push(9); push(10); displayList(); cin >> stay; //because it will keep the command line up return 0; } ------------------------------------- Now. I have gotten it to work by declaring the head pointer in the main function. But then I have to crap like head = push(head, 10); in order to get it to work. I don't want this either. I want to be able to call like this: push(head, 10); and mutate the pointer like that. I don't know if I'm using the correct terminology, I am pretty new, but in any case, I would like to build the list like that. MrAccident I think proposed I use double pointers, and I intruiged by that method. It would require something like dereferencing a pointer to a pointer to the list. Sounds a bit complicated, but maybe it'll work for my needs. Are there any other ways? I'm not trying to be too picky, and I appreciate all the help I've gotten and can get. Thanks. [Edited by - Oranjoose on January 30, 2007 12:44:57 PM]

Share this post


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


Link to post
Share on other sites
Something like this?

node* head=NULL;

void push_front(node* head) {
node* n=new node;
n->data=1.0f;
n->next=head;
head=n;
}

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 this post


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


Link to post
Share on other sites
Quote:
Original post by Crazyfool
struct node{
node* next;
data object;
}; node head_of_list;


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

Share this post


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


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


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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!