Header Ads Widget

Trending

6/recent/ticker-posts

Linked List Data Structure

 Linked List is a Linear data structure in which each node is connected with other one and each Node contains data and address of it's next node. Link list data structure is the collection of Node joined together with pointers. Link list is most commonly used data structure because of its fastest searching, insertion and deletion operations. Linked List does not allow random access of data.

Types of Linked List

There are commonly three types of linked list.
  1. Singly Linked List
  2. Double Linked List
  3. Circular Linked List

Uses of Linked List

  1. Linked List are used to represent polynomials and various operations on it.
  2. We can Represent Sparse matrix using Linked List.
  3. It is used in dynamic memory allocation.
  4. Linked list is used to implement stack and queues
  5. Various Applications uses Linked List to Undo and Redo any function.

Difference between Linked List and Array is that Array uses contiguous memory location while linked list doesn't.




Linked List Data structure


Implementation of Linked List

For Implementation of Linked list we follow following Procedures.
  1. We declare a Head node and initialize it will point to null value.
  2. Each Node will store data and address of it's next element.
  3. Null value of node indicate the end of linked list.

Let us see Implementation of Linked List in C++ and Java

Also Read - [ Trie Data Structure ]

Implementation of Linked List in C++

class linkedlist{
    public:
        class node{
        public:
        int data;
        node* next;
     node(int val)
    {
        data=val;
        next=NULL;

    }
    };
    
node* head=NULL;
};


As you can see we made class name linkedlist and created a node which has two variables one for storing data and other for address.

Insertion in Linked List in C++

we will insert element at end of Linked List

void add(int val)
    {
         node* n= new node(val);
        if(head==NULL)
        {
            head=n;
          return;
        }
        node* temp=head;
        while(temp->next!=NULL)
        {

            temp=temp->next;
        }
        temp->next=n;
    }

Insert Node at beginning of Linked List

  void insertFirst(int val)
{
    node* n= new node(val);
    node* temp=head;
    head=n;
    head->next=temp;
}

Insert Node at specific index in linked list

we will insert element at specific position in a Linked List

 void addOn(int ind,int val)
    {

         node* n= new node(val);
    int i=0;

        node* temp=head;
        node* wamp=NULL;
        while(temp!=NULL)
        {
            if(i==ind-1)
            {
                wamp=temp;
            }
            if(i==ind) break;
          i=i+1;
            temp=temp->next;
        }
        if(ind>i){ cout<<"Not Possible \n"return;}
        n->next=temp;
        if(ind==0) {n->next=head;head=n; return;}
        wamp->next=n;
    }


Add node in Linked list by side of a number

we will insert a node by side of a specific number.

 void addAt(int Target,int num)
    {
        if(head==NULL) {cout<<" No element exist \n"return;}
        node* n= new node(num);
       node* temp=head;
        while(temp!=NULL)
        {
            if(temp->data==Target) break;
            temp=temp->next;
        }
        if(temp==NULL) {cout<<"No Such element exist \n"return;}
        n->next=temp->next;
        temp->next=n;

    }

Count Nodes in Linked List

we will count total number of Nodes present in a given linked list.

   void Count()
    {
        int i=0;
        node* temp=head;
        while(temp!=NULL)
        {
            i=i+1;
            temp=temp->next;

        }
        cout<<"The size of the Linked List is : "<<i<<"\n";
    }

Print all Element in Linked List


void Displays()
    {
    node* temp=head;

        if(head==NULL)
        {

            cout<<"No element present \n";
        }
    else{

        while(temp!=NULL)
        {

            cout<<temp->data<<"  ";


           temp=temp->next;

        }
    }
cout<<"\n";
    }


Sorting a Linked List

we will sort our linked list 

void Sort()
{
    node* curr = head;
    node* next;
    int temp;

    while (curr && curr->next)
    {

        node * next = curr->next;
        while (next)
        {
            if (curr->data > next->data)
            {
                std::swap(next->datacurr->data);
            }
            next = next->next;
        }
        curr = curr->next;
    }
}

Remove a Node in linked list

Let us write a program to delete a node from a linked list

 void RemoveVal(int Target)
    {
        if(head==NULL){ cout<<"Not Possible"return;}
       node* temp=head;
       int i=0;
         node* wamp=NULL;
        while(temp->next!=NULL)
        {
            if(temp->next->data==Target) wamp=temp;
            if(temp->data==Target) break;
            temp=temp->next;
            i++;
        }
        if(temp->data!=Target) {cout<<"No Such element exist \n"return;}
        if(i==0){head=head->nextreturn;  }
       wamp->next=temp->next;


    }

Count occurrence of a number in Linked list

void countInt(int num)
{

    int i=0;
    node* temp=head;
    while(temp!=NULL)
    {
        if(temp->data==num) i++;
        temp=temp->next;

    }

    cout<<num<<" appeared "<<i<<" times \n";


}

Program to Reverse a Linked List

linkedlist Reverse()
{
linkedlist l;
    node* temp= head;
    while(temp!=NULL)
    {
        l.insertFirst(temp->data);
        temp=temp->next;

    }

return l;

}



Assume you have made yr head variable access to all function above. we will cover other topics like Circular linked list and double linked list in our upcoming articles.
Practice important questions on this topic we will show you more questions on the topic of linked list.