Linked list on C++

Last Updated on March 28, 2022 by Ria Pathak

Linked List is a linear data structure which comprises of elements/nodes stored at various locations not necessarily contiguous. But don’t we have arrays for keeping a list? Well, there are quite a bit of advantages of linked list. In linked list it’s much easier to insert a value or delete a value which will require more time in arrays.
It consists of nodes which can have multiple variables but alone with it has a next pointer which points to the next node in the linked list. The last node points to a NULL pointer which denotes the end of the linked List.

Structure

Let’s define it structurally –

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

Well, CPP does provide linked list implementation in STL but we will be covering the basics of designing a linked list by ourselves. Let’s dive in.

Linked List supports generally three operations Insert, size, delete at position. To begin with p=p→next is a the most important statement to understand. It says if p be a node in the linked list then if we want to go to the next node, we just need to assign p to it’s next. The whole linked list traversal is based on this.

• Insertion: Whenever we need to insert a node in linked list, we can either choose to insert it in the beginning or at any position given by k.
  So, when we insert at the beginning, we just need to assign the temporary variable’s next to our current head and then change our head to a new temporary node.
  When we have a particular position, we will do the same thing only first we will traverse to k-1thnode in the linked list and insert the new temporary node in the list.

Code Implementation –

void insertLinkedList(Node *Head,int data,int position){
    if(Head == NULL){
        Node *temp;
        temp->data = data;
        temp->next = NULL;
        *Head = temp;
    }
    else{
        int k = position -1;
        Node *temp;
        temp->data = data;
        temp->next = NULL;
        Node *pt = *Head;
        while(k-- && pt!=NULL){
            pt = pt->next;
        }
        temp->next = pt->next;
        pt->next = temp;
        free(temp);
        free(pt);
    }
}

• Deletion: Deletion refers to deleting a node from the beginning or a given position. It works on the same algorithm as insertion. Only change that we have to make is If p points to the node to be deleted, we will traverse to the node before it and just change the next pointer to the next pointer of the ‘to be deleted’ node.

Code Implementation –

void deletenode(Node *Head,int position){
        int k = position -1;
        Node *temp = NULL;//following ptr
        Node *pt = *Head;
        while(k-- && pt!=NULL){
            temp = pt;
            pt = pt->next;
        }
        temp->next = pt->next;
        free(temp);
        free(pt);
}

• Size: This function will traverse the linked list and just return the size of the linked list.

Code Implementation –

int sizelinkedlist(Node *Head){
    int count = 0;
        Node *pt = *Head;
        while(pt){
            count++;
            pt = pt->next;   
        }
    return count;
}

STL Linked List in CPP

CPP provide built int function for Lists which are sane sequence containers that allow non-contiguous memory allocation. STL provides list with very strong method background and makes easier to implement linked list in CPP.
list llist;[declaration of list in STL]
It has various methods like –

• Front(): returns the value of the first element.
• Back(): returns the value of the last element.
• Push_back(): inserts the new element to the end of the list.
• Size(): returns the size of the linked list.
• Reverse(): return the pointer to the reversed list.( Actually reverses the linked list also), etc.

Applications
Linked list has various applications like –

• Creating stacks and queues.
• Implementation in graphs
• Performing arithmetic operations on long integers
• Image Viewer
• Music Player

This article was a brief introduction to Linked list in CPP. Although all other problems can be solved using these basic algorithms related to Linked list.

This article tried to discuss Linked List implementation on c++. Hope this blog helps you understand and implement the concept. To practice more and build your foundation you can check out Prepbytes Courses.