Linked List Data Structure

by

Linked List

A collection of objects called nodes is defined as a Linked List. These nodes are randomly stored in memory. There are two fields present in a node. The first field is the data stored at that particular address and the second field is the pointer containing the address of the next node in the memory. A pointer to the null is included in the last node of the list.

Uses of a Linked List:

The list doesn’t need to be present continuously in the memory. The node can be linked together to make a list, wherever they reside in the memory, thus providing an optimized utilization of space. The size of the list also doesn’t need to be declared in advance. It is limited to the memory size. In a linked list, an empty node is not allowed. In the singly linked list, the values of primitive types or objects can be stored.

Why use a linked list over an array?

An array, as a data structure, is used to organize the group of elements that are to be stored individually in the memory, but still has several advantages and disadvantages.

Limitations of an array:

  • Before using an array in a program, its size must be mentioned in advance.
  • Expanding the size of the array is almost impossible at run time. Also, increasing the size of an array is a time taking process.
  • In an array, all the elements are continuously stored in the memory, which means that inserting an element in the array needs shifting of all its predecessors.

To overcome the limitations of an array, we can use a linked list.

Advantages of a linked list:

  • The memory is allocated dynamically by a linked list.
  • In a linked list, the nodes of the linked list are non-contiguously stored in the memory.
  • In a linked list, the nodes are linked together with the help of pointers.
  • It is not required to define the size of a linked list at the time of declaration. Sizing is thus, not a problem.
  • Depending on the demand of the program, the list grows but is limited to the available memory space.

Singly-linked list or One-way chain:

A collection of an ordered set of elements is defined as a singly linked list. According to the demand of the program, the number of elements in a singly linked list may vary. Its node consists of two parts. The first part is the data part which is used to store the actual information to be represented by the node. The second part is the linked part which is used to store the address of its immediate successor. One of the important features of the singly linked list is that it can be traversed only in one direction. It is also known as a one-way chain, i.e, each node contains only the next pointer and we can not traverse the list in the reverse direction.

Complexity:

Data Structure Time Complexity Space Complexity
Average Worst Worst
Access Search Insertion Deletion Access Search Insertion Deletion
Singly Linked List θ(n) θ(n) θ(1) θ(1) O(n) O(n) O(1) O(1) O(n)

Operations on Singly Linked List:

We can perform various operations on a singly linked list.

Node Creation:

struct node   
{  
    int data;   
    struct node *next;  
};  
struct node *head, *ptr;   
ptr = (struct node *)malloc(sizeof(struct node *));

Insertion:

In a singly linked list, the operation of insertion can be performed at different positions. The insertion is categorized into various categories, based on the position of the new node being inserted. These are:

S.No. Operation Description
1 Insertion at beginning
  • Involves the insertion of any element at the front of the list.
  • Need to make a few link adjustments to make the new node as the head of the list.
2 Insertion at the end of the list
  • Involves the insertion at the end of the linked list.
  • The new node can be inserted as the last one or it can be inserted as the only node in the list.
  • In each scenario, different logic is implemented.
3 Insertion after the specified node
  • Involves the insertion after the specified node of the linked list.
  • To reach the node after which the new node should be inserted, the desired number of nodes needs to be skipped.

Deletion and Traversing:

In a singly linked list, the operation of deletion can be performed at different positions. The deletion is categorized into various categories, based on the position of the node being deleted. These are:

S.No. Operation Description
1 Deletion at beginning
  • Involves the deletion of a node from the beginning of the list.
  • Simplest operation among all.
  • Needs a few adjustments in the node pointers.
2 Deletion at the end of the list
  • Involves the deletion of the last node of the list.
  • Either the list can be empty or it can be full.
  • For the different scenarios, different logics are implemented.
3 Deletion after the specified node
  • Involves the deletion of the node after the specified node in the list.
  • To reach the node after which the node should be deleted, the desired number of nodes needs to be skipped.
  • Traversing through the list is required.
4 Traversing
  • To perform some specific operation on the nodes of a list, we simply visit each node of the list at least once.
  • This is called traversing.
5 Searching
  • To search for an element, we match each element of the list with the given element.
  • This is called searching.
  • The location of that element is returned, if the element is found on any of the locations.
  • The null is returned otherwise.

Linked List in C: Menu-Driven Program:

#include  
#include  
struct node   
{  
    int data;  
    struct node *next;   
};  
struct node *head;  
 
