Types of Linked List - Singly Linked List

Singly Linked List -

A singly linked list is the simplest type of linked list whose each node consists of two parts, one DATA field and another NEXT field which contains a pointer to the next node i.e., it stores the address of next node.

Representation of Singly Linked List -

Operations in Singly Linked List -

• Inserting a new node in a Singly Linked List -

1. Inserting a node at the beginning of a singly linked list- We first allocate memory space for new node. Set its DATA part with the value and the NEXT part is initialized with the address of the first node stored in HEAD. Since we are adding the new node at the beginning i.e., it will be our first node. So now we will point HEAD towards this new node that is HEAD will store the address of this new node.

C program to insert node at the beginning of singly linked list -

#include <stdio.h>
#include <malloc.h>

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

void insertatbeg(struct node** head)
{
    int n;
    printf("Enter value to insert at beginning: ");
    scanf("%d",&n);
    struct node* val=(struct node*)malloc(sizeof(struct node));
    val->data=n;
    val->next=*head;
    *head=val;

}
void display(struct node* head)
{
    struct node* t=head;
    while(t!=NULL)
    {
        printf("%d => ",t->data);
        t=t->next;
    }
    printf("NULL \n");
    
}

struct node* head=NULL;
void main()
{
    insertatbeg(&head);
    display(head);
}

Output -

Enter value to insert at beginning: 2
2 => NULL

2. Inserting a node at the end of singly linked list- We first allocate memory space for new node. Set its DATA part with the value and the NEXT part is initialized with NULL. Then we will use a pointer variable t and initialize it with HEAD i.e., t will point to the first node. In while loop we will traverse through the linked list to reach the last node. Once reached, we will change last node's NEXT pointer to store the address of the new node and point the NEXT pointer of new node to NULL.

C program to insert a node at the end of singly linked list-

#include <stdio.h>
#include <malloc.h>

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

void insertatend(struct node** head)
{
    int n;
    printf("Enter value to insert at end: ");
    scanf("%d",&n);
    struct node* val=(struct node*)malloc(sizeof(struct node));
    val->data=n;
    val->next=NULL;
    if(*head==NULL)
    {
        *head=val;
        return;
    }
    struct node* t=*head;
    while(t->next!=NULL)
    {
        t=t->next;
    }
    t->next=val;
}
void display(struct node* head)
{
    struct node* t=head;
    while(t!=NULL)
    {
        printf("%d => ",t->data);
        t=t->next;
    }
    printf("NULL \n");
    
}

int main()
{
    struct node* head=NULL;
    insertatend(&head);
    insertatend(&head);
    insertatend(&head);
    display(head);
    return 0;
}

Output-

Enter value to insert at end: 1
Enter value to insert at end: 2
Enter value to insert at end: 3
1 => 2 => 3 => NULL

Now let us write a c program to implement both the operations that we just read to get a clear idea about them i.e., c program to insert a new node at the beginning and at the end of a singly linked list.

C program to insert a node at the beginning and at the end of a singly linked list -

#include <stdio.h>
#include <malloc.h>

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

void insertatbeg(struct node** head)
{
    int n;
    printf("Enter value to insert at beginning: ");
    scanf("%d",&n);
    struct node* val=(struct node*)malloc(sizeof(struct node));
    val->data=n;
    val->next=*head;
    *head=val;

}

void insertatend(struct node** head)
{
    int n;
    printf("Enter value to insert at end: ");
    scanf("%d",&n);
    struct node* val=(struct node*)malloc(sizeof(struct node));
    val->data=n;
    val->next=NULL;
    if(*head==NULL)
    {
        *head=val;
        return;
    }
    struct node* t=*head;
    while(t->next!=NULL)
    {
        t=t->next;
    }
    t->next=val;
}
void display(struct node* head)
{
    struct node* t=head;
    while(t!=NULL)
    {
        printf("%d => ",t->data);
        t=t->next;
    }
    printf("NULL \n");
    
}

