Linked List Implementation ( C ++ ) Program

A Linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. 

Linked list is an Abstract Data Type ( ADT ).

Node definition ( Structure ) 

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

The num variable stores the data given by the user and the pointer (next) stores the address of the next element present in the linked list.

Operations 

void insert_beg(int value);
void insert_end(int value);
void insert_inBetween();
node* find(int cvalue,int p=0);
void input_ll();
void display();
void delete_ll();                                                                          void delete_node(); 

Function definitions

1) Inserting in beginning 

void insert_beg(int value){
     node* n=new node;
     n->num=value;
     if(first==NULL){
         n->next=NULL;
         first=n;
     }
     else{
         n->next=first;
         first=n;
     }
 }

the above function ,when called creates a new node and stores the value passed to it in num (variable) ,now the function checks if the list is empty and if it is empty then it is simply marked as the first element in the linked list.

if the list is not empty then the pointer (next ) is assigned to the first element address and the marker (first) is given to current element.

2) Insertion at end 

void insert_end(int value){
     node* n=new node;
     n->num=value;
     n->next=NULL;
     if(first==NULL)
         first=n;
     else{
         node* temp=first;
         while(temp->next!=NULL)
             temp=temp->next;
         temp->next=n;
     }
 }

This function is called when an element is to be stored in the last position of a linked list.

if the list is empty , we will add the element as first in the list.

if not then , we have to traverse the list first and stop when a node's (temp) next value is NULL and then point the node's (temp) next value to the node which is to be inserted.

3) Insertion in between two nodes 

void insert_inBetween(){
 int cvalue,value;
 cout<<"Enter the value after which you want to insert the new node"<<endl;
 cin>>cvalue;
 cout<<"enter the value of new node: ";
 cin>>value;
 cout<<endl;
 node *n,*prev;
 n->num=value;
 if(prev=find(cvalue,0)){
  n->next = prev->next;
  prev->next=n;
  cout<<"node inserted succesfully";
 }
 else{
  cout<<"Node value not found";
 }
}

for performing the insertion after an element given by the user , we need to know the location of the node after which it is to be inserted, for this another function (find()) will be called which will return the address of the node after which we have to insert the new node.

the function ( find() ) accepts two arguments value and the relative position of node (-1,0,1).

-1 : return the previous node

0 : return the current node

1 : return the next node

Definition of function node* find(int,int)

node* find(int cvalue,int p){
 node* temp=first;
 node* prev;
 prev=temp;
 while(temp){
  
  if(temp->num==cvalue){
   if(p==-1)
    return prev;
   if(p==0)
    return temp;
   if(p==1)
    return temp->next;
  }
  prev=temp;
  temp=temp->next;
 }
 return NULL;
}
 

Now, after finding the location of node we just have to assign the current node's next value to the node after (prev) (the node where the value given by the user is stored ) .

 n->next = prev->next;
 prev->next=n;                            cout<<"node inserted successfully";

and then link the new node (current) address to the prev->next to complete the joining of linked list.

4) Taking input from the user 

 void input_ll(){
 int tvalue,nl;
 cout<<"Enter number of members in Linked List\n";
 cin>>nl;
 cout<<endl<<"Enter Members"<<endl;
 for(int i=0;i<nl;i++){
  cin>>tvalue;
  if(T) insert_end(tvalue);
  else {insert_beg(tvalue);}
 }
 T=1;
}

The above function is made to take input values from the user and to call the insertion function:

void insert_beg(int value);
void insert_end(int value);

for adding nodes ( elements ) to the linked list.

The variable stores 1 by default ,to insert nodes in the end in sequential manner until the user decides to add the nodes in beginning of linked list.

5) Display the linked list 

void display(){
 cout<<"the linked list is as follows:"<<endl;
 node* tdis=first;
 while(tdis){
  cout<<tdis->num<<" ";
  tdis=tdis->next;
 }
}

The above function will traverse the linked list until it meets a location ( pointer ) which stores NULL , and display the value of num stored in each node.

The below functions for deleting node are very similar to insertion of a node. The functions definitions are given below .

6) Deleting node from beginning 

void delete_beg(){
 if(first==NULL){
  cout<<"Empty list\n";
 }
 else{
  node* temp=first;
  first=first->next;
  delete(temp);
 }
}

7) Deleting node from end

void delete_end(){
 if(first==NULL)
  cout<<"Empty list\n";
 else{
  node *temp=first;
  while(temp->next->next)
   temp=temp->next;
  delete(temp->next);
  temp->next=NULL;
 }
}

8) Deleting node from in between ( By searching for a specific node value )

void delete_node(){
 int dValue;
 cout<<"Enter the value you want to delete; ";
 cin>>dValue;
 if(first->num==dValue){
  node* t1=first;
  first=first->next;
  delete(t1);
 }
 else{
  node* prev=find(dValue,-1);
  node* dNode=prev->next;
  if(prev!=NULL){
   prev->next=dNode->next;
   delete(dNode);
  }
  else
   cout<<"Value not found"<<endl;
 }
}
  

