Single Linked List

One of the most common and simple applications of Pointers in C programming is the Single Linked List. This is basically a series of dynamically created data records (structs) that are linked by a single pointer connection. Stacks (aka LIFO - Last-In-First-Out) implementation is very simple and easy by using this kind of data structure and algorithms, but other approaches like queues (aka FIFO - First-In-First-Out) are a little bit more complicated as we can search for items in the list in one direction only (that's the reason they are named "single linked"). Another good feature of the SLL is that in your programs you only need to keep a single reference pointer to the header of the list, and with that single data you can perform all operations.

This is the simplest of the data structures declaration you need to define for creating a Single Linked List. You can define your own set of data, I'm using only an integer value for demonstration purposes.

struct list_node {
    int val;
    struct list_node *next;
};

typedef struct list_node node;

Now, let's go to the basic of the functionalities, the node creation. We will accomplish this by creating a function that will return a pointer to our dynamically created node.

node *create_node(int data)
{
    node *temp = (node *)malloc(sizeof(node));
    temp->val = data;
    temp->next = NULL;
    return temp;
}

In this function we are passing as value parameter some of the data we want stored in the node, then allocating some memory for the precise size of the data structure we want to store and finally making sure that the pointer to the next node is NULL (we don't want to try to jump into an unreferenced memory and have a catastrophic error).

Next, let's examine how we can start building our list by defining another function. I will use the name "push" that is the most commonly known operation for inserting elements in a stack.

void push(node **head, int data)
{
    node *curr = create_node(data);
    curr->next = *head; //new node points to the original head
    *head = curr; //move the reference of the head to the new node.
}

Notice how we are passing the reference to our list "head" as a double pointer: this is because we are passing it as reference as the head value will be updated with the new head that will be in the top of the stack. The original head will be now the second element of the stack, and this is accomplished by first making sure the new node points to the original head, and then "moving" the reference of the head to the new node.

For calling the previous function you need to pass the adress (&) of the head pointer, here an example:

int main()
{
   node *head;
   head = NULL;

   push(&head,30);

   delete_list(&head);  //always remember to free the allocated memory before exiting your modules

   return 0;
}

For operations that doesn't imply the modification of the head reference you may pass this pointer as value, here is an example of a function of this kind that will only search the list for a specific node:

node *last_node(node *head){
    node *curr=NULL;
    while(head)
    {
        curr=head;
        head=head->next;
    }
    return curr;
}

Deleting a node is accomplished by first, locating the node and then freeing the memory. You always need to make sure that the previous node in the list is aware that the next node is NULL after you delete the consecutive node.

void delete_list(node **head)
{
    while(*head)
        remove_head_node(head);
}

int pop(node **head)
{
    if(*head)
    {
        node *curr = *head;
        int temp = curr->val;
        *head = curr->next;
        free(curr);
        return temp;
    }
    return 0;
}

Here is a link to a MinGW project that illustrate SLL implementation.