The Undergraduate

A Linked List is a data structure that arranges data from a given input into a stored ‘list’. Each item in the list is known as a ‘node’.

Each node within the list contains the set data as well as a ‘pointer’ to the next node within the list; hence ‘Linked List’.

Linked Lists in C utilise three things:

1. malloc
2. structs
3. Pointers

Creating the structure

A C struct acts as a ‘node’ within the Linked List. One of the better ways to declare a C struct is to ‘typedef’ it as such:

#include <stdio.h>
#include <stdlib.h>

typedef struct my_struct_name {
    /* Declare the variables you want in each node */
    int i, j;
    char c;
    double d;

    /* Pointer for next node in list */
    struct my_struct_name *next_node;
} my_struct;

Note: The struct has, in essence, two names. Why? Well, the first name ‘my_struct_name’ refers to that ‘type’ of struct. The second name ‘my_struct’ refers to that specific struct. Also note that there is a pointer within the struct, of that type, which will be used to point to the next node within the list.

And that’s the simplest way to create a node. So, what’s next?

When inserting and retrieving information from the linked list, you will not be calling the struct directly. You in fact need to create three more pointers, external to the struct. These are:

my_struct *first_node, *current_node, *last_node

These pointers will be what you refer to when dealing with your list.

Malloc and Struct syntax

Let’s miss out the part regarding file reading for now (that will be covered in another article) and assume you know what values you want within the list. How are you going to insert them? Quite simple:

1. Begin a loop
2. Malloc the current node in order to reserve memory for that node:

current_node = (my_struct*)malloc(sizeof(my_struct));

3. If the head of the list has not been made, assign the current node to be the head of the list (or ‘first_node’). If the head already exists, assign the current_node to be the last_node’s ‘next_node’ pointer:

if(first_node == NULL)
    first_node = current_node;

else
    current_node = last_node -> next_node;

4. Insert your values by representing the variables within the current node in the structure:

/*Remember this is a pointer and represents the structure*/
&current_node -> i = 42;
&current_node -> j = 100;
current_node -> c = 'a';
&current_node -> d = 13.37;

When you insert into the node, you use the ‘current_node’ pointer ALWAYS. When you call ‘current_node’, you’re calling the structure it represents at a specific block of memory (previously reserved by malloc). The ‘->’ means that you wish to insert or retrieve a value from a variable within the structure. It essentially tells the code to ‘look inside’ the struct and find the variable.

Note: When inserting integer, double, float, or long values into a variable, make sure you use the ‘&’ symbol beforehand.

5. Assign last_node to be the node you’ve just inserted to (as you will be moving on to the next node afterwards:

/* This is important as you might be at the end of the list */
current_node -> next_node = NULL;
last_node = current_node;

These steps are relatively simple to follow and they outline the important parts of creating a simple single linked list using malloc and pointers.

Displaying information from a Linked List

This is very simple and only requires you to set the start node and what rules there are to loop through the list. The most basic version is thus:

current_node = first_node;

while(current_node -> next_node != NULL) {
    printf("One of the values in this node is: %d", current_node -> i);

    /* Set the current_node to point to the next node in the list */
    current_node = current_node -> next_node;
}

This loop will begin at the head of the list, and work its way through each node as long as ‘current_node -> next_node’ is not empty (a.k.a the end of the list).