Singly Linked List Program in C

In this article, we will implement and understand the singly linked list program in C. We will not just implement it, we will understand what is singly linked list, working of the linked list, uses of singly linked list, what will be the time complexity of the different operations in the singly linked list. So, let’s discuss what is a singly linked list.

Singly Linked List

A certain type of linked list known as a single linked list which can only be traversed from head to final node (tail). Each item in a linked list is referred to as a node. Data and a pointer to the following node are both contained in a single node that aids in keeping the list’s structure.

The head node, which points to the list’s root node and facilitates access to all other elements, is the first node. We determine the last node as the tail node, as it is pointing towards the NULL pointer.
Let’s see representation of node of the singly linked list in c:

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

Operations on singly linked list:

1. Insertion
The procedure for adding a new node to the beginning of a singly linked list is as follows.

  • Point the new node at HEAD.
  • Make the HEAD point to the new node.

void insertStart(struct Node** head, int data){
    
    // dynamically create memory for this newNode
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    
    // assign data value
    newNode->data = data;
    // change the next node of this newNode 
    // to current head of Linked List
    newNode->next = *head;

    //re-assign head to this newNode
    *head = newNode;
    printf("Inserted %d\n",newNode->data);
}

2. Deletion
The first node of the singly linked list can be deleted as follows,

  • Make the HEAD point to its next element.
void deleteStart(struct Node** head){
    struct Node* temp = *head;
  
    // If head is NULL it means Singly Linked List is empty
    if(*head == NULL){
        printf("Impossible to delete from empty Singly Linked List");
        return;
    }
    
    // move head to next node
    *head = (*head)->next;
    printf("Deleted: %d\n", temp->data);
    free(temp);
}

3. Display
To display the entire singly linked list, we need to traverse it from first to last.
Linked list nodes cannot be randomly accessed, in contrast to arrays. We must therefore go through all (n-1) elements in order to reach the nth element.

void display(struct Node* node){
    printf("\nLinked List: ");
    // as linked list will end when Node is Null
    while(node!=NULL){
        printf("%d ",node->data);
        node = node->next;
    }
    printf("\n");
}

Code Implementation

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

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

void deleteStart(struct Node** head){
    struct Node* temp = *head;
  
    // If head is NULL it means Singly Linked List is empty
    if(*head == NULL){
        printf("Impossible to delete from empty Singly Linked List");
        return;
    }
    
    // move head to next node
    *head = (*head)->next;
    printf("Deleted: %d\n", temp->data);
    free(temp);
}

void insertStart(struct Node** head, int data){
    
    // dynamically create memory for this newNode
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    
    // assign data value
    newNode->data = data;
    // change the next node of this newNode 
    // to current head of Linked List
    newNode->next = *head;

    //re-assign head to this newNode
    *head = newNode;
    printf("Inserted %d\n",newNode->data);
}

void display(struct Node* node){
    printf("\nLinked List: ");
    // as linked list will end when Node is Null
    while(node!=NULL){
        printf("%d ",node->data);
        node = node->next;
    }
    printf("\n");
}

int main()
{
    struct Node* head = NULL;

    insertStart(&head,100);
    insertStart(&head,80);
    insertStart(&head,60);
    insertStart(&head,40);
    insertStart(&head,20);
    
    display(head);
    
    deleteStart(&head);
    deleteStart(&head);
    display(head);
    
    return 0; 
}

Output

Inserted 100
Inserted 80
Inserted 60
Inserted 40
Inserted 20

Linked List: 20 40 60 80 100 
Deleted: 20
Deleted: 40

Linked List: 60 80 100 

Time Complexity

  • Inserting a new node at the start is an O(1) operation.
  • Deleting the first node of a singly linked list is an O(1) operation.
  • Since the entire linked list is traversed, the operation costs us O(N) time complexity.

Uses of Linked List

Some of the real-world applications of the singly linked list are as follows:

  • Used to store polynomials with one or two variables.
  • Serve as a foundation for various data structures, such as Queue, Stack, and Graph.
  • A strategy for operating system-based file allocation techniques.
  • Observe the amount of free space on the backup disk. The open spaces can all be connected.
  • A circular linked list can be used in turn-based games to determine which player is about to be played. We go on to the next player after that player has completed their turn.
  • To retain a record of anything that may be navigated between successively, such as music, films, photographs, web pages, etc.

Conclusion
This blog tries to discuss the implementation of singly linked list program in C. Having knowledge about data structures topics like singly linked list will definitely help in improving your career. After going over all of its features and advantages, we finally recognised some of its practical uses.

Other C Programs

C Program for Binary Search
C Program to Add Two Numbers
C Program to Calculate Percentage of 5 Subjects
C Program to Convert Binary Number to Decimal Number
C Program to Convert Celsius to Fahrenheit
C Program to Convert Infix to Postfix
C Program to Find Area of Circle
C Program to Find Roots of Quadratic Equation
C program to Reverse a Linked List
C program to reverse a number
Ascending Order Program in C
Menu Driven Program For All Operations On Doubly Linked List in C
C Program for Armstrong Number
C Program For Merge Sort For Linked Lists
C program for performing Bubble sort on Linked List
Hello World Program in C
Perfect Number Program in C
Leap Year Program in C
Odd Even Program in C
Selection Sort Program in C
Linear Search Program in C
While Loop Program in C
C Program to Swap Two Numbers
Calculator Program in C Language
Simple Interest Program in C
Compound Interest Program in C
Priority Scheduling Program in C
Doubly Linked List Program in C
FCFS Scheduling Program in C
Insertion Sort Program in C

Leave a Reply

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