struct node* head=NULL;
void main()
{
    int c=0;
    do
    {
        printf("       || Menu ||       \n");
        printf("Press 1 to insert at beginning \n");    
        printf("Press 2 to insert at end \n");    
        printf("Enter your choice: ");
        printf("\n");    
        scanf("%d",&c);
        switch(c)
        {
            case 1:
                insertatbeg(&head);
                display(head);
                break;
            case 2:
                insertatend(&head);
                display(head);
                break;
            default:
                printf("Invalid Input!!!!!");
                break;
        }
    } while (c!=3);
}

Output -

       || Menu ||       
Press 1 to insert at beginning 
Press 2 to insert at end       
Enter your choice: 
1
Enter value to insert at beginning: 2
2 => NULL 
       || Menu ||
Press 1 to insert at beginning
Press 2 to insert at end 
Enter your choice:
2
Enter value to insert at end: 5
2 => 5 => NULL 
       || Menu ||
Press 1 to insert at beginning 
Press 2 to insert at end
Enter your choice: 
1
Enter value to insert at beginning: 1
1 => 2 => 5 => NULL 
       || Menu ||
Press 1 to insert at beginning
Press 2 to insert at end
Enter your choice: 
3
Invalid Input!!!!!

3. Inserting a node after a given node in singly linked list- We first allocate memory space for new node. Then we will take a pointer variable temp and initialize it with HEAD that is, temp will point to the first node. Then we will store the value to be inserted in new node's data part. In while loop, we will traverse through the linked list to reach the node after which we want to insert new node. Once reached, we will point the next pointer in such a way that the new node is inserted after desired node.

C program to insert a node after a given node in singly linked list-

#include <stdio.h>
#include <malloc.h>

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

void insertatend(struct node** head)
{
    int n;
    printf("Enter value to insert at end: ");
    scanf("%d",&n);
    struct node* val=(struct node*)malloc(sizeof(struct node));
    val->data=n;
    val->next=NULL;
    if(*head==NULL)
    {
        *head=val;
        return;
    }
    struct node* t=*head;
    while(t->next!=NULL)
    {
        t=t->next;
    }
    t->next=val;
}

void insertafernode(struct node** head)
{
    int n;
    printf("Enter value of node after which you want to insert : ");
    scanf("%d",&n);
    struct node* nw=(struct node*)malloc(sizeof(struct node));
    struct node* temp=*head;
    while(temp->data!=n)
    {
        temp=temp->next;
    }
    nw->data=12;
    nw->next=temp->next;
    temp->next=nw;
}

void display(struct node* head)
{
    struct node* t=head;
    while(t!=NULL)
    {
        printf("%d => ",t->data);
        t=t->next;
    }
    printf("NULL \n");
    
}

int main()
{
    struct node* head=NULL;
    insertatend(&head);
    insertatend(&head);
    insertatend(&head);
    insertafernode(&head);
    display(head);
    return 0;
}

Output -

Enter value to insert at end: 9
Enter value to insert at end: 10
Enter value to insert at end: 11
Enter value of node after which you want to insert : 10
9 => 10 => 12 => 11 => NULL

4. Inserting a node before a given node in a singly linked list- We first allocate memory space for new node. Then we will take a pointer variable temp and initialize it with HEAD that is, temp will point to the first node. Then we will store the value to be inserted in new node's data part. In while loop, we will traverse through the linked list to reach the node before which we want to insert new node. Once reached, we will point the next pointer in such a way that the new node is inserted before desired node.

C program to insert a node before a given node in singly linked list-

#include <stdio.h>
#include <malloc.h>

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

void insertatend(struct node** head)
{
    int n;
    printf("Enter value to insert at end: ");
    scanf("%d",&n);
    struct node* val=(struct node*)malloc(sizeof(struct node));
    val->data=n;
    val->next=NULL;
    if(*head==NULL)
    {
        *head=val;
        return;
    }
    struct node* t=*head;
    while(t->next!=NULL)
    {
        t=t->next;
    }
    t->next=val;
}

