All You Need to Know About a Linked List in a Data Structure

A linked list is the most sought-after data structure when it comes to handling dynamic data elements. A linked list consists of a data element known as a node. And each node consists of two fields: one field has data, and in the second field, the node has an address that keeps a reference to the next node.

  • What is a Linked List?
  • Representation of a Linked List
  • Creation of Node and Declaration of Linked Lists
  • Types of Linked Lists
    • Singly Linked List
    • Doubly Linked List
    • Circular Linked List
  • Essential Operation on Linked Lists
    • Traversing
    • Insertion
    • Deletion¬†¬†
    • Searching¬†
  • Application of Linked Lists

What is a Linked List?

  • A linked list is a linear data structure that stores a collection of data elements dynamically.
  • Nodes represent those data elements, and links or pointers connect each node.
  • Each node consists of two fields, the information stored in a linked list and a pointer that stores the address of its next node.
  • The last node contains null in its second field because it will point to no node.
  • A linked list can grow and shrink its size, as per the requirement.
  • It does not waste memory space.

Post Graduate Program in Data Analytics

In partnership with Purdue UniversityView Course
Post Graduate Program in Data Analytics

Representation of a Linked List

This representation of a linked list depicts that each node consists of two fields. The first field consists of data, and the second field consists of pointers that point to another node.

representation-of-linked-list

Here, the start pointer stores the address of the first node, and at the end, there is a null pointer that states the end of the Linked List. 

Creation of Node and Declaration of Linked Lists

struct node

{

 int data;

 struct node * next;

};

struct node * n;

n=(struct node*)malloc(sizeof(struct node*));

It is a declaration of a node that consists of the first variable as data and the next as a pointer, which will keep the address of the next node.

Here you need to use the malloc function to allocate memory for the nodes dynamically.

Types of Linked Lists

The linked list mainly has three types, they are:

  1. Singly Linked List
  2. Doubly Linked List
  3. Circular Linked List

Singly Linked List

A singly linked list is the most common type of linked list. Each node has data and an address field that contains a reference to the next node.

singly-linked-list

Doubly Linked List

There are two pointer storage blocks in the doubly linked list. The first pointer block in each node stores the address of the previous node. Hence, in the doubly linked inventory, there are three fields that are the previous pointers, that contain a reference to the previous node. Then there is the data, and last you have the next pointer, which points to the next node. Thus, you can go in both directions (backward and forward).

doubly-linked-list.

Circular Linked List

The circular linked list is extremely similar to the singly linked list. The only difference is that the last node is connected with the first node, forming a circular loop in the circular linked list.

circular-linked-list

Circular link lists can either be singly or doubly-linked lists.

  • The next node's next pointer will point to the first node to form a singly linked list.
  • The previous pointer of the first node keeps the address of the last node to form a doubly-linked list.

Essential Operation on Linked Lists

  • Traversing: To traverse all nodes one by one.
  • Insertion: To insert new nodes at specific positions.
  • Deletion: To delete nodes from specific positions.
  • Searching: To search for an element from the linked list.

Traversal 

In this operation, you will display all the nodes in the linked list.

When the temp is null, it means you traversed all the nodes, and you reach the end of the linked list and get out from the while loop.

struct node * temp = start;

printf(‚Äú\n list empty are-‚ÄĚ);

while (temp!= NULL)

{

¬†printf(‚Äė%d ‚Äú, temp -> data)

 temp=temp -> next;

}

 Insertion

You can add a node at the beginning, middle, and end.

Insert at the Beginning

  • Create a memory for a new node.
  • Store data in a new node.
  • Change next to the new node to point to start.
  • Change starts to tell the recently created node.

struct node *NewNode;

NewNode=malloc(sizeof(struct node));

NewNode -> data = 40;

NewNode -> next= start;

start= NewNode;

Insert at the End

  • Insert a new node and store data in it.
  • Traverse the last node of a linked list
  • Change the next pointer of the last node to the newly created node.

