Linked List In Data Structure, Explanation, Algorithm, Code, Questions

October 15, 2020February 21, 2022 CS Electrical And Electronics

Hello guys, welcome back to my blog. In this article, I will discuss the linked list in data structure using c, what is linked list, how it works, algorithm, code, and I will also share some interview questions.

If you need an article on some other topics then comment us below in the comment box. You can also catch me @ Instagram – Chetan Shidling.

Also, read:

Linked List In Data Structure

A linked list, in simple words, is a linear arrangement of data elements. Those data elements are described nodes. A linked list is a data structure which in turn can be employed to perform other data structures. Therefore, it serves as a building block to perform data structures so as to stacks, queues, and variations. A linked list can be seen as a train or a sequence of nodes in which each node includes one or more data fields and a pointer to the following node.

we can observe a linked list in which each node holds two parts, a data location and a pointer to the next node. The left portion of the node which holds data may include a simple data type, an array, or a structure. The right portion of the node contains a pointer to the next node (or address of the next node in order).

In C, we can create a linked list using the following code:

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

Why linked list in data structure?

Memory and the capacity of an array remain fixed. In the case of linked lists, we can keep adding and removing elements without any capacity constraints.

Drawbacks of linked list in data structure

Extra memory space for pointers is required (for every node one pointer is needed).
Random access not allowed as elements are not stored in contiguous memory locations.

Linked list program for the creation & traversal?

#include<stdio.h>
#include<stdlib.h>
struct Node{
    int data;
    struct Node * next;
};

