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.
- Singly Linked List
- Double Linked List
- Circular Linked List
Uses of Linked List
- Linked List are used to represent polynomials and various operations on it.
- We can Represent Sparse matrix using Linked List.
- It is used in dynamic memory allocation.
- Linked list is used to implement stack and queues
- 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.
Implementation of Linked List
For Implementation of Linked list we follow following Procedures.
- We declare a Head node and initialize it will point to null value.
- Each Node will store data and address of it's next element.
- 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->data, curr->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->next; return; }
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.