void insertbeforenode(struct node** head)
{
    int n;
    printf("Enter value of node before which you want to insert : ");
    scanf("%d",&n);
    struct node* nw=(struct node*)malloc(sizeof(struct node));
    struct node* temp=*head;
    while(temp->next->data!=n)
    {
        temp=temp->next;
    }
    nw->data=12;
    nw->next=temp->next;
    temp->next=nw;
}

void display(struct node* head)
{
    struct node* t=head;
    while(t!=NULL)
    {
        printf("%d => ",t->data);
        t=t->next;
    }
    printf("NULL \n");
    
}

int main()
{
    struct node* head=NULL;
    insertatend(&head);
    insertatend(&head);
    insertatend(&head);
    display(head);
    insertbeforenode(&head);
    display(head);
    return 0;
}

Output-

Enter value to insert at end: 9
Enter value to insert at end: 10
Enter value to insert at end: 11
9 => 10 => 11 => NULL 
Enter value of node before which you want to insert : 10
9 => 12 => 10 => 11 => NULL

• Deleting a node from a Singly Linked List -

1. Deletion of first node - First we will check if linked list exists or not. If HEAD == NULL , it indicates that there are no nodes in the linked list. Then we take a pointer variable del that points to HEAD i.e., it points to the first node which we are going to delete. Then we will point the HEAD to the next node of first node and finally we will free the memory occupied by the node pointed by del and return to the free pool.

C program to delete first node from a singly linked list-

#include <stdio.h>
#include <malloc.h>

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

void insertatend(struct node** head)
{
    int n;
    printf("Enter value to insert at end: ");
    scanf("%d",&n);
    struct node* val=(struct node*)malloc(sizeof(struct node));
    val->data=n;
    val->next=NULL;
    if(*head==NULL)
    {
        *head=val;
        return;
    }
    struct node* t=*head;
    while(t->next!=NULL)
    {
        t=t->next;
    }
    t->next=val;
}

void deleteathead(struct node** head)
{
    if(*head==NULL)
    {
        return;
    }
    
    struct node* del=*head;
    *head=(*head)->next;

    free(del);
}
void display(struct node* head)
{
    struct node* t=head;
    while(t!=NULL)
    {
        printf("%d => ",t->data);
        t=t->next;
    }
    printf("NULL \n");
    
}

int main()
{
    struct node* head=NULL;
    insertatend(&head);
    insertatend(&head);
    insertatend(&head);
    display(head);
    deleteathead(&head);
    display(head);

    return 0;
}

Output-

Enter value to insert at end: 2
Enter value to insert at end: 3
Enter value to insert at end: 5
2 => 3 => 5 => NULL  
3 => 5 => NULL

2. Deletion of last node- First we will check if linked list exists or not. If HEAD == NULL , it indicates that there are no nodes in the linked list. Then we will check the last node which we are deleting is the only node in the list or not if yes then we will call deleteathead() function that we just created. If not, then we will take a pointer variable temp that points to HEAD i.e., it points to the first node. Then we will traverse through the linked list till we reach the last node. Once reached, we will free the memory occupied by the node and return to the free pool.

C Program to delete last node from a singly linked list-

#include <stdio.h>
#include <malloc.h>

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

void insertatend(struct node** head)
{
    int n;
    printf("Enter value to insert at end: ");
    scanf("%d",&n);
    struct node* val=(struct node*)malloc(sizeof(struct node));
    val->data=n;
    val->next=NULL;
    if(*head==NULL)
    {
        *head=val;
        return;
    }
    struct node* t=*head;
    while(t->next!=NULL)
    {
        t=t->next;
    }
    t->next=val;
}