struct node *NewNode;

NewNode=malloc(sizeof(struct node));

NewNode-> data = 40;

NewNode->next = NULL;

struct node *temp = start;

while( temp->next ! = NULL){

temp=temp -> next;

    }

 temp -> next = NewNode;

Insert at the Middle

  • Allocate memory and store data in the new node.
  • Traverse the node, which is just before the new node.
  • Change the next pointer to add a new node in between.

struct node *NewNode;

NewNode= malloc(sizeof(struct node));

NewNode -> data = 40;

struct node - > temp = start;

for(int i=2; i<position; i++){

if (temp -> next!= NULL)

temp = temp -> next;

}}

NewNode -> next = temp -> next;

temp -> next = NewNode;

Deletion

You can also do deletion in the linked list in three ways either from the end, beginning, or from a specific position.

Delete from the Beginning

  • The point starts at the second node.

start = start -> next;

Delete from the End

  • Traverse the second last element in the linked list.
  • Change its next pointer to null.

struct node * temp = start;

while(temp -> next -> next!= NULL){

temp=temp -> next;

}

temp -> next = NULL;

Delete from the Middle

  • Traverse the element before the element to be deleted.
  • Change the next pointer to exclude the node from the linked list.

for (int i = 2; i, position; i++){

if (temp -> next ! = NULL)

temp = temp -> next;

}

}

temp-> next = temp -> next -> next;

Searching 

The search operation is done to find a particular element in the linked list. If the element is found in any location, then it returns. Else, it will return null.

Operations on Linked-Lists

Code to Insert at the Beginning of the Linked List

void insertatbeg()  

{  

    struct node *NewNode;  

    int item;  

    NewNode = (struct node *) malloc(sizeof(struct node *));  

    if(NewNode == NULL)  

    {  

        printf("\nOVERFLOW");  

    }  

    else  

    {  

        printf("\nEnter value\n");    

        scanf("%d",&item);    

        NewNode->data = item;  

        NewNode->next = start;  

        start = NewNode;  

        printf("\nNode inserted");  

    }    

}  

Code to Insert at the End of the Linked List

void insertatend()  

{  

    struct node *NewNode,*temp;  

    int item;     

    NewNode = (struct node*)malloc(sizeof(struct node));      

    if(NewNode == NULL)  

    {  

        printf("\nOVERFLOW");     

    }  

    else  

    {  

        printf("\nEnter value?\n");  

        scanf("%d",&item);  

        NewNode->data = item;  

        if(start == NULL)  

        {  

            NewNode -> next = NULL;  

            start = NewNode;  

            printf("\nNode inserted");  

        }  

        else  

        {  

            temp = start;  

            while (temp -> next != NULL)  

            {  

                temp = temp -> next;  

            }  

            temp->next = NewNode;  

            NewNode->next = NULL;  

            printf("\nNode inserted");        

        }  

    }  

}  

Code to Insert at the Middle of the Linked List

void insertmiddle()  

{  

    int i,position,item;   

    struct node *NewNode, *temp;  

    NewNode = (struct node *) malloc (sizeof(struct node));  

    if(NewNode == NULL)  

    {  

        printf("\nOVERFLOW");  

    }  

    else  

    {  

        printf("\nEnter element value");  

        scanf("%d",&item);  

        NewNode-> data = item;  

        printf("\n Enter the location after which you want to insert an element ");  

        scanf("\n%d",&position);  

        temp=start;  

        for(i=0;i<position;i++)  

        {  

            temp = temp->next;  

            if(temp == NULL)  

            {  

                printf("\can't insert\n");  

                return;  

            }          

        }  

        NewNode ->next = temp ->next;   

        temp ->next = NewNode;   

        printf("\nNode inserted");  

    }  

}  

Code to Delete From the Beginning of the Linked List

void deleteatbeg()  

