Linked Lists in C: push, pop, shift and unshift

A sound understanding of linked lists and how to use them is a prerequisite for programming in C, or indeed most programming languages for that matter.   Most scripting languages provide built-in helper functions for dealing with arrays and linked lists, C on the other hand doesn’t – so you have to do it yourself.   Luckily though, there’s really not that much to it, but if you’re new to C then it might be quite daunting to realise you’re in the deep end with no arm bands!

There are plenty of great books and online tutorials that cover the topic very well, however personally I prefer to look at working examples and so I have created a few for those who are already aware of the theory and want to get on with programming.

All of the examples in this tutorial use a fairly simple struct for linked list nodes containing just a pointer to an integer and the next node in the list.   (You can of course change your nodes to better suit your requirements, but you will have to change the helper functions a bit to reflect this.)

It should be fairly simple to figure out what what’s going on from the inline comments, so I’ll stop waffling now and get on with the code!

Node

Here is the struct that defines each item in the list.

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

Note that I have decided to store each item’s data as an integer, but you can of course choose other types so long as you alter the functions below to accommodate this type. Basically, the struct can be whatever so long as it has a pointer to the next item in the list.

Push

Creates a new node and add it onto the end of the list.

/**
 * Adds a node onto the end of the list
 *
 */
void push(struct node** item, int data)
{
    struct node *current;
    struct node *endItem;
    
    current = *item;
    
    /* See if the passed value is a node */
    if (current)
    {
        /* See if this is the last node in the list */
        if (current->next == NULL)
        {
            /* This is the last item, so create a new node to go on the end */
            
            /* Allocate memory for the new node */
            endItem = malloc(sizeof(struct node));
            
            /* Set the value */
            endItem->val = data;
            
            /* Set the pointer to the next item to be NULL (there isn't a next, this will be the last item) */
            endItem->next  = NULL;
            
            /* Set the next pointer in the last item to the new item, making the new item now the last one */
            current->next = endItem;
            
            return;
        }
        else
        {
            /* This is not the last item, recurse to the next one */
            return push(¤t->next, data);
        }
    }
    
    /* There are no nodes in the list, so create a new node and it will be the first in the list */
    endItem = malloc(sizeof(struct node));
    
    /* Set the value */
    endItem->val = data;
    
    /* Set the pointer to the next item to be NULL (there isn't a next, this will be the last item) */
    endItem->next  = NULL;
    
    /* Set the passed pointer to point to the new node */
    *item = endItem;
}

Pop

Removes the last node from the end of the list and return its value.

/**
 * Remove the last item and return the value
 *
 */
int pop (struct node **item, int *p)
{
    struct node *current;
    
    current = *item;
    
    if (current)
    {
        /* See if the current item specifies a proceding item */
        if (current->next)
        {
            /* There is a next item, so see if it is the last one */
            if (current->next->next == NULL)
            {
                /* The next item is the last one, so get its value */
                *p = current->next->val;
                
                /* Free the memory reserved for the last item */
                free(current->next);
                
                /* Remove the pointer to the last item */
                current->next = NULL;
                
                return 0;
            }
            
            /* Move on to the next item */
            return pop(¤t->next, p);
        }
        
        /* There aren't any more items, this is the last one and therefore also the first */
        *p = current->val;
        
        /* Release the memory reserved for it */
        free(*item);
        
        /* Set the head node to NULL */
        *item = NULL;
        
        return 0;
    }
    
    /* There are no items in the list */
    p = NULL;
    
    return -1;
}

Shift

Removes the first element from the list and return its value.

/**
 * Remove the first item in the list
 *
 */
int shift(struct node **head, int *p)
{
    struct node *firstNode;
  
    firstNode = *head;

    /* See if there is a first node */
    if (firstNode == NULL)
    {
        /* There isn't, so return -1*/
        return -1;
    }
     
    /* Set the passed pointer, the pointer to the first node in the list, to the next node */
    *head = firstNode->next;
    
    /* Get the value from the first node before we free() it */
    *p = firstNode->val;
    
    /* Deallocate the first node */
    free(firstNode);
    
    /* Return 0, all ok */
    return 0;
}

Unshift

Creates a new node and add it onto the beginning of the list.

/**
 * Add a node onto the beginning of the list
 *
 */
void unshift(struct node** head, int data)
{
    /* Declare and reserve memory for the new item */
    struct node* newNode = malloc(sizeof(struct node));
    
    /* Se the new node's value */
    newNode->val = data;
    
    /* Set the next item to be the item that was previously first */
    newNode->next = *head;
    
    /* Set the pointer to the first item to this new item */
    *head = newNode;
}
Things to bear in mind
pop() and shift(), there is a call to free() on the node we are removing.   Free() does exactly what it says on the tin; it frees the memory reserved for the variable addressed by the the pointer it is passed.   Note that before we create a new node, we must first allocate memory for it by calling malloc().   Free() deallocates this space so that the process can re-use it again in the future.   If we didn’t call free() then we would have to keep using more and memory to store new nodes in, which could soon get out of hand if you create and delete lots of nodes.

So how do we make sure we’re not eating memory?

I made a simple function (see below) that continuously adds and then removes nodes onto and from the list – if we are correctly freeing memory then we should see that the memory used by the program when run will be stable.

int main()
{
    struct node *head;
    int i, j;

    head = NULL;
    
    while (1)
    {
    
        for (i=1;i<6;i++)
        {
            /* Add to the beginning */
            unshift(&head, i);
            printf("Unshift: %d\n", i);
        }
        
        for (i=6;i<11;i++)
        {
            /* Add to the end */
            push(&head, i);
            printf("Push: %d\n", i);
        }
        
        for (i=1;i<6;i++)
        {
            /* Remove from the end */
            if (pop(&head, &j) == 0)
            {
                printf("Pop: %d\n", j);
            }
        }
        
        for (i=1;i<6;i++)
        {
            /* Remove from the beginning */
            if (shift(&head, &j) == 0)
            {
                printf("Shift: %d\n", j);
            }
        }
        
        /* Functions in a different order */
        
        for (i=1;i<6;i++)
        {
            /* Add to the end */
            push(&head, i);
            printf("Push: %d\n", i);
        }

        for (i=6;i<11;i++)
        {
            /* Add to the beginning */
            unshift(&head, i);
            printf("Unshift: %d\n", i);
        }

        
        for (i=1;i<6;i++)
        {
            /* Remove from the beginning */
            if (shift(&head, &j) == 0)
            {
                printf("Shift: %d\n", j);
            }
        }

        for (i=1;i<6;i++)
        {
            /* Remove from the end */
            if (pop(&head, &j) == 0)
            {
                printf("Pop: %d\n", j);
            }
        }
    }
    
    return 0;    
}

Compile:
gcc llist.c -ollist

Don’t forget rights
chmod +x llist

Run:
./llist

Now, in another terminal we can watch how much memory the program is running:
watch 'ps aux | grep llist'

Just for fun
Comment one of the free() calls from either pop() or shift(), recompile, run and watch the new program.   You should see the memory it is using steadily inrease.

Download:

Here’s a file containing all of the above functions and the test.
Linked List Tutorial v1.0

This entry was posted in C and tagged , , , , , , , , , , , , , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *