Linked List

There are various datatypes in c/c++ and a Linked list is one of them. A linked list is a non-primitive datatype. Just like an array, it can also store homogeneous data in it.

What is the difference between an array and a Linked List?

The main difference between an array and a Linked List is that an array stores the elements in a contagious block of memory while the linked list does not store them in a contagious memory location.

Another difference between them is that the array has a fixed size while the linked list has a dynamic size. In the array, the memory is allocated at compile time while in the linked list the memory is allocated at run time.

Insertion and deletion in the linked list are easy as compared to the array as in the array we need to shift the element.

Types of Linked Lists

The linked list is of three types-:

1.) Singly linked list

2.) Doubly linked list

3.) Circular linked list

4.)Doubly circular linked list

Implementation of linked list

#include <iostream>
using namespace std;

//tie---------------------------------------------------------------->
//creating the node of the linked list
class node{
    //defining the data member of this node
    //this will containg two things one is
    //data and the adress of the next node
    public:
        int data;
        node* next;
    //creating the constructor
    node(int data){
        this->data = data;
        //this key word is used as pointer to the 
        //data in the data memebers
        this->next = NULL;
    }
    //destructor
    ~node(){
        int value = this->data;
        while(this->next!=NULL){
            this->next = NULL;
            delete next;
        }
        cout<<"delete the node"<<value<<endl;
    }
};
//printing the linked list
void print(node* &head){
    node *temp = head;
    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
    cout<<endl;
}

int main(){
    node* node1 = new node(10);
    node* head = node1;
    print(head);
    return 0;
}
//take it easy------------------------------------------------------->

A linked list has two fields combined it is known as a node which contains data and a node pointer that points to the next node or in simple words it stores the address of the next node.It also contains a head pointer which points to the first node only.

Insert a node in front of the list

To insert an element in front of the list we can create a function in which we can pass head reference and data to pass as an argument.

//insert at head---->
void insertAtHead(node* &head,int data){
    node *temp = new node(data);
    temp->next = head;
    head = temp;
}

Insert node at any position

To insert a node at any position we need head, position and data to pass as an argument to the function.

In implementing it we need to look for two cases-:

1.)When the position is 1

2.) When the position is anywhere accept 1

//Insert at middle or position--->
void insertAtMiddle(node* &tail,node* &head,int data,int pos){
    node *temp = head;
    //if position is 1 then
    if(pos == 1){
        insertAtHead(head,data);
        return;
    }
    int cnt = 1;
    while(cnt<pos-1){
        temp = temp->next;
        cnt++;
    }
    //if position is last
    if(temp->next ==NULL){
        insertAtEnd(tail,data);
        return;
    }
    //creatint a new node
    node* inMiddle = new node(data);
    inMiddle->next = temp->next;
    temp->next = inMiddle;
}

So this is it for now Thank you for your time 😊.