What is, and how do you use linked lists? ======================== Game project(s): www.fiend.cjb.net

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

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

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

That will be great!

I think i can put that on hold for a while

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

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