Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a Linked List?
3.
Representation of Linked Lists
3.1.
Syntax:
4.
Why do we need linked lists?
5.
Operations in the Linked Lists
5.1.
1. Traversal Operation
5.2.
2. Insertion Operation
5.3.
3. Deletion Operation 
5.4.
4. Updation Operation
5.5.
5. Sort Operation
6.
Types of Linked Lists
6.1.
Singly Linked Lists
6.2.
Doubly Linked Lists
6.3.
Circular Linked Lists
7.
Advantages of Linked List
8.
Applications of Linked List
9.
Frequently Asked Questions
9.1.
What are the 4 types of linked list?
9.2.
Which of the following are linked list operations?
9.3.
What are the operations of queue?
9.4.
What are the various operations on stack using linked list?
10.
Conclusion
Last Updated: Apr 3, 2024
Easy

Linked List in Data Structures

Introduction

A linked list is a type of linear data structure that uses nodes to store the data.

linked list operations

Each node in a linked list is a structure-defined data type that consists of data and a pointer referencing the address of the next node.

What is a Linked List?

A linked list is a linear data structure where elements, called nodes, are connected through pointers. Each node contains data and a reference to the next node, forming a sequence. Unlike arrays, linked lists do not require contiguous memory allocation, allowing dynamic memory management and efficient insertion and deletion operations.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Representation of Linked Lists

Representation of Linked Lists

A linked list is a collection of “nodes” connected together via links. These nodes consist of the data to be stored and a pointer to the address of the next node within the linked list. In the case of arrays, the size is limited to the definition, but in linked lists, there is no defined size. Any amount of data can be stored in it and can be deleted from it.

The first node in a linked list is referred to as the head, while the last node frequently links to null to denote the end of the list. Each link contains a data field or fields as well as a link field named next. Every link is connected to the next link using the next link.

Syntax:

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

 

The syntax above represents a single node in a linked list. The next pointer connects the next node, forming a lengthy chain known as a linked list.

Why do we need linked lists?

It offers some amazing features and thus it is of great use, some of the advantages of it include:

  • Dynamic Size: It offers the flexibility to extend the size at runtime and thus we need to worry about the size of data elements beforehand.
  • Ease of Deletion/Insertion: It offers a good and economical way of insertion and deletion of data elements as this insertion and deletion can be costly with the use of arrays.

Operations in the Linked Lists

 There are several operations which were performed on the Linked Lists

  1. Traversal - To traverse throughout the linked list.
     
  2. Insertion - Insertion of a node at any position.
     
  3. Deletion - Deletion of a node from any position.
     
  4. Updation - Updation of data of a node.
     
  5. Sort - Sorting the node members
     

We will cover each one of these operations on linked lists in C/C++ one by one in detail. So, fasten your seat belts.

1. Traversal Operation

Traversal is one of the basic operations on linked lists in C/C++ in which we traverse throughout the linked list from beginning to the end or from head to tail.

Traversal can be used to print the nodes of the linked list, to reach out for a required node in a list.

Let us take the example of printing the nodes of the linked list through traversal operation.
 

Algorithm :

  • First, initialize a Node variable, say ‘temp’ pointing to the head of the linked list.
     
  • Iterate till the ‘temp’ will not become NULL.
     
  • Print the node’s data.
     
  • Increment ‘temp’ to temp’s next.
     
void traversal(Node* head) {
    Node* temp = head;
    while(temp != NULL)
    {
        cout<<(temp->data);
        temp = temp->next;
    }
}      

2. Insertion Operation

Of the operations on linked lists in C/C++, insertion is used to insert a node at a particular position. The positions can be:

  • At the beginning of the linked list.
     
  • At the end of the linked list.
     
  • After after a particular node.
     

Insertion at the Beginning - In this case we need not to traverse the linked list. We will check if the list is empty then we will make the new node as head. Otherwise, we have to connect the head of the list with the new node by making the next pointer of the node pointing to the head and then making the new node as head of the list.

insertion on linked list
insertion on linked list
insertion on linked list

Source : codeforwin

Node* insertAtBegin(Node* head, int x)
{
    // creation of a new node of linked list.
    Node* newNode = new Node(x)
 
    // checking if the linked list is empty.
    if(head == NULL)         
    return newNode;
 
    // insertion of the node at the beginning.
    else     
    {
        newNode->next = head;
        return newNode;
    }
}

 

Insertion at the end - In this case we have to traverse throughout the linked list until we will find the last node and then we will insert the required node in the list.

For this, we have to consider some special cases. For eg. if the list is empty then we will just create the new node and make it as head. In this case the new node will be the first and the last node of the list.

insertion at the end  on linked list

Source: AfterAcademy

Node* insertAtEnd(Node* head, int x)
{
 
    // If the list is empty.
    if( head == NULL )     
    {
        Node* newNode = new Node(x);
        head = newNode;
        return head;
    }
    Node* temp = head;

    // Traversing the list till the last node
    while(temp->next != NULL)
    {
        temp = temp->next;
    }
    Node* newNode = new Node(x);
    temp->next = newNode;
    return head;
}

 

Insertion after a particular node -

In this case a reference to a particular node will be given. Then a new node will be inserted after that.

If the reference of the node is not given instead data of the node is given, then we have to traverse to the given node matching the given data and then we will insert the new node after that node.

insertion after a given node on linked list

Source: AfterAcademy

void insertAfterNode(Node* givenNode, int x)
{
    Node* newNode = new Node(x);
    
    newNode->next = givenNode->next;
    givenNode->next = newNode;
}

3. Deletion Operation 

This is one type of the operations on linked lists in C/C++, in which we just need to follow the following steps:

  • Traversing to the previous node of the node to be deleted.
     
  • Changing the next pointer of that previous node to point to the address of the next node of the node to be deleted.
     
  • Freeing up the memory which is occupied by the node to be deleted.
     
deletion a node in linked list

        Source : AfterAcademy

Node deleteNode(Node* head, Node* toBeDeleted)
{

    // If the node to be deleted is the head node.
    if(head == toBeDeleted) 
    {
        return head.next;
    }

    // temp is the traversing node.
    Node* temp = head;
    
    while( temp->next != NULL )
    {

        // Searching for the previous node of the node to be deleted.
        if(temp->next == toBeDeleted) 
        {
            temp->next = temp->next->next;

            // Freeing up the memory of the node to be deleted.
            return head;
        }
        temp = temp->next;
    }

    // If no node matches in the Linked List.
    return head;
}

4. Updation Operation

This kind is one of the operations on linked lists in C/C++, in which we have to replace the data part of the required node with the given value.

For this, we will be traversing throughout the linked list until we find a node that will be matching to the required node to be updated.

void updateNode(Node* head, int value, int newValue)
{
    // temp is the traversing node
    Node* temp = head;
    while(temp != NULL)
    {
        // If the node matches the given node to be updated.
        if( temp->data == val)
        { 
            // Updating the data part of the node with the new value.
            temp->data = newVal;
            return;
        }
        temp = temp->next;
    }
}

5. Sort Operation

This operation sorts the nodes present in a linked list. You can use various sorting algorithms for linked lists but merge sort is one of the most performant. Let's see the implementation of Merge sort for singly linked lists in C++:-

ListNode* mergeLists(ListNode* Left, ListNode* Right){
    ListNode *head = new ListNode(-1), *curr = head;
    
    while(Left && Right){
        if(Left->val < Right->val){
            curr->next = Left;
            Left = Left->next;
        }else{
            curr->next = Right;
            Right = Right->next;
        }
        curr = curr->next;
    }
    
    curr->next = (Left)?Left:Right;
    
    return head->next;
}

ListNode* sortList(ListNode* head) {
    if(!head || !head->next) return head;

    ListNode *slow = head, *fast = head->next;
    
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    
    auto Right = sortList(slow->next);
    slow->next = NULL;
    auto Left = sortList(head);
    
    return mergeLists(Left, Right);
}

 

The sortList() function accepts the Linked List head pointer and returns the head pointer after sorting it recursively. At each step, the middle node is found, and the left and right halves are sorted independently, and then they are merged using the mergeLists() helper function.

Types of Linked Lists

There are three types of linked lists that have their own unique ways of implementation. They are namely:

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

Singly Linked Lists

Singly Linked List is the collection of nodes which consist of data and the pointer part which will be pointing to the address of the next node.

singly linked list

The structure of the node of Singly Linked List be like:

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

 

The nodes are connected with  the help of the next pointer which is pointing towards the address of the next node. If the next node is not present or the current node is the last node of the Linked List then the next pointer will be pointing to NULL.

singly linked list

Doubly Linked Lists

Doubly Linked List is the collection of nodes which consists of data and two pointers one of which will be pointing to the previous node’s address and another will be pointing to the next node’s address.

Doubly Linked List

The structure of the node of Singly Linked List be like:

Struct Node
{
    int data;
    Node* next;
    Node* prev;
};

 

The nodes are connected with the help of the next pointer which is pointing towards the address of the next node and the prev pointer which is pointing towards the address of the previous node. If the next node is not present or the current node is the last node of the Linked List then the next pointer will be pointing to NULL. And in the other case if the previous node is not present or the current node is the first node of the linked list then the prev pointer will be pointing to NULL.

Doubly Linked Lists

Circular Linked Lists

Circular Linked List is the collection of nodes which consists of data and a pointer which will be pointing to the next node’s address.

The Last node’s next pointer will be pointing to the first node of the Circular Linked List.

Circular Linked Lists

Source: AlphaCodingSkills

Now let us jump to the basic operations performed on a linked list.

Advantages of Linked List

  1. Linked Lists are dynamic in nature, which means they can allocate memory when required.
     
  2. Insertion and deletion in Linked Lists can be on both sides, i.e., either from the head part or from the tail part.
     
  3. Linked Lists reduce access time.

Applications of Linked List

  1. Linked Lists can be used to implement queues, stacks, and graphs.
     
  2. Forward and backward button in the toolbar for navigation uses doubly linked lists.
     

You can also read Difference Between Array List and Linked List here.

Frequently Asked Questions

What are the 4 types of linked list?

The four types of linked lists are Singly Linked List, Doubly Linked List, Circular Linked List, and Doubly Circular Linked List. Each has unique properties and advantages for different applications.

Which of the following are linked list operations?

Linked list operations include insertion, deletion, traversal, searching, and updating nodes. These operations are essential for manipulating the elements within the linked list efficiently.

What are the operations of queue?

Queue operations involve enqueue (adding elements to the rear), dequeue (removing elements from the front), peek (viewing the front element without removing), and isEmpty (checking if the queue is empty).

What are the various operations on stack using linked list?

Stack operations using linked list include push (adding elements to the top), pop (removing elements from the top), peek (viewing the top element without removing), and isEmpty (checking if the stack is empty). These operations follow the Last In, First Out (LIFO) principle.

Conclusion

This article covered the types of linked lists and various operations on linked lists in C/C++. If you want to learn more about linked lists and want to practice some questions which require you to take your basic knowledge on operations on linked lists in C/C++, a notch higher, then you can visit our Guided Path for Linked List.

Recommended Reading:

To study more about Linked Lists, refer to Applications Of Linked Lists.

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Advantages and Disadvantages of Linked List
Next article
Difference between ArrayList and LinkedList
Live masterclass