Here ,the function find() is used again with parameter ( -1 ) ,so that it returns the address of the node preceding the node which contains the value to be searched .

FOR EXECUTABLE CODE : CLICK HERE :

SOURCE CODE ( C++)

/* Made by : Jatin yadav ( QxCoding )
 LINKED LIST OPERATIONS
*/
#include <iostream>
using namespace std;
struct node{
 int num;
 node* next;
};
int T=1;
node* first=NULL;
void clrscr(){
 for(int i=0;i<5;i++)
  cout<<endl;
}
void insert_beg(int value);
void insert_end(int value);
void insert_inBetween();
node* find(int cvalue,int p=0);
void input_ll();
void display();
void delete_beg();
void delete_end();
void delete_ll();
void delete_node();


int main(int argc, char *argv[]) {
 
 int choice;
 while(1){
 clrscr();
 cout<<"Enter the choice :"<<endl;
 cout<<"1)Insertion at begining"<<endl
  <<"2)Insertion at end"<<endl
  <<"3)Insertion after any given value"<<endl
  <<"4)Display Linked list"<<endl
  <<"5)Delete specific node"<<endl
  <<"6)Delete from end"<<endl
  <<"7)Delete from beginning"<<endl
  <<"8)Delete All nodes"<<endl
  <<"0)Exit"<<endl<<endl;
 cin>>choice;
 switch(choice){
  case 1: T=0;
  case 2: clrscr();input_ll();break;
  case 3: clrscr();insert_inBetween();break;
  case 4: clrscr();display();break;
  case 5: clrscr();delete_node();break;
  case 6: clrscr();delete_end();break;
  case 7: clrscr();delete_beg();break;
  case 8: clrscr();delete_ll();break;
  case 0: goto xit;
  default: cout<<"Invalid Input"<<endl;
 }
 }
 xit:
 delete_ll();
 
 return 0;
}



void insert_beg(int value){
 node* n=new node;
 n->num=value;
 if(first==NULL){
  n->next=NULL;
  first=n;
 }
 else{
  n->next=first;
  first=n;
 }
}
void insert_inBetween(){
 int cvalue,value;
 cout<<"Enter the value after which you want to insert the new node"<<endl;
 cin>>cvalue;
 cout<<"enter the value of new node: ";
 cin>>value;
 cout<<endl;
 node *n,*prev;
 n->num=value;
 if(prev=find(cvalue,0)){
  n->next = prev->next;
  prev->next=n;
  cout<<"node inserted succesfully";
 }
 else{
  cout<<"Node value not found";
 }
}
node* find(int cvalue,int p){
 node* temp=first;
 node* prev;
 prev=temp;
 while(temp){
  
  if(temp->num==cvalue){
   if(p==-1)
    return prev;
   if(p==0)
    return temp;
   if(p==1)
    return temp->next;
  }
  prev=temp;
  temp=temp->next;
 }
 return NULL;
}
 
 
void insert_end(int value){
 node* n=new node;
 n->num=value;
 n->next=NULL;
 if(first==NULL)
  first=n;
 else{
  node* temp=first;
  while(temp->next!=NULL)
   temp=temp->next;
  temp->next=n;
 }
}
void input_ll(){
 int tvalue,nl;
 cout<<"Enter number of members in Linked List\n";
 cin>>nl;
 cout<<endl<<"Enter Members"<<endl;
 for(int i=0;i<nl;i++){
  cin>>tvalue;
  if(T) insert_end(tvalue);
  else {insert_beg(tvalue);}
 }
 T=1;
}

 
void display(){
 cout<<"the linked list is as follows:"<<endl;
 node* tdis=first;
 while(tdis){
  cout<<tdis->num<<" ";
  tdis=tdis->next;
 }
}

void delete_ll(){
 node* temp=first;
 if(first==NULL){
  cout<<"Empty list\n";
  return;
 }
 while(first=first->next){
  delete(temp);
  temp=first;
 }
 delete(temp);
}
void delete_beg(){
 if(first==NULL){
  cout<<"Empty list\n";
 }
 else{
  node* temp=first;
  first=first->next;
  delete(temp);
 }
}

void delete_end(){
 if(first==NULL)
  cout<<"Empty list\n";
 else{
  node *temp=first;
  while(temp->next->next)
   temp=temp->next;
  delete(temp->next);
  temp->next=NULL;
 }
}

void delete_node(){
 int dValue;
 cout<<"Enter the value you want to delete; ";
 cin>>dValue;
 if(first->num==dValue){
  node* t1=first;
  first=first->next;
  delete(t1);
 }
 else{
  node* prev=find(dValue,-1);
  node* dNode=prev->next;
  if(prev!=NULL){
   prev->next=dNode->next;
   delete(dNode);
  }
  else
   cout<<"Value not found"<<endl;
 }
}

if any doubts or queries please comment