Linked Lists

Like an array, a linked list is a data structure for holding numerous pieces of data in some sequence. The big problem with arrays is that you generally need to know in advance how many pieces of data you want to store in order to define them. Whilst there are such things as dynamic arrays, which get around this problem, they can become a little difficult to manage. Linked lists to the rescue!

Unlike predefined static arrays, linked lists are designed to have items added to them in real time while the program is actually running. If the user inputs more data, more items are added to the linked list to hold them.

In structure, a linked list is very simple. It just consists of a series of items called nodes, each of which contains two things: a piece of data, and a pointer to the next node. Adding nodes to a linked list is then very easy. One simply sets aside some memory to hold the new node, sets the pointer part of the last node to be defined, to point to the new node and puts the relevant piece of data into the new node.

Here is a very basic implementation of a linked list in C, each node of which contains an integer as its piece of data:

   typedef struct node
        int numdata;
        struct node * nextnode;
    } node;
    node * linkedlist;

The final line tells you that linkedlist is a pointer to a variable of type node. This is of course not an internal C type, but one of our own making. This is what the typedef is all about. The word typedef tells C we are going to define our own type.

The variable type node consists of a structure (also called node) containing (between the curly braces) the two things we mentioned: an int and a pointer to another node. Note that since we are in the process of defining what a node is, we cannot simply refer to nextnode as a pointer to a node. Instead, we tell C that nextnode is a pointer to a structure which is called node.

Actually, this type definition consists of two things. One is the definition of a type called node and the other is the definition of a compound structure (also called node). They can be separated out, if one desires, as follows:

    struct node
        int numdata;
        struct node * nextnode;
    typedef struct node node;

Of course the definition of the struct itself is really enough. All the typedef in fact does is make it so that we don't have to refer to our structure as struct node all the time, and we can just call it a node. It is most common to combine the typedef and struct as in the fisrt method which we showed above, rather than separating the two out.