Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

JonatanHedborg

Linked lists

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

Advertisement
ked list is a data structure that has memory allocated at runtime. It is sort of like an array but it can change size at any time. They are composed of nodes, structs that include content and a pointer to the next node.

You implement one like this.

First create a struct that includes the content and a pointer to the struct. I''ll use an int.

struct node{
int content; //this can be anything
node* next;
};

Then create a pointer to the top of the link list to be created.
This pointer is usually called head. Since the list is initially empty set this to null.

node* head = NULL;

When you want to add an item use ''new'' to allocate a new node and
have head point to it. BTW make sure that the last node in the list always points to NULL.

node* newNode = new node;
newNode->content = 42;
newNode->next = NULL;

Now your list is one item long and looks like this.

head-->Node #1-->NULL
\->42

Try adding new nodes to the beggining, middle end of the list. You will find out that ''while'' loops are your best friend. Here is how you read the list.

node* focus = head;
while(focus != NULL){
printf("%i \n", focus->content);
focus = focus->next;
}

Notice how the list is flexible when it comes to size. If the list is empty it prints nothing and if if has 1000 items it prints 1000 items. Linked lists have some advantages over arrays in that they have that flexibility. It is also very fast to insert to or delete from a linked list. Inserting into the middle of an array is painful as I''m sure you''ve found out.

Once you''ve got a handle on linked lists try a doubly linked list or a tree. Hope this helps.


-Jordan Andersen

Share this post


Link to post
Share on other sites
Ok, now i feel realy stupid =)

Could you perhaps post a short program? (please, i realy need to know this... i think... )


========================
Game project(s):
www.fiend.cjb.net

Share this post


Link to post
Share on other sites
I''m currently working on a series of articles devoted to Data Structures, of which linked lists are described in the first article. If you can wait a little while (month?), it''ll be up in the featured article area.

Kevin

Share this post


Link to post
Share on other sites
I always love to use a for-loop to iterate through the list:

for (node *focus=head; focus; focus=focus->next)
printf("%i \n", focus->content);


ArgoN

Share this post


Link to post
Share on other sites
Something you should know is that linked lists are just simple objects (of structures) termed nodes. How they linked is that each node stores a pointer to the next node and also, that next node contains a pointer to the node after it.

How this helps is that you can add (and delete) nodes so it becomes something like an array but with a volatile size or capacity.

The head node is the first in the list and of course the tail as the last whose pointer should be NULL.

Say for example, you have a structure that contains information of fighter planes and objects would be declared in game and are destroyed when the plane crashes. What you would do is create a linked lists and add nodes as and when you need. When you add nodes, you must make the tail pointer point to the newest node and when you delete one, you must "link" back up the list.

Hope that clears up something.

Share this post


Link to post
Share on other sites
quote:
Original post by ArgoN

I always love to use a for-loop to iterate through the list:

for (node *focus=head; focus; focus=focus->next)
printf("%i \n", focus->content);


ArgoN



In the article I''ve written, I''ve just been using while loops for simplicity, but I think I''ll stick the for loop in there just to show another way to iterate through the list.

Kevin

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!