Introduction to Pointers, Structures and Linked-Lists Part 3

Introduction to Pointers, Structures and Linked-Lists Part 3
Introduction to Simple Linked-Lists
by Chris Bennett aka Dwarfsoft

Phew, we are now up to the third part of this introduction. The dirty part is Linked-Lists. Truly, though, linked lists are not that bad, and are very beneficial for a LOT of reasons. They are more dynamic than arrays in that you can keep expanding a linked list until your RAM runs out, and they are also good for collection of relevant data into one structure. Anyway, let us have a bit of a theoretical talk about what linked lists are and how you go about implementing one.

Figure 1 - Simple setup for a linked list structure

The above setup is our structure. It is just a visual representation where Member Data (and the box below it) are just the variables that you have in your structure, and Next is a pointer to a structure of the same type. Next is required in a linked list, but there may be more. A single linked list is a list where there is only one join between two structures of the same type in the list. There can be double linked lists, where there is a dual bond between the two structures (usually 'previous' and 'next') or there can be dynamic linked lists (like a current project that I am doing) which has a dynamic value between 0 and [theoretically] infinite links between structures (or nodes).

Anyway, here is how you define the structure that is listed above, continuing on with our address book idea:

typedef struct strAddress
{
    char Name[30];
    char Address[180];
    char PhoneNo[10];
    struct strAddress *Next;
} Address_t, *AddressPtr_t;

OK, so we have our linked list structure defined already. You are probably asking why I defined 'Next' with 'struct strAddress *' instread of 'AddressPtr_t'. That is because AddressPtr_t hasn't been defined yet. There is a way to get AddressPtr_t defined at the same time as using it in the structure. This is mainly for ensuring consistency.

typedef struct strAddress *AddressPtr_t;
typedef struct strAddress
{
    char Name[30];
    char Address[180];
    char PhoneNo[10];
    AddressPtr_t *Next;
} Address_t;

This is legal and it does work, more importantly, you can use this method to link between different structures by defining pointers to structures before the structures themselves. Unlike in PASCAL, in C/C++ you can define the pointer to a structure ANYWHERE outside of a code block. I recommend that you define all of your typedefs in a header file though, for ease of including.

And from that structure we can do this:

Figure 2 - A link from one element in the list to the next

This can be condinued for eternity (or until you run out of memory) and will work. So how do we get about doing this? First, I would like you to take note of this. Whenever you create a linked list, reset all of its pointers to NULL, just to be safe. If you do this, then we can safely parse through the list until we hit a NULL dead end. In the above pictures, take it that a 'Next' box without an arrow from it contains a NULL.

Now, creating a simple link between two variables. We go about this like so:

Address_t Address1,Address2;
Address2.Next = NULL;
Address1.Next = &Address2;

Now, when you want to go through your list, you can use the following code (assuming that you have included 'stdio.h' or 'stdlib.h')

AddressPtr_t Current;
Current = &Address1;
while (Current)
{
  printf("\nName: % s\nAddress: %s\nPhoneNo: %s\n",
          Current->Name,Current->Address,
          Current->PhoneNo);
  Current = Current->Next;
}

The reason why the line 'while (Current)' works is because it keeps going until the pointer 'Current' is equal to the value 'NULL', which is why I said that when you initialise your linked list to set the values for Next to NULL if they didn't point to anything. The line 'Current = Current->Next' does just what it looks like. It sets what it is currently pointing to, to the next item in the list. The last thing it will do, is set itself to NULL before exiting. This will print out all of the values in the list (which is just the contents of Address1 and Address2).

So now you are wondering 'what is the point' because you have to initialise all of the variables and put them in a list yourself. There is something else that we are missing, and it is the key reason for linked lists. Dynamic Memory Allocation. I will continue on about this in the next section.

Cheers, Chris Bennett (aka. Dwarfsoft)

Discuss this article in the forums

Date this article was posted to GameDev.net: 9/30/2004
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
General