void linkedlisttraversal(struct Node * ptr){
    while(ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}

int main(){
    struct Node * head;
    struct Node * second;
    struct Node * third;
    struct Node * fourth;

    //Allocate memory for nodes in the linked list in heap
    head = (struct Node *) malloc(sizeof(struct Node));
    second = (struct Node *) malloc(sizeof(struct Node));
    third = (struct Node *) malloc(sizeof(struct Node));
    fourth = (struct Node *) malloc(sizeof(struct Node));

    //Link first and second nodes
    head->data = 6;
    head->next = second;

    //Link second and third nodes
    second->data = 16;
    second->next = third;

    //Link third and fourth nodes
    third->data = 32;
    third->next = fourth;

    //Link fourth node
    fourth->data = 70;
    fourth->next = NULL;

    linkedlisttraversal(head);
    return 0;
}

Output:

Element: 6
Element: 16
Element: 32
Element: 70

Types Of Linked List In Data Structure

01. Singly linked lists

02. Circular linked list

03. Doubly linked list

04. Circular doubly linked list

05. Header linked list

01. Singly-linked lists

A singly linked list is the easiest variety of linked list in which each node includes some data and a pointer to the next node of the corresponding data type. By assuming that the node contains a pointer to the next node, we determine that the node stores the address of the next node in the series. A singly linked list provides traversal of data just in one way.

Traversing a linked list indicates accessing the nodes of the list in sequence to perform any processing on them. Remember a linked list always includes a pointer variable START which collects the address of the first node of the list. The end of the list is indicated by storing NULL or –1 in the NEXT field of the last node. For traversing the linked list, we likewise make usage of another pointer variable PTR which points to the node that is currently living accessed. The algorithm to traverse a linked list is shown below.

Algorithm for traversing a linked list

Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3: Apply Process to PTR DATA
Step 4: SET PTR = PTR NEXT
        [END OF LOOP]
Step 5: EXIT

In this algorithm, we first initialize PTR with the address of START. So now, PTR points to the first node of the linked list. Then in Step 2, a while loop is executed which is repeated until PTR processes the last node, that is until it encounters NULL. In Step 3, we apply the method (e.g., print) to the current node, that is, the node pointed by PTR. In Step 4, we move to the next node by making the PTR variable point to the node whose address is stored in the NEXT field.

Algorithm to print the number of nodes in a linked list

Step 1: [INITIALIZE] SET = 0
Step 2: [INITIALIZE] SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR != NULL
Step 4: SET=+ 1
Step 5: SET PTR = PTR NEXT
        [END OF LOOP]
Step 6: Write COUNT
Step 7: EXIT

Let us now discuss an algorithm to count the number of nodes in a linked list. To do that, we will traverse each and all node of the list and while traversing every individual node, we will increment the counter by 1. Once we reach NULL, that is, when all the nodes of the linked list have been traversed, the final value of the counter will be displayed.

Algorithm to search a linked list

Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Step 3 while PTR != NULL
Step 3: IF VAL = PTR DATA
        SET POS = PTR
        Go To Step 5
        ELSE
        SET PTR = PTR NEXT
        [END OF IF]
        [END OF LOOP]
Step 4: SET POS = NULL
Step 5: EXIT

In Step 1, we initialize the pointer variable PTR with START that holds the address of the first node. In Step 2, a while loop is executed which will relate every node’s DATA with VAL for which the search is being made. If the search is victorious, that is, VAL has been determined, then the address of that node is stored in POS and the control jumps to the last statement of the algorithm. But, if the search is unsuccessful, POS is set to NULL which means that VAL is not present in the linked list.

Inserting a New Node in a Linked List

We will take four cases and later see how insertion is done in each case.

Case 1: The new node is inserted at the beginning.
Case 2: The new node is inserted at the end.
Case 3: The new node is inserted after a given node.
Case 4: The new node is inserted before a given node.

01. Inserting at the beginning

Step 1: IF AVAIL = NULL
        Write OVERFLOW
        Go to Step 7
        [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE NEXT = START
Step 6: SET START = NEW_NODE
Step 7: EXIT

In Step 1, we first examine whether the memory is available for the new node. If the free memory has exhausted, then an OVERFLOW message is displayed. Otherwise, if a free memory cell is ready, then we allocate space for the new node. Set its DATA part with the given VAL and the next part is initialized with the address of the first node of the list, which is stored in START. Presently, since the new node is added as the first node of the list, it will now be known as the START node, that is, the START pointer variable will now hold the address of the NEW_NODE. Note the following two steps:

Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT

These steps allocate memory for the new node. In C, there are functions like malloc(), alloc(), and calloc() which automatically do the memory allocation on behalf of the user.

Linked list program to insert element at the beginning?

#include <stdio.h>
#include <stdlib.h>

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

void linkedlisttraversal(struct Node * ptr){
    while(ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}

struct Node * insertAtFirst(struct Node *head, int data){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    ptr->next = head;
    ptr->data = data;
    return ptr;
};

int main()
{
    struct Node * head;
    struct Node * second;
    struct Node * third;
    struct Node * fourth;

    //Allocate memory for nodes in the linked list in heap
    head = (struct Node *) malloc(sizeof(struct Node));
    second = (struct Node *) malloc(sizeof(struct Node));
    third = (struct Node *) malloc(sizeof(struct Node));
    fourth = (struct Node *) malloc(sizeof(struct Node));

    //Link first and second nodes
    head->data = 6;
    head->next = second;

    //Link second and third nodes
    second->data = 16;
    second->next = third;

    //Link third and fourth nodes
    third->data = 32;
    third->next = fourth;

    //Link fourth node
    fourth->data = 70;
    fourth->next = NULL;

    linkedlisttraversal(head);
    head = insertAtFirst(head, 17);
    linkedlisttraversal(head);
}

Output:

Element: 6
Element: 16
Element: 32
Element: 70
Element: 17
Element: 6
Element: 16
Element: 32
Element: 70

02. Inserting at the end

Step 1: IF AVAIL = NULL
           Write OVERFLOW
           Go to Step 1
        [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> NEXT = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR -> NEXT != NULL
Step 8: SET PTR = PTR - > NEXT
        [END OF LOOP]
Step 9: SET PTR -> NEXT = NEW_NODE
Step 10: EXIT

Shows the algorithm to insert a new node at the end of a linked list. In Step 6, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. In the while loop, we traverse through the linked list to reach the last node. Once we reach the last node, in Step 9, we change the NEXT pointer of the last node to store the address of the new node. Remember that the NEXT field of the new node contains NULL, which signifies the end of the linked list.

Linked list program to insert element at the end?

#include <stdio.h>
#include <stdlib.h>

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

void linkedlisttraversal(struct Node * ptr){
    while(ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}

struct Node * insertAtend(struct Node *head, int data){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    ptr->data = data;
    struct Node * p = head;

    while(p->next!=NULL){
            p = p->next;

    }
    p->next = ptr;
    ptr->next = NULL;
    return head;

};

int main()
{
    struct Node * head;
    struct Node * second;
    struct Node * third;
    struct Node * fourth;

    //Allocate memory for nodes in the linked list in heap
    head = (struct Node *) malloc(sizeof(struct Node));
    second = (struct Node *) malloc(sizeof(struct Node));
    third = (struct Node *) malloc(sizeof(struct Node));
    fourth = (struct Node *) malloc(sizeof(struct Node));

    //Link first and second nodes
    head->data = 6;
    head->next = second;

    //Link second and third nodes
    second->data = 16;
    second->next = third;

    //Link third and fourth nodes
    third->data = 32;
    third->next = fourth;

    //Link fourth node
    fourth->data = 70;
    fourth->next = NULL;

    printf("Linked list before insertion\n");
    linkedlisttraversal(head);
    head = insertAtend(head, 17);
    printf("Linked list after insertion\n");
    linkedlisttraversal(head);

}

Output:

Linked list before insertion
Element: 6
Element: 16
Element: 32
Element: 70
Linked list after insertion
Element: 6
Element: 16
Element: 32
Element: 70
Element: 17

03. New node is inserted after a given node

Step 1: IF AVAIL = NULL
           Write OVERFLOW
           Go to Step 12
        [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PREPTR -> DATA
        != NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR -> NEXT
        [END OF LOOP]
Step 1 : PREPTR -> NEXT = NEW_NODE
Step 11: SET NEW_NODE -> NEXT = PTR
Step 12: EXIT

In Step 5, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. Then we take another pointer variable PREPTR which will be used to store the address of the node preceding PTR. Initially, PREPTR is initialized to PTR. So now, PTR, PREPTR, and START are all pointing to the first node of the linked list. In the while loop, we traverse through the linked list to reach the node that has its value equal to NUM. We need to reach this node because the new node will be inserted after this node. Once we reach this node, in Steps 10 and 11, we change the NEXT pointers in such a way that a new node is inserted after the desired node.

Linked list program to insertion an element after node?

#include <stdio.h>
#include <stdlib.h>

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

void linkedlisttraversal(struct Node * ptr){
    while(ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}

struct Node * insertafterNode(struct Node *head, struct Node *preNode, int data){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    ptr->data = data;
    struct Node * p = head;

    ptr->next = preNode->next;
    preNode->next = ptr;

    return head;

};


int main()
{
    struct Node * head;
    struct Node * second;
    struct Node * third;
    struct Node * fourth;

    //Allocate memory for nodes in the linked list in heap
    head = (struct Node *) malloc(sizeof(struct Node));
    second = (struct Node *) malloc(sizeof(struct Node));
    third = (struct Node *) malloc(sizeof(struct Node));
    fourth = (struct Node *) malloc(sizeof(struct Node));

    //Link first and second nodes
    head->data = 6;
    head->next = second;

    //Link second and third nodes
    second->data = 16;
    second->next = third;

    //Link third and fourth nodes
    third->data = 32;
    third->next = fourth;

    //Link fourth node
    fourth->data = 70;
    fourth->next = NULL;

    printf("Linked list before insertion\n");
    linkedlisttraversal(head);

    head = insertafterNode(head, third, 67);
    printf("Linked list after insertion\n");
    linkedlisttraversal(head);

}

Output:

Linked list before insertion
Element: 6
Element: 16
Element: 32
Element: 70
Linked list after insertion
Element: 6
Element: 16
Element: 32
Element: 67
Element: 70

04. New node is inserted before a given node

Step 1: IF AVAIL = NULL
        Write OVERFLOW
        Go to Step 12
        [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PTR -> DATA != NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR -> NEXT
        [END OF LOOP]
Step 1 : PREPTR -> NEXT = NEW_NODE
Step 11: SET NEW_NODE -> NEXT = PTR
Step 12: EXIT

In Step 5, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. Then, we take another pointer variable PREPTR and initialize it with PTR. So now, PTR, PREPTR, and START are all pointing to the first node of the linked list. In the while loop, we traverse through the linked list to reach the node that has its value equal to NUM. We need to reach this node because the new node will be inserted before this node. Once we reach this node, in Steps 10 and 11, we change the NEXT pointers in such a way that the new node is inserted before the desired node.

Deleting a Node in a Linked List

Deleting the elements from the linked list can be done in three ways:

01. By deleting first node

02. By deleting last node

03. By deleting given node

01. Deleting the First Node from a Linked List

Step 1: IF START = NULL
        Write UNDERFLOW
        Go to Step 5
        [END OF IF]
Step 2: SET PTR = START
Step 3: SET START = START NEXT
Step 4: FREE PTR
Step 5: EXIT

In Step 1, we check if the linked list exists or not. If START = NULL, then it signifies that there are no nodes in the list and the control is transferred to the last statement of the algorithm. However, if there are nodes in the linked list, then we use a pointer variable PTR that is set to point to the first node of the list. For this, we initialize PTR with START that stores the address of the first node of the list. In Step 3, START is made to point to the next node in sequence and finally, the memory occupied by the node pointed by PTR (initially the first node of the list) is freed and returned to the free pool.

Program for deleting the first node in the linked list?

#include<stdio.h>
#include<stdlib.h>
struct Node{
    int data;
    struct Node * next;
};

void linkedlisttraversal(struct Node * ptr){
    while(ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}

//Deleting the First Element from the linked list

struct Node * deleteFirst(struct Node * head){
    struct Node * ptr = head;
    head = head->next;
    free(ptr);
    return head;
};

int main(){
    struct Node * head;
    struct Node * second;
    struct Node * third;
    struct Node * fourth;

    //Allocate memory for nodes in the linked list in heap
    head = (struct Node *) malloc(sizeof(struct Node));
    second = (struct Node *) malloc(sizeof(struct Node));
    third = (struct Node *) malloc(sizeof(struct Node));
    fourth = (struct Node *) malloc(sizeof(struct Node));

    //Link first and second nodes
    head->data = 6;
    head->next = second;

    //Link second and third nodes
    second->data = 16;
    second->next = third;

    //Link third and fourth nodes
    third->data = 32;
    third->next = fourth;

    //Link fourth node
    fourth->data = 70;
    fourth->next = NULL;

    printf("Linked list before deletion\n");
    linkedlisttraversal(head);

    head = deleteFirst(head);

    printf("Linked list after deletion\n");
    linkedlisttraversal(head);
    return 0;
}

Output:

Linked list before deletion
Element: 6
Element: 16
Element: 32
Element: 70
Linked list after deletion
Element: 16
Element: 32
Element: 70

02. Deleting the Last Node from a Linked List

Step 1: IF START = NULL
        Write UNDERFLOW
        Go to Step 8
        [END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR NEXT != NULL
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR NEXT
        [END OF LOOP]
Step 6: SET PREPTR NEXT = NULL
Step 7: FREE PTR
Step 8: EXI

In Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. In the while loop, we take another pointer variable PREPTR such that it always points to one node before the PTR. Once we reach the last node and the second last node, we set the NEXT pointer of the second last node to NULL, so that it now becomes the (new) last node of the linked list. The memory of the previous last node is freed and returned back to the free pool.

Program to delete the last node in a linked list?

#include<stdio.h>
#include<stdlib.h>
struct Node{
    int data;
    struct Node * next;
};

void linkedlisttraversal(struct Node * ptr){
    while(ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}

//Deleting the  Element at end
struct Node * deleteAtEnd(struct Node * head){
    struct Node * p = head;
    struct Node * q = head->next;
    while(q->next != NULL)
    {
        p = p->next;
        q = q->next;
    }
    p->next = q->next;
    free(q);
    return head;
};

int main(){
    struct Node * head;
    struct Node * second;
    struct Node * third;
    struct Node * fourth;

    //Allocate memory for nodes in the linked list in heap
    head = (struct Node *) malloc(sizeof(struct Node));
    second = (struct Node *) malloc(sizeof(struct Node));
    third = (struct Node *) malloc(sizeof(struct Node));
    fourth = (struct Node *) malloc(sizeof(struct Node));

    //Link first and second nodes
    head->data = 6;
    head->next = second;

    //Link second and third nodes
    second->data = 16;
    second->next = third;

    //Link third and fourth nodes
    third->data = 32;
    third->next = fourth;

    //Link fourth node
    fourth->data = 70;
    fourth->next = NULL;

    printf("Linked list before deletion\n");
    linkedlisttraversal(head);

    head = deleteAtEnd(head);
    printf("Linked list after deletion\n");
    linkedlisttraversal(head);
    return 0;
}

Output:

Linked list before deletion
Element: 6
Element: 16
Element: 32
Element: 70
Linked list after deletion
Element: 6
Element: 16
Element: 32

03. Deleting the Node After a Given Node in a Linked List

Step 1: IF START = NULL
        Write UNDERFLOW
        Go to Step 1
        [END OF IF]
Step 2: SET PTR = START
Step 3: SET PREPTR = PTR
Step 4: Repeat Steps 5 and 6 while PREPTR DATA != NUM
Step 5: SET PREPTR = PTR
Step 6: SET PTR = PTR NEXT
        [END OF LOOP]
Step 7: SET TEMP = PTR
Step 8: SET PREPTR NEXT = PTR NEXT
Step 9: FREE TEMP
Step 10 : EXIT

In Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. In the while loop, we take another pointer variable PREPTR such that it always points to one node before the PTR. Once we reach the node containing VAL and the node succeeding it, we set the next pointer of the node containing VAL to the address contained in the next field of the node succeeding it. The memory of the node succeeding the given node is freed and returned back to the free pool.

Program to delete element at given node in linked list?

#include<stdio.h>
#include<stdlib.h>
struct Node{
    int data;
    struct Node * next;
};

void linkedlisttraversal(struct Node * ptr){
    while(ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}

//Deleting the  Element at given value
struct Node * deleteAtValue(struct Node * head, int value){
    struct Node * p = head;
    struct Node * q = head->next;
    while(q->data != value && q->next != NULL)
    {
        p = p->next;
        q = q->next;
    }
    if(q->data == value){
         p->next = q->next;
         free(q);
    }
    return head;
};

int main(){
    struct Node * head;
    struct Node * second;
    struct Node * third;
    struct Node * fourth;

    //Allocate memory for nodes in the linked list in heap
    head = (struct Node *) malloc(sizeof(struct Node));
    second = (struct Node *) malloc(sizeof(struct Node));
    third = (struct Node *) malloc(sizeof(struct Node));
    fourth = (struct Node *) malloc(sizeof(struct Node));

    //Link first and second nodes
    head->data = 6;
    head->next = second;

    //Link second and third nodes
    second->data = 16;
    second->next = third;

    //Link third and fourth nodes
    third->data = 32;
    third->next = fourth;

    //Link fourth node
    fourth->data = 70;
    fourth->next = NULL;

    printf("Linked list before deletion\n");
    linkedlisttraversal(head);

    head = deleteAtValue(head, 32);
    printf("Linked list after deletion\n");
    linkedlisttraversal(head);
    return 0;
}

Output:

Linked list before deletion
Element: 6
Element: 16
Element: 32
Element: 70
Linked list after deletion
Element: 6
Element: 16
Element: 70

02. Circular linked list

In a circular linked list, that last node holds a pointer to the first node of the list. While traversing a circular linked list, we can start at any node and traverse the list in either direction, forward or backward, till we reach the same node where we began. Therefore, a circular linked list has no beginning and no end.

03. Doubly linked list

A doubly linked list or a two-way linked list is a higher complex variety of linked list which includes a pointer to the next as well as the earlier node in the series. Hence, it consists of three parts—data, a pointer to the next node, and a pointer to the past node.

04. Circular doubly linked list

A circular doubly linked list or a circular two-way linked list is a more complex type of linked list which contains a pointer to the next as well as the previous node in the order. The difference within a doubly linked and a circular doubly linked list is identical as that exists between a singly linked list and a circular linked list.

05. Header linked list

A header linked list is a specific type of linked list which includes a header node at the start of the list. Hence, in a header linked list, START will not point to the first node of the list but START will include the address of the header node. The following are the two kinds of a header linked list:

Grounded header linked list which saves NULL in the next field of the last node and circular header linked list which saves the address of the header node in the next field of the last node.

I will update some more information of types of linked list later. I hope this article may help you all a lot. Thank you for reading. If you have any doubts related to this article “Linked List In Data Structure”, then comment below.

Also, read: