Operations on Linked Lists in C/C++

Introduction

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

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.

Advantages – 

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 –

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

Types of Linked Lists

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

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

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

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

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.

Doubly Linked Lists – Doubly Linked List is the collection of nodes that 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.

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

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.

Circular Linked Lists – Circular Linked List is the collection of nodes that consists of data and a pointer that 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.

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

Operations on Linked Lists in C/C++

 There are several operations that 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.

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 –

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 –  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 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.

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 a head. In this case, the new node will be the first and the last node of the list.

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.

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

3. Deletion – This is one type of the operation 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.

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 – 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;
    }
}

Frequently Asked Questions

Key Takeaways

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.

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

By: Deepanshu Dhingra