{  

    struct node *NewNode;  

    if(start == NULL)  

    {  

        printf("\nList is empty\n");  

    }  

    else   

    {  

        NewNode = start;  

        start = NewNode->next;  

        free(NewNode);  

        printf("\nNode deleted from the beginning\n");  

    }  

}  

Code to Delete From the End of the Linked List

void deleteatend()  

{  

    struct node *NewNode,*NewNode1;  

    if(start == NULL)  

    {  

        printf("\list is empty");  

    }  

    else if(start -> next == NULL)  

    {  

        start = NULL;  

        free(NewNode);  

        printf("\n node of the list deleted\n");  

    }  

           else  

    {  

        NewNode = start;   

        while(NewNode->next != NULL)  

        {  

            NewNode1 = NewNode;  

            NewNode = NewNode ->next;  

        }  

        NewNode1->next = NULL;  

        free(NewNode);  

        printf("\nDeleted Node from the last\n");  

    }     

} 

Code to Delete From the Middle of the Linked List

void deletemiddle()  

{  

    struct node *NewNode,*NewNode1;  

    int position,i;    

    printf("\n what location of the node \n");  

    scanf("%d",&position);  

    NewNode=start;  

    for(i=0;i<position;i++)  

    {  

        NewNode1 = NewNode;       

        NewNode = NewNode->next;              

        if(NewNode == NULL)  

        {  

            printf("\nCan't delete");  

            return;  

        }  

    }  

    NewNode1 ->next = NewNode ->next;  

    free(NewNode);  

    printf("\nDeleted node %d ",position+1);  

}  

FREE Course: Introduction to Data Analytics

Learn Data Analytics Concepts, Tools & SkillsStart Learning
FREE Course: Introduction to Data Analytics

Code to Search for an Element From the Linked List.

void search()  

{  

    struct node *NewNode;  

    int item,i=0,flag;  

    NewNode = start;   

    if(NewNode == NULL)  

    {  

        printf("\nEmpty List\n");  

    }  

    else  

    {   

        printf("\nEnter an item which you want to search\n");   

        scanf("%d",&item);  

        while (NewNode!=NULL)  

        {  

            if(NewNode->data == item)  

            {  

                printf("item found at position%d ",i+1);  

                flag=0;  

            }   

            else  

            {  

                flag=1;  

            }  

            i++;  

            NewNode = NewNode -> next;  

        }  

        if(flag==1)  

        {  

            printf("Item not found\n");  

        }  

    }              

}  

Code to Show Data Elements of the Linked-List

void show()  

{  

    struct node *NewNode;  

    NewNode = start;   

    if(NewNode == NULL)  

    {  

        printf("Nothing to print");  

    }  

    else  

    {  

        printf("\nprinting values\n");   

        while (NewNode!=NULL)  

        {  

            printf("\n%d",NewNode->data);  

            NewNode = NewNode -> next; 

        }  

    }  

} 

Application of a Linked List

  • A linked list is used to implement stacks and queues.
  • A linked list also helps to implement an adjacency matrix graph.
  • It is used for the dynamic memory location.
  • The linked list makes it easy to deal with the addition and multiplication of polynomial operations.
  • Implementing a hash table, each bucket of the hash table itself behaves as a linked list.
  • It is used in a functionality known as undo in Photoshop and Word.

With that, you have reached the end of this tutorial on Linked Lists.

Looking forward to a career in Data Analytics? Check out the Data Analyst Training Program and get certified today.

Next Steps

‚ÄúStack in data structure‚ÄĚ can be next in the line of news topic. It makes sense to learn about stack representation, implementation, and application, where stack plays a vital role.

If you are perhaps looking to build a career in data analytics, do explore Simplilearn’s Post Graduate Program in Data Analytics in partnership with Purdue University & in collaboration with IBM. Featuring ask-me-anything sessions from IBM, a masterclass from Purdue, and many great benefits, this program will give you the work-ready data analytics training you need to succeed today. 

If you have any queries regarding linked lists in data structures, please feel free to comment below. Our experts will be happy to resolve your question as soon as possible.

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.