void beginsert ();   
void lastinsert ();  
void randominsert();  
void begin_delete();  
void last_delete();  
void random_delete();  
void display();  
void search();  
void main ()  
{  
    int choice =0;  
    while(choice != 9)   
    {  
        printf("\n\n*********Available Operations*********\n");  
        printf("\nSelect one operation from the below list::\n");  
        printf("\n===============================================\n");  
        printf("\n1.Insert in beginning\n2.Insert at last\n3.Insert at any random location\n4.Delete from Beginning\n5.Delete from last\n6.Delete node after specified location\n7.Search for an element\n8.Show\n9.Exit\n");  
        printf("\nEnter your choice:\n");         
        scanf("\n%d",&choice);  
        switch(choice)  
        {  
            case 1:  
            beginsert();      
            break;  
            case 2:  
            lastinsert();         
            break;  
            case 3:  
            randominsert();       
            break;  
            case 4:  
            begin_delete();       
            break;  
            case 5:  
            last_delete();        
            break;  
            case 6:  
            random_delete();          
            break;  
            case 7:  
            search();         
            break;  
            case 8:  
            display();        
            break;  
            case 9:  
            exit(0);  
            break;  
            default:  
            printf("A valid choice is required....");  
        }  
    }  
}  
void beginsert()  
{  
    struct node *ptr;  
    int item;  
    ptr = (struct node *) malloc(sizeof(struct node *));  
    if(ptr == NULL)  
    {  
        printf("\nOVERFLOW");  
    }  
    else  
    {  
        printf("\nEnter value:\n");    
        scanf("%d",&item);    
        ptr->data = item;  
        ptr->next = head;  
        head = ptr;  
        printf("\nNode successfully inserted!!");  
    }  
 
}  
void lastinsert()  
{  
    struct node *ptr,*temp;  
    int item;     
    ptr = (struct node*)malloc(sizeof(struct node));      
    if(ptr == NULL)  
    {  
        printf("\nOVERFLOW");     
    }  
    else  
    {  
        printf("\nEnter value:\n");  
        scanf("%d",&item);  
        ptr->data = item;  
        if(head == NULL)  
        {  
            ptr -> next = NULL;  
            head = ptr;  
            printf("\nNode successfully inserted!!");  
        }  
        else  
        {  
            temp = head;  
            while (temp -> next != NULL)  
            {  
                temp = temp -> next;  
            }  
            temp->next = ptr;  
            ptr->next = NULL;  
            printf("\nNode successfully inserted!!");  
 
        }  
    }  
}  
void randominsert()  
{  
    int i,loc,item;   
    struct node *ptr, *temp;  
    ptr = (struct node *) malloc (sizeof(struct node));  
    if(ptr == NULL)  
    {  
        printf("\nOVERFLOW");  
    }  
    else  
    {  
        printf("\nEnter value:\n");  
        scanf("%d",&item);  
        ptr->data = item;  
        printf("\nEnter the location after which you want to insert:\n");  
        scanf("\n%d",&loc);  
        temp=head;  
        for(i=0;i<loc;i++) { temp = temp->next;  
            if(temp == NULL)  
            {  
                printf("\nInsertion not possible!!\n");  
                return;  
            }  
 
        }  
        ptr ->next = temp ->next;   
        temp ->next = ptr;   
        printf("\nNode successfully inserted!!");  
    }  
}  
void begin_delete()  
{  
    struct node *ptr;  
    if(head == NULL)  
    {  
        printf("\nList is empty\n");  
    }  
    else   
    {  
        ptr = head;  
        head = ptr->next;  
        free(ptr);  
        printf("\nNode successfully deleted!!\n");  
    }  
}  
void last_delete()  
{  
    struct node *ptr,*ptr1;  
    if(head == NULL)  
    {  
        printf("\nlist is empty");  
    }  
    else if(head -> next == NULL)  
    {  
        head = NULL;  
        free(head);  
        printf("\nOnly node of the list deleted successfully!!\n");  
    }  
 
    else  
    {  
        ptr = head;   
        while(ptr->next != NULL)  
        {  
            ptr1 = ptr;  
            ptr = ptr ->next;  
        }  
        ptr1->next = NULL;  
        free(ptr);  
        printf("\nNode successfully deleted!!\n");  
    }     
}  
void random_delete()  
{  
    struct node *ptr,*ptr1;  
    int loc,i;    
    printf("\nEnter the location of the node after which you want to perform deletion: \n");  
    scanf("%d",&loc);  
    ptr=head;  
    for(i=0;i<loc;i++) { ptr1 = ptr; ptr = ptr->next;  
 
        if(ptr == NULL)  
        {  
            printf("\nDeletion not possible!!\n");  
            return;  
        }  
    }  
    ptr1 ->next = ptr ->next;  
    free(ptr);  
    printf("\nDeleted node %d ",loc+1);  
}  
void search()  
{  
    struct node *ptr;  
    int item,i=0,flag;  
    ptr = head;   
    if(ptr == NULL)  
    {  
        printf("\nEmpty List\n");  
    }  
    else  
    {   
        printf("\nEnter item to search:\n");   
        scanf("%d",&item);  
        while (ptr!=NULL)  
        {  
            if(ptr->data == item)  
            {  
                printf("Item found at location %d ",i+1);  
                flag=0;  
            }   
            else  
            {  
                flag=1;
            }  
            i++;  
            ptr = ptr -> next;  
        }  
        if(flag==1)  
        {  
            printf("Item not found\n");  
        }  
    }     
 
}  
 
void display()  
{  
    struct node *ptr;  
    ptr = head;   
    if(ptr == NULL)  
    {  
        printf("Nothing to print");  
    }  
    else  
    {  
        printf("\nPrinting list . . . . .\n");   
        while (ptr!=NULL)  
        {  
            printf("\n%d",ptr->data);  
            ptr = ptr -> next;  
        }  
    }  
}

Output

*********Available Operations*********

Select one operation from the below list::

===============================================

1.Insert at beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice:
1

Enter value:
2

Node successfully inserted!!

*********Available Operations*********

Select one operation from the below list::

===============================================

1.Insert at beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit

Enter your choice:
7

Enter item to search:
2
Item found at location 1