Hello welcome readers!

In this blog, we will discuss LinkedList and its 3 types and then we will also discuss some basic operations that we can do in a linked list. So let's get started. 🥸

So first thing first what is a Linked list? 🥸

A linked list is a sequential data structure, which is connected together via links. A linked list is a sequence of links that contain items. Each link contains a connection to another link.

Why Linked List? 👀

Arrays can be used to store linear data of similar types, but arrays have the following limitations.

• The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
• Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create a room existing elements have to be shifted.

Drawbacks:

• Random access is not allowed. We have to access elements sequentially starting from the first node.
• Extra memory space for a pointer is required with each element of the list.
• It is not cache-friendly. Since array elements are contiguous locations, there is a locality of reference which is not there in the case of linked lists.

It consists of:

A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head is NULL.

Each node in a list consists of at least two parts:

• Data
• Pointer (Or Reference) to the next node

A linked list can be visualized as a chain of nodes, where every node points to the next node. See below:

Types of Linked List 🧐

• Simple Linked List− Item navigation is forward only.

• Doubly Linked List− Items can be navigated forward and backward.

• Circular Linked List− The last item (or node) contains a link of the first element (or node) as next and the first element has a link to the last element as previous.

---

Basic Operations on Simple Linked List ⚡️ ☄️

Following are the basic operations supported by a list.

• Insertion− Adds an element at the beginning of the list.

• Deletion− Deletes an element at the beginning of the list.

• Display− Displays the complete list.

• Search− Searches an element using the given key.

• Delete− Deletes an element using the given key.

Creating Node constructor to allocate value on every declaration of a Node.

class Node
{
public:
    int data;
    Node* next;
    Node(int val)
    {
        data = val;
        next = NULL;
    }
};

1. insert Node at Trail: 🤘

void insert_at_trail(Node* &head, int val)      // head starting of list to which
// we have to add
// value that we want to add
{
    Node* n = new Node(val);
    // Make new node "n" through constructor
    if (head == NULL)
    {
        head = n;
        return;
    }
    Node* temp = head;

    while (temp -> next != NULL)
    {
        temp = temp -> next;
    }
    temp -> next = n;
}

2. Insert node as a Header node: 🤙

void insert_at_first(Node* &head, int val)
{
    Node* n = new Node(val);
    n->next = head;
    head = n;
}

3. Check if the given element is present or not: 👈

bool search_in_linkedlist(Node* head, int element_to_search)
{
    Node* temp = head;
    while (temp != NULL)
    {
        if (temp->data == element_to_search) return true;

        temp = temp -> next;
    }
    return false;
}

4. Traverse and display: 👉

void display_linked_list(Node* head)
{
    Node* temp = head;
    while (temp != NULL)
    {
        cout << temp->data << " --> ";
        temp = temp -> next;
    }
    cout << "null" << endl;
}

So finally here is the Program that can perform these operations on Normal LinkedList:

🤓

#include <bits/stdc++.h>
using namespace std;

class Node
{
public:
    int data;
    Node* next;
    Node(int val)
    {
        data = val;
        next = NULL;
    }
};

void insert_at_trail(Node* &head, int val)      // head starting of list to which
// we have to add
// value that we want to add
{
    Node* n = new Node(val);
    // Make new node "n" through constructor
    if (head == NULL)
    {
        head = n;
        return;
    }
    Node* temp = head;

    while (temp -> next != NULL)
    {
        temp = temp -> next;
    }
    temp -> next = n;
}

void insert_at_first(Node* &head, int val)
{
    Node* n = new Node(val);
    n->next = head;
    head = n;
}

bool search_in_linkedlist(Node* head, int element_to_search)
{
    Node* temp = head;
    while (temp != NULL)
    {
        if (temp->data == element_to_search) return true;

        temp = temp -> next;
    }
    return false;
}

void display_linked_list(Node* head)
{
    Node* temp = head;
    while (temp != NULL)
    {
        cout << temp->data << " --> ";
        temp = temp -> next;
    }
    cout << "null" << endl;
}


int main()
{
    Node* head = NULL;

    insert_at_trail(head, 0);
    insert_at_trail(head, 1);
    insert_at_trail(head, 2);
    insert_at_trail(head, 3);
    display_linked_list(head);

    cout << search_in_linkedlist(head, 2) << endl;
    cout << search_in_linkedlist(head, 7) << endl;
}

Remember these operations are only for normal LinkedList. So in the next blog, we will discuss these operations on a circular as well as on a double-headed linked list.

So till then, goodbye and have a great day ahead.

😄🙌