Linked Lists in the C Programming Language – Define, Print, and Erase Elements of Linked Lists

In this C programming lesson, we provide a concise tutorial on linked lists in C. In particular, we explain how to

• Define a linked list by using C structures
• Develop minimal C code that creates a linked list
• Print data stored in nodes of a linked list
• Erase all nodes in a linked list

Note that in this tutorial we keep the implementation of linked lists as simple as possible in order not to blur the presentation with too many C implementation details or advanced C concepts. The implementation is not optimal and not completely robust. However, it is simple and consequently, it enables a student to understand the basic concepts.

The YouTube tutorial is given below.

Copyright notice

Copyright notice: this lesson, YouTube video, developed code files, and documents should not be copied, redistributed, or posted on public or private websites, public or private code repositories, or social media platforms. This lesson and all the provided study materials are strictly for personal use. Without the permission of the author, this lesson and the provided material should not be used for commercial purposes and for training of engineers working in companies. This lesson and the provided material should not be used as lecture materials on online learning platforms and in university courses. This lesson and the provided material should not be used to train an AI algorithm or a large language model.

Introduction to Linked Lists in the C programming Language

• A linked list is a data structure that consists of nodes that are linked together by using pointers.
• A node in a linked list is a data structure consisting of stored data (a data object) and a pointer to the next node in the linked list.
• Stored data can be integers, floats, strings, objects, arrays, or any other user-defined data type

The figure below represents a node of a linked list.

In the figure above, a node contains two parts: stored data and pointer to the next node. Every node has a unique memory address that the pointer of the preceding node in the linked points to.

• In this tutorial, we call the pointer to the next node as the link. By using this naming convention a node of a linked list is shown in the figure below.

• To properly define a linked list, we need to declare a head pointer of the struct node. We call the head pointer simply as head in this tutorial.
• For a non-empty linked list, head points to the first node in the linked list. 
• The link of the last node in the linked list should be a null pointer. This pointer denotes the end of the list. In this tutorial, we use NULL to mark the end of the list.
• By using the above explained conventions, we can illustrate our firs linked list. Figure below shows a linked list consisting of three nodes.

Consider the figure shown above. The linked list starts with a head pointer (called head) that points to the first node in the linked list. The fist node stores some data (integers, floats, objects, etc) and a pointer to the next node. This pointer is called as link 1. Similarly, the second node stores data, and link2 which points to the third node. The third node stores data. However, since there is no node below the third node, its link is equal to the NULL pointer. The node whose pointer is a null pointer represents the last node in the linked list.

• Linked lists are dynamic data structures. In the C programming language, nodes are created by using the malloc() function and returned pointers. A pointer points to the node struct object and not to the data objects stored in the node. We can expand the list by adding new nodes or shrinking the list by erasing some nodes.

Implementation of Linked List in the C programming Language

We implement linked lists in the C programming language by using C structures. We use the keyword struct to define a C structure. In fact, a node of a linked list is implemented as a structure. We do it like this:

struct node
{
    int stored_data;
    
    struct node *link;
};

For simplicity, in this particular case, we assume that the data stored in the structure is an integer value. The above declared node structure has a link pointer that points to struct node.

The C code shown below explains how to

1. Create a linked list that consists of three nodes.
2. Print the data entries stored in the nodes of the linked list.
3. Erase all the entries of the linked list.

First, we present the complete code, and then we explain the most important parts of the code. The code is given below.

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

struct node
{
    int stored_data;
    
    struct node *link;
};

