Implementation of Singly Linked List in C

A singly linked list is a data structure consisting of nodes where each node has a pointer to the next node in the list and the last node points to a null pointer marking the end of the list. Linked list provides a versatile way to organize a collection of data in system programming. Nodes in a linked list can be added, removed or modified. The program shown below is a very good starting point to understand singly linked list better.

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

#define OK  0
#define NG -1

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


void printList();
int insertNodeFirst(int data);
int insertNodeLast(int data);
int deleteNodeIfDataIs(int data);

struct node* listHead = NULL;

void printList()
{
    struct node* currentNode = listHead;
    
    printf("Printing linked list\n\n");
    
    while(currentNode != NULL)
    {
        printf("| %d | -> ", currentNode->data);
        
        currentNode = currentNode->next;
    }
    
    printf("NULL\n\n");
}

int insertNodeFirst(int data)
{
    int retVal = NG;
    struct node* newNode = NULL;
    struct node* temp = listHead;
    
    newNode = (struct node*)malloc(sizeof(struct node));
    
    if (newNode != NULL)
    {
        retVal = OK;
        newNode->data = data;
        listHead = newNode;

        if (listHead == NULL)
        {
            newNode->next = NULL;
        }
        else
        {
            newNode->next = temp;
        }
    }
    
    return retVal;
}

int insertNodeLast(int data)
{
    int retVal = NG;
    struct node* newNode = NULL;
    struct node* temp = listHead;
    
    newNode = (struct node*)malloc(sizeof(struct node));
    
    if (newNode != NULL)
    {
        retVal = OK;
        newNode->data = data;
        newNode->next = NULL;
        
        if (listHead == NULL)
        {
            listHead = newNode;
        }
        else
        {
            while (temp->next != NULL)
            {
                temp = temp->next;
            }
            
            temp->next = newNode;
        }
    }
    
    return retVal;
}

int deleteNodeIfDataIs(int data)
{
    int retVal = NG;
    struct node* temp = listHead;
    struct node* prev;

    do
    {
        if (temp == NULL)
        {
            continue;
        }
        
        if (temp->data == data)
        {
            retVal = OK;
            listHead = temp->next;
    
            continue;
        }
        
        while (temp != NULL)
        {
            if (temp->data == data)
            {
                retVal = OK;
                prev->next = temp->next;
    
                break;
            }
            
            prev = temp;
            temp = temp->next;
        }
                
    } while (0);
    
    if (retVal == OK)
    {
        free(temp);
    }
        
    return retVal;
}

int main()
{ 
    insertNodeFirst(1);
    insertNodeFirst(2);
    insertNodeFirst(3);
    insertNodeFirst(4);
    insertNodeFirst(5);
    
    printList();        // | 5 | -> | 4 | -> | 3 | -> | 2 | -> | 1 | -> NULL
    
    deleteNodeIfDataIs(4);
    
    printList();        // | 5 | -> | 3 | -> | 2 | -> | 1 | -> NULL
    
    insertNodeLast(6);
    insertNodeLast(7);

    printList();        // | 5 | -> | 3 | -> | 2 | -> | 1 | -> | 6 | -> | 7 | -> NULL
    
    return 0;
}

About Program:

This C program demonstrates a singly linked list. Basic supported functionalities include insert node at at first, insert node at last and delete a node if a data is found.

Code walk-through:

The main() function inserts nodes, deletes node and prints the list from its function body.

The below lines actually inserts few nodes into the list by inserting at the start of list,

insertNodeFirst(1);
    insertNodeFirst(2);
    insertNodeFirst(3);
    insertNodeFirst(4);
    insertNodeFirst(5);
    
    printList();        // | 5 | -> | 4 | -> | 3 | -> | 2 | -> | 1 | -> NULL

The following lines deletes a node if the data is 4 and prints the list,

deleteNodeIfDataIs(4);
    
    printList();        // | 5 | -> | 3 | -> | 2 | -> | 1 | -> NULL

The below code section inserts couple of nodes at the last of the linked list and prints the list,

insertNodeLast(6);
    insertNodeLast(7);
 
    printList();        // | 5 | -> | 3 | -> | 2 | -> | 1 | -> | 6 | -> | 7 | -> NULL

Analysis of printList()

*struct node currentNode = listHead; sets the *currentNode*** variable to the head of the linked list.

The below while-loop iterates through the entire linked list and prints the individual data values.

while(currentNode != NULL)
    {
        printf("| %d | -> ", currentNode->data);
        
        currentNode = currentNode->next;
    }

Analysis of insertNodeFirst()

int insertNodeFirst(int data)
{
    int retVal = NG;
    struct node* newNode = NULL;
    struct node* temp = listHead;
    
    newNode = (struct node*)malloc(sizeof(struct node));
    
    if (newNode != NULL)
    {
        retVal = OK;
        newNode->data = data;
        listHead = newNode;
 
        if (listHead == NULL)
        {
            newNode->next = NULL;
        }
        else
        {
            newNode->next = temp;
        }
    }
    
    return retVal;
}

A new node is created using the malloc() function and assigns data to its data member. Head of the linked list is updated with the newly created node as the node is to be inserted at the front.

In case if the list was empty, then the newly created node’s next pointer is assigned as NULL else the next pointer is assigned with the previous header node.

Analysis of insertNodeLast()

int insertNodeLast(int data)
{
    int retVal = NG;
    struct node* newNode = NULL;
    struct node* temp = listHead;
    
    newNode = (struct node*)malloc(sizeof(struct node));
    
    if (newNode != NULL)
    {
        retVal = OK;
        newNode->data = data;
        newNode->next = NULL;
        
        if (listHead == NULL)
        {
            listHead = newNode;
        }
        else
        {
            while (temp->next != NULL)
            {
                temp = temp->next;
            }
            
            temp->next = newNode;
        }
    }
    
    return retVal;
}

Here also a new node is created using the malloc() function. The data is assigned to its data member and NULL is assigned to the new node’s next pointer since the node is to be inserted at the end of the list.

If the list is empty then the new node is assigned as the head node. Otherwise the while-loop iterates to the end of the list and inserts the new node there.

Analysis of deleteNodeIfDataIs()

int deleteNodeIfDataIs(int data)
{
    int retVal = NG;
    struct node* temp = listHead;
    struct node* prev;
 
    do
    {
        if (temp == NULL)
        {
            continue;
        }
        
        if (temp->data == data)
        {
            retVal = OK;
            listHead = temp->next;
    
            continue;
        }
        
        while (temp != NULL)
        {
            if (temp->data == data)
            {
                retVal = OK;
                prev->next = temp->next;
    
                break;
            }
            
            prev = temp;
            temp = temp->next;
        }
                
    } while (0);
    
    if (retVal == OK)
    {
        free(temp);
    }
        
    return retVal;
}

A do-while loop is used to facilitate in an early exit from the function if there is a NULL pointer passed or if the data being searched is found at the head node itself.

If the data being searched is not at the head of the list then the nested while loop will iterate through the individual list nodes and if found, then the next pointer of the previous node is updated to skip the matched node which will be later deleted using the free() function call.

General Note:

In this code there are return values implemented to check whether a particular function execution is a success or not, but the return values are discarded as this article is only an example to show the functionality of a singly linked list.

In the case of production code the return values of the functions needs to be evaluated before proceeding to the next statement of the program and should also service the error codes.