Thread: Another Linked List plee

Alright, I'll give you a quick structure / pointer / list tutorial:

Code:

struct name
{
    int data;
};

This is a structure. It a collection of arbitrary data types combine into a single variable type. Structures have a name, which is optional when you declare them. If you don't provide a name at the time of declaration, you can't create instances of them later. So usually we give them a name. The above structure's name is name.

It only has one member, which is an int, called data.

To create an instance of a structure, we can do the following:

Code:

struct name instance;

We now have an instance of this data type. It is called, oddly enough, instance. Creating an instance of a structure is exactly the same as creating any other variable. This variable's type is "struct name", it's name is "instance".

To access members of a structure directly, you use the . operator, commonly called the dot operator (or period). To access data in our instance, we do:

Code:

/* assigning to the data... */
int something = 10;
instance.data = something;
/* assinging the data to something else...*/
something = instance.data;

You can also have pointers to structures. I'll assume you know what pointers are. In case you don't, pointers are variables that store memory addresses. Normal variables hold values. The value a pointer holds is a memory address. You dereference a pointer to see what it points at, that is to say, to get the value of whatever is being pointed at.

You create a pointer to a structure just like you would create a pointer to another variable.

Code:

int *pointer;
struct name *ptrToStruct;

Here we have created a pointer to an integer, and a pointer to a "struct name" data type. To assign an address to a pointer, you can do one of two things:

Code:

struct name *ptrToStruct;
struct name *ptrToStruct2;
struct name instance;

/* assign the address of instance to a pointer directly... */
ptrToStruct = &instance;
/* assign the value of one pointer to another... */
ptrToStruct2 = ptrToStruct;

In the first example, we use the address-of operator to get the address of instance. Once we have it, we assign it to a pointer of the same type. In the second example, we directly give the value of one pointer to another. This is just like assigning "normal" variables values.

To access the data in the structure through a pointer, you use the -> operator. This is commonly called the arrow operator. You use it so you don't have to dereference with parentheses and what not (due to operator precedence). Basicly, it's an easy way to access items in a structure when you're using a pointer to point at that structure. And so...

Code:

/* assign the address of instance to a pointer directly... */
ptrToStruct = &instance;

/* access data using our pointer... */
ptrToStruct->data = 10;

Now, were you to go back to instance, and access the member data, you would find that it is now 10.

All a linked list is, is a structure which contains a pointer to a structure of the same type. This pointer is used to point to another structure, which points to another, which... and so on. Just like links of a chain. Let's demonstrate:

Code:

struct node { /* we'll call this one node, but the name doesn't matter, so long as it has one. */
    struct node *next; /* this is a pointer of the same type as the structure we're creating */
    int somedata;
    int somemoredata;
    int someotherdata;
};

Here we now have a structure, just like any other structure, with one minor exception. It contains a pointer to the structure of the same type as itself. This is so we can make a big list of them, (or small) where one points to the next, points to the next...

And now we will do so:

Code:

/* for illustration, we'll just make 2 pointers, and 2 "regular" instances */
struct node instance1, instance2;
struct node *ptr1, *ptr2;

/* again, for illustration, we'll make each pointer point to a different node */
ptr1 = &instance1;
ptr2 = &instance2;

/* now, we'll make the next pointer in one point to another node */
ptr->next = ptr2;

We now have just created a linked list. It's small, but a list none the less. Were you to access "instance1.next" directly, you'd find that it stores the address of "instance2". Were you to access "ptr1->next", you'd find the same thing.

That'll get you started. Be sure you always initialize your pointers before you use them. I didn't in the case of "ptr2->next", it points randomly at some place in memory. Usually you'd do:

Code:

ptr2->next = NULL;

Or something like that. Anyway that's enough to get you in trouble, so I'll let you get to it.

Quzah.
[edit]Edits to close tags... Preview you say? Hah! [/edit]

Do you know how to use malloc and free? In short, yes. Every time you want another structure, you create an instance of it. In a linked list, you (usually*) use pointers and allocate your new structures whenever you need another one. Then when you're done with them, you free them. Here is a function that creates a new instance dynamicly:

Code:

struct node *makenewnode( void )
{
    struct node *temp = NULL;
    temp = malloc( sizeof( struct node ) );
    return temp;
}

This is the simplest of implementations. Usually your function would initialize each member of the structure to whatever you want. This one simply makes you a new node. You'd use it like so:

Code:

struct node *anode;
anode = makenewnode( );
if( anode != NULL )
{
    ...do whatever you want with it...
}
else
    ...malloc failed, you're out of memory...

But no, you don't have to make "regular" instances each time. And for your final question, yes, every time you want to store data in a link of the list, you have to create another node instance.

It's like so:

Code:

create one node
    put some data in it

create another node
    link it to the first node
    put some data in the new node

create a third node
    link it to the second node
    put some data in it

Now take a look at some of the other linked list examples on the forum, and see if you have a better understanding of them.

Quzah.