int main()
{
    struct node* head=NULL;
    struct node* p_new_node=malloc(sizeof(struct node));
    
    p_new_node->stored_data=1;
    p_new_node->link=head;
    head=p_new_node;

    // create and link the second node 
    p_new_node=malloc(sizeof(struct node));
    p_new_node->stored_data=2;
    p_new_node->link=head;
    head=p_new_node;

    // create and link the third node 
    p_new_node=malloc(sizeof(struct node));
    p_new_node->stored_data=3;
    p_new_node->link=head;
    head=p_new_node;

    p_new_node=NULL;

    struct node* p_current_node=head;
    int counter=3;

    while(p_current_node!=NULL)
    {
        int number=p_current_node->stored_data;
        printf("Value stored at the node %d is %d \n", counter, number);
        counter--;
        p_current_node=p_current_node->link;
    }

    p_current_node=head;

    while(p_current_node!=NULL)
    {
        head=p_current_node->link;
        free(p_current_node);
        p_current_node=head;
    }

    // check if we erased the linked list
    if (head==NULL)
    {

        printf("List is erased! \n ");
    }

    return 0;
}

You can save this file as “list1.c” and you can compile it by using the gcc compiler like this (from the command line):

gcc -Wall -W -o list1 list1.c

Let us explain the code.

To create a linked list, we first need to declare a head pointer and create a new node, and return a pointer to this new node. We do it like this:

 struct node* head=NULL;
 struct node* p_new_node=malloc(sizeof(struct node));

The head pointer is denoted by “head” and a pointer to the new node is created by “p_new_node”. We use the function malloc() to reserve space for the new node. This function reserves the memory space and returns the pointer to the reserved memory space. To calculate how many bytes our node will need, we use the operator sizeof(). These two operations are illustrated in the figure below.

To store data in the newly created node and to integrate our new node in the linked list, we use the following three statements

   p_new_node->stored_data=1;
   p_new_node->link=head;
   head=p_new_node;

We first store the number 1 in the node. Then, we set the link of the newly created node. Since head is NULL, the link of the new node will be NULL. This means that this link is the end of the linked list. Finally, we move head such that it points to the newly created node. Now, the newly created node is integrated in the linked list. This is shown in the figure below.

Now, we repeat this procedure to create and link the second node. This is done by using this code block

    // create and link the second node 
    p_new_node=malloc(sizeof(struct node));
    p_new_node->stored_data=2;
    p_new_node->link=head;
    head=p_new_node;

We reserve a new memory space for the second node and return a pointer to this memory space. We then store the data in the second node. Then, we link the second node and finally we move the head up such that it points to the second node. These steps are illustrated in the two figures given below.

Finally, we use the following code block to create and link the third node. The code is given below

 // create and link the third node 
    p_new_node=malloc(sizeof(struct node));
    p_new_node->stored_data=3;
    p_new_node->link=head;
    head=p_new_node;

This process is illustrated in the figure below.

Finally, we can set the “p_new_node” pointer to NULL since we do not need it anymore:

    p_new_node=NULL;

This is perfectly fine since the head pointer points at the top of the linked list.

To print the entries of the linked list we use the following code block

    struct node* p_current_node=head;
    int counter=3;

    while(p_current_node!=NULL)
    {
        int number=p_current_node->stored_data;
        printf("Value stored at the node %d is %d \n", counter, number);
        counter--;
        p_current_node=p_current_node->link;
    }

This code block will iterate through the nodes of the linked list by using the pointer p_current_node. At the beginning, we set p_current_node to point the top of the linked list. The while loop will be executed until p_current_node becomes a NULL pointer. The NULL pointer means that we have reached the end of the list. In every iteration of the while loop, we print the entry stored in the current node (that is pointed by the current value of p_current_node). Then, we simply move through the list by using this statement:

p_current_node=p_current_node->link

Before we can compile and execute the program, it is very important to erase all the nodes in the linked list. Namely, since we used the function malloc() to allocate the memory space for nodes. We need to free this memory space. Otherwise, we will create a memory leak which a serious bug. In this particular case since we only have three nodes, our system will not even notice this small memory leak. However, if you are heaving million of nodes, then the memory leak can be significant. We erase the linked list by using this code block.

    p_current_node=head;

    while(p_current_node!=NULL)
    {
        head=p_current_node->link;
        free(p_current_node);
        p_current_node=head;
    }

    // check if we erased the linked list
    if (head==NULL)
    {

        printf("List is erased! \n ");
    }