void deleteathead(struct node** head)
{
    if(*head==NULL)
    {
        return;
    }
    
    struct node* del=*head;
    *head=(*head)->next;

    free(del);
}
void deletend(struct node** head)
{
    if(*head==NULL)
    {
        return;
    }
    if((*head)->next==NULL)
    {
        deleteathead(head);
        return;
    }
    struct node* temp=*head;
    while(temp->next->next!=NULL)
    {
        temp=temp->next;
    }
    struct node* del=temp->next;
    temp->next=temp->next->next;
    free(del);
}
void display(struct node* head)
{
    struct node* t=head;
    while(t!=NULL)
    {
        printf("%d => ",t->data);
        t=t->next;
    }
    printf("NULL \n");
    
}

int main()
{
    struct node* head=NULL;
    insertatend(&head);
    insertatend(&head);
    insertatend(&head);
    display(head);
    deletend(&head);
    display(head);

    return 0;
}

Output-

Enter value to insert at end: 5
Enter value to insert at end: 6
Enter value to insert at end: 9
5 => 6 => 9 => NULL 
5 => 6 => NULL

3. Delete a node after given node- First we will take a pointer variable temp and initialize it with HEAD i.e., now temp points to the first node of the linked list. In while loop we will traverse through the linked list till we reach the value of node after which we want to delete node. Once reached we will store it in a pointer variable del and change the next pointer in such a way that the node is deleted after desired node. Then finally we will free the memory occupied by the node and return to the free pool.

C program to delete a node after a given node from a singly linked list-

#include <stdio.h>
#include <malloc.h>

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

void insertatend(struct node** head)
{
    int n;
    printf("Enter value to insert at end: ");
    scanf("%d",&n);
    struct node* val=(struct node*)malloc(sizeof(struct node));
    val->data=n;
    val->next=NULL;
    if(*head==NULL)
    {
        *head=val;
        return;
    }
    struct node* t=*head;
    while(t->next!=NULL)
    {
        t=t->next;
    }
    t->next=val;
}

void deleteathead(struct node** head)
{
    if(*head==NULL)
    {
        return;
    }
    
    struct node* del=*head;
    *head=(*head)->next;

    free(del);
}
void deletenode(struct node** head)
{
    int n;
    printf("Enter the value of node whose next you want to delete: ");
    scanf("%d",&n);
    if(*head==NULL)
    {
        return;
    }
    if((*head)->next==NULL)
    {
        deleteathead(head);
        return;
    }
    struct node* temp=*head;
    while(temp->data!=n)
    {
        temp=temp->next;
    }
    struct node* del=temp->next;
    temp->next=temp->next->next;
    free(del);
}
void display(struct node* head)
{
    struct node* t=head;
    while(t!=NULL)
    {
        printf("%d => ",t->data);
        t=t->next;
    }
    printf("NULL \n");
    
}

int main()
{
    struct node* head=NULL;
    insertatend(&head);
    insertatend(&head);
    insertatend(&head);
    display(head);
    deletenode(&head);
    display(head);

    return 0;
}

Output-

Enter value to insert at end: 4
Enter value to insert at end: 5
Enter value to insert at end: 6
4 => 5 => 6 => NULL 
Enter the value of node whose next you want to delete: 5
4 => 5 => NULL

4. Delete a given node- First we will take a pointer variable temp and initialize it with HEAD i.e., now temp points to the first node of the linked list. In while loop we will traverse through the linked list till we reach the value of node which we want to delete node. Once reached we will store it in a pointer variable del and change the next pointer in such a way that the node desired node is deleted. Then finally we will free the memory occupied by the node and return to the free pool.

C program to delete a given node from a singly linked list-

#include <stdio.h>
#include <malloc.h>

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

void insertatend(struct node** head)
{
    int n;
    printf("Enter value to insert at end: ");
    scanf("%d",&n);
    struct node* val=(struct node*)malloc(sizeof(struct node));
    val->data=n;
    val->next=NULL;
    if(*head==NULL)
    {
        *head=val;
        return;
    }
    struct node* t=*head;
    while(t->next!=NULL)
    {
        t=t->next;
    }
    t->next=val;
}

void deleteathead(struct node** head)
{
    if(*head==NULL)
    {
        return;
    }
    
    struct node* del=*head;
    *head=(*head)->next;

    free(del);
}
void deletenode(struct node** head)
{
    int n;
    printf("Enter the value of node you want to delete: ");
    scanf("%d",&n);
    if(*head==NULL)
    {
        return;
    }
    if((*head)->next==NULL)
    {
        deleteathead(head);
        return;
    }
    struct node* temp=*head;
    while(temp->next->data!=n)
    {
        temp=temp->next;
    }
    struct node* del=temp->next;
    temp->next=temp->next->next;
    free(del);
}
void display(struct node* head)
{
    struct node* t=head;
    while(t!=NULL)
    {
        printf("%d => ",t->data);
        t=t->next;
    }
    printf("NULL \n");
    
}

int main()
{
    struct node* head=NULL;
    insertatend(&head);
    insertatend(&head);
    insertatend(&head);
    display(head);
    deletenode(&head);
    display(head);

    return 0;
}

Output-

Enter value to insert at end: 4
Enter value to insert at end: 5
Enter value to insert at end: 6
4 => 5 => 6 => NULL 
Enter the value of node you want to delete: 5
4 => 6 => NULL

• Searching for a value in a singly linked list- Searching for a value in a singly linked list means to check whether a given value is present in the DATA part of the node or not. If present we will return true otherwise false.

First we will take a pointer variable temp and initialize it with HEAD i.e., now temp points to the first node of the linked list. In while loop, we will traverse through the linked list till we reach to the node which contains the given value. If we find such node then we will return true otherwise false.

C program to search for a given value in singly linked list -

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

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

void insertatend(struct node** head,int n)
{
    
    struct node* val=(struct node*)malloc(sizeof(struct node));
    val->data=n;
    val->next=NULL;
    if(*head==NULL)
    {
        *head=val;
        return;
    }
    struct node* t=*head;
    while(t->next!=NULL)
    {
        t=t->next;
    }
    t->next=val;
}


bool search(struct node* head)
{
    int n;
    printf("Enter the value you want to search: ");
    scanf("%d",&n);
    
    
    struct node* temp=head;
    while(temp->next!=NULL)
    {
        temp=temp->next;
        if(temp->data==n)
        {
            return 1;
        }
    }
    return 0;
}
void display(struct node* head)
{
    struct node* t=head;
    while(t!=NULL)
    {
        printf("%d => ",t->data);
        t=t->next;
    }
    printf("NULL \n");
    
}

int main()
{
    struct node* head=NULL;
    struct node* ll;
    
    int arr[10]={1,2,3,4,5,6,7,8,9,10};
    
    for(int i=0;i<10;i++)
    {
        insertatend(&head,arr[i]);
    }
    display(head);
    printf("%d",search(head));
    // display(head);

    return 0;
}

Output-

1 => 2 => 3 => 4 => 5 => 6 => 7 => 8 => 9 => 10 => NULL 
Enter the value you want to search: 8
1

1 => 2 => 3 => 4 => 5 => 6 => 7 => 8 => 9 => 10 => NULL 
Enter the value you want to search: 11
0

Types of Linked List - Singly Linked List | codeitwise

Representation of Singly Linked List -

Operations in Singly Linked List -

C program to insert node at the beginning of singly linked list -

C program to insert a node at the end of singly linked list-

C program to insert a node at the beginning and at the end of a singly linked list -

C program to insert a node after a given node in singly linked list-

C program to insert a node before a given node in singly linked list-

Post a Comment

Post a Comment

Top 10 Best Laptops for Programming under 50000 | codeitwise

Build Simple Calculator using HTML CSS and JavaScript | Html Css JavaScript Project

Top 9 Most Demanding Programming Languages of the Decade - codeitwise

ICSE Class 10 Computer Specimen Paper 2023 Solved PDF

Contact Form