Stack in STL C++

 Stacks are linear data structures. The last added element is removed first and the first added element is removed at the last. So it  is a LLIFO or FILO data structure.

Functions associated with stack :

empty() : returns true if stack is empty else false

size() : returns stack size

top() : returns a top reference to the top most element of the stack

push(): to add the element at the top of the stack.

pop() : to delete the top most element of the stack

void showstack(stack <int>s)

{

while(!s.empty())

{

cout<<'\t'<<s.top(); s.pop();

} //while ends

cout<<'\n';

} //to print stack

int main()

{

stack<int> s;

s.push(10); 

s.push(30);

s.push(20); 

s.push(5); 

s.push(1); 

cout<<showstack(s);

cout<<s.size(); cout<<s.top();

cout<<s.top(); 

showstack(s);

} 

Stacks Data Structcure

 Stack is a linear data structure. It follows a special order in which operations are performed. The order is LIFO or FILO. 

This can be understood by an easy example. A stack of plate. As you can imagine, the plate on the top is removed first which means that the last plate added is moved first which is LIFO.

In the same way, the First In plate will be removed at the last which is FILO. So we can conclude that the first plate added will remain for the longest time.

3 operations: Push- to add an item in the stack. If the stack is full, it is said to be an underflow condition.

Pop- to remove an item from the stack. The items are popped out in the reverse order in which they are pushed.

Peek or Top- to return the top element of stack.

isEmpty- returns true if stack is empty else false.

Time complexity: pop() push() isEmpty() peek() all takes O(1). We do not use any loop in these operations.

Application: 1. Redo Undo features for apps like editors, photoshop.

2. Forward and backword feature in web browsers.

Implementation: We can implement a stack using array and linked list.

4Methods:Intersection of 2 sorted LL

 Method1: using dummy node

method2: using local references

method3: a recursive approach

using dummy node: put a dummy temp node at the start of the result list. Pointer tail will always point to the last node in the result list, so new nodes can be added easily. 

dummy node gives the tail a special memory to point to. This dummy node is efficient as it is temporary, and it is allocated in the stack. 

The loop proceeds removing one node from either a or b and adding it to the tail. 

when the given lists are traversed, the result is in dummy. next as the values are allocated from the next node of the dummy. 

If both the elements are equal then remove both and insert the element to the tail. else remove the smaller element among both the lists.

Code:

void push(node** head_ref, int new_data)

{

  node dummy; node* tail= &dummy;

  dummy.next= NULL; 

while(a!=NULL && b!=NULL) 

{

if(a->data==->data)

{

push((&tail->next),a->data);

tail=tail->next; a=a->next;

b=b->next;

} //if ends

//advance the small linked list

else if(a->data <b->data)

a=a->next;

else b=b->next;

} \\while ends

return (dummy.next);

} //function ends

void push(node** head_ref, int new_data) {}

void printlist(node* head) {}

int main() {}

TC- O(M+N)

Method2: using local references

Using local reference is structurally very similar to the dummy node method.  But we do not use a dummy node in this method. 

Instead, it maintains a struct node** pointer, lastPtrRef that always points to the last pointer of the result list. 

This solves the case that the dummy node did.  If we want to make the list at the tail node, either dummy method or struct node** reference method can be used. 

struct node{} 

void push(struct node** head_ref, int new_data) {} 

void node* sortedintersect(struct node* a, struct node* b)

{

struct node* result= NULL; //took a pointer name result

struct node** lastPtrRef = &result;

//advance comparing first nodes in both lists. 

//when 1 lists ends , we are done

while(a!=NULL && b!=NULL) 

{

if(a->data==b->data) //got matching data

{

push(lastPtrRef, a->data);

lastPtrRef= &((*lastPtrRef)->next);

a=a->next; b=b->next;

} //ifends

else if(a->data< b->data) 

a=a->next; //advance th smaller list

esle b=b->next;

} //while ends

return (reuslt);

}

void push(struct node** head_ref, int new_data) {}

void printlist(struct node* head)

int main() {}

Method3: Recursive sol

Move last element of LL to front

 Approach: 

1. Traverse the list till last node.

2. Take 2 pointers: one to store the address/ pointer of last node and other to store the pointer/address of 2nd last node.

3. After the loop is executed, do the following operation:

a) Make second last node as last node of list(seclast->next=NULL)

b) Set next of last node as head(last->next=*head_ref)

c) Make last node as head node(*head_ref= last) 

Code

class node{}

void movetofront(node **head_ref)

{

    //do nothing if list is empty or contain only 1          node

    if(*head_ref==NULL || 

    (*head)- >next==NULL) 

    return;

     //initialize 2nd and last pointers

     node *seclast=NULL; 

     node *last=*head_ref;

     

     

 //after loop seclast pointer stores address of   seclast node and last stores the address of last   node

  while(last->next!=NULL)    

 {

  seclast=last; last=last->next;

  }  //while ends  

//set next of secalst as NULL

seclast->next=NULL; 

last->next= (*head_ref); //set last node pointer point to headnode

(*head_re)f= last;

} //function ends

void push(struct node** head_ref, int new_data) {}

void printlist(node* head) {}

int main() {}

Swap nodes in pairs : 2 methods

 Method1: iterative approach

Start traversing from the head, swap data of each node with the data of its next node. 

class node{}

void pairwiseswap(node* head) 

{

   node *temp= head; 

//traverse only if atlest 2 nodes are left

while(temp!=NULL && temp->next!=NULL)

{

  swap(temp->data, temp->next->data);

temp->next->next; //move temp by 2 units for next pair wise swap

}  //while loopends

}  //function ends

void push(node** head_ref, int new_data) {}

void printlist(node *head) {}

int main() {}

Recursive approach: by using a function

void pairwiseswap(struct node * head)

{

   if (head!=NULL  && head->next!=NULL) //if there are atleast 2 nodes

 {

      //swap head and head next data 

     swap(head->data, head->next->data);  

      

       //call pairwiseswap method/fuction for rest              of  list

      pairwiseswap(head->next->next)

 } //if ends

} //function 

Swap nodes withoud swapping data

Approach: 

1. First, we will search the nodes x,y. 

2. If they are not present in the linked list, do nothing.

3. While searching for x and y keep track of the current and previous pointers.

4. First change the next of the previous pointer and then change the next of the current pointer.

Code:

Class node{}

void swapnode(node** head_ref, int x, int y)

{

//do nothing if both are same

if (x==y) return 0; 

//search for X and keep track of previous and current pointer

node *prevx= NULL, *currx= *head_ref;

while(currx && currx->data !=x)

{

prevx=currx; currx= currx->next;

}

//search for Y and keep track of the previous and current pointer

node *prevy=NULL, *curry=*head_ref;

while(prevy && curry->data)

{

 prevy= curry; curry= curry->next;

}

//if both X Y  are absent do nothing

if(currx==NULL || curry==NULL ) return;

//if x is not head of list

if(prevx!= NULL) prevx->curry;

else  *head_ref =curry; //make y as newhead

//if y is not head of list

if(prevy!=NULL) prevy->next= currx; 

else  *head_ref = currx;

}

//swap next pointers

node *temp = curry->next;

curry->next= currx->next;

currx->next= temp;

}

void push(node** head_ref, int new_data){}

void printlist(node* head) {} 

int main() {}

__________________________

A little optimization

void swap(node *& a, node *& b)

{ node *temp= a; a=b; b= temp;

}

void swapnode(node **head_ref, int x, int y)

{ if(x==y) return;

//search x,y and store their pointers in a and b

while(*head_ref)

{

if((*head_ref)->data==x){ a=head_ref;}

else if((*head_ref)->data==y) {b= head_ref;}

head_ref = &((*head_ref)->next);

} //while ends

//if a, b found, swap current and next pointer of these

if(a && b) 

{ 

   swap(*a, *b); 

swa(((*a)->next), ((*b)->next));

}

}

int main() {}

Using hashing remove duplicates from unsorted list

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

struct node{

    int data; struct node* next;

};

struct node *newnode(int data)

{

    struct node *temp= new node;

    temp->data= data; temp->next= NULL; return temp;

    

} //nn ends

void remdup(struct node* head)

{

    unordered_set<int> seen; //hash to store seen values

    //name of hash is seen

    

    //pick elements 1 by 1

    struct node *curr= head;  

    struct node *prev= NULL; 

    while(curr!=NULL) //traverse the list to the last node

    {

        //if current data is seen before

        if(seen.find(curr->data)!=seen.end())

        {

            prev->next=curr->next; delete(curr);

        } //if ends

        

        else {

            seen.insert(curr->data); prev= curr;

        } //else ends

        

        curr= prev->next;

    } //w ends 

    

} //fends

void printlist(struct node* head)

{

    while(head!=NULL) 

    {

         cout<< head->data<<" "; head= head->next;

    } //while ends

    

} // f ends

int main() {

struct node* head= newnode(10);

head->next = newnode(12);

   head->next->next = newnode(11);

   head->next->next->next = newnode(11);

  head->next->next->next->next = newnode(12);

    head->next->next->next->next->next =

                                    newnode(11);

   head->next->next->next->next->next->next =

                                    newnode(10);

printlist(head);

remdup(head);

printlist(head);

return 0;

}

 

using 2 loops Remove duplicates from unsorted linked list

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

struct node{

    int data;

    struct node* next;

};

//function to create  a new node

struct node* newnode(int data) //newnode is a pointer and data is its data

{

    node* temp= new node; temp->data=data;

    temp->next=NULL; return temp;

    

} //newnode ends

void remdup(node* start)

{

    struct node *ptr1, *ptr2, *dup;

    ptr1= start;  //put ptr1 on head

    while(ptr1!=NULL && ptr1->next!=NULL) //loop to pick element 1 by 1

    {

        ptr2= ptr1;

        while(ptr2->next!=NULL) //compare picked element with rest elements

        {

            if(ptr1->data==ptr2->next->data) //if duplicate then delete it

            {

                dup= ptr2->next;

                ptr2->next= ptr2->next->next;

                delete(dup);

                

            } //if ends

            else ptr2=ptr2->next;

            

           

        } //w ends

           ptr1= ptr1->next;

    } //w ends

    

    

} //fends

void printlist(node *node)

{

    while (node!=NULL)

    {

        cout<<node->data<< " "; node= node->next;

    } //w ends

    

} //f fends

int main() {

struct node *start= newnode(10);

 start->next = newnode(12);

    start->next->next = newnode(11);

    start->next->next->next = newnode(11);

    start->next->next->next->next = newnode(12);

    start->next->next->next->next->next =

                                    newnode(11);

    start->next->next->next->next->next->next =

                                    newnode(10);

 

  printlist(start); 

  remdup(start);

  printlist(start);

return 0;

}

 

Recursive method to delete duplicates from list and print list

 #include <iostream>

#include <bits/stdc++.h>

using namespace std;

class node{

    public: int data; node* next;

    

};

void remdupli(node* head)

{

    node *tofree ; //pointer to store  pointer of node to be deleted

    if(head==NULL) return; //do nothing if list is empty

    if(head->next!=NULL) //traverse list to the last node

    {

        if(head->data==head->next->data) //compare head and next node

        {

            tofree=head->next; //tofree strores the next of headpointer to be delected

            head->next==head->next->next; //move headnext by 1 unit

            free(tofree); 

            remdupli(head);

        }

        

        else

        {

            remdupli(head->next); //only advance if no deletion

        } //else ends

    } //if ends

    

} // f ends

void push(node** head_ref, int new_data)

{

    node *new_node= new node();

    new_node->data= new_data;

    new_node->next= (*head_ref);

    (*head_ref)=new_node;

    

} //f ends

void printlist(node* node)

{

    while(node!=NULL)

    {

    cout<<node->data<<" ";

    node= node->next;

    } //while ends

} //f ends

int main() {

 node *head= NULL;

 push(&head, 20);

  push(&head, 13); 

    push(&head, 13); 

    push(&head, 11); 

    push(&head, 11); 

    push(&head, 11);  

    printlist(head); //list before duplicate removal

    remdupli(head); //method to remove duplicate

    printlist(head); //list after duplicate is removed

 

return 0;

}

Remove duplicates from a sorted ll and print

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

//take ll node

class node{

  public:  int data; node* next;

};

//function to rem duplicates from sorted list

void remdupli(node* head)

{

    node *current = head;  //current pointer points to head

    node *next_next;      //another pointer named next_next

    //next next pointer willl store the pointer of the node to be deleted

    

    if(current== NULL) return;  //if list empty do nothing

    

    //traverse the list till last node

    while(current->next!=NULL)

    {

       if(current->data==current->next->data) //compare current and next node

       {

         next_next=current->next->next; 

         free(current->next); 

         current->next= next_next;

        

       } //iffends

       

       else {current=current->next;} //if duplicate not found, move pointer 

    } //while ends

} //f ends

//function to push nodedata

void push(node** head_ref, int new_data) // head_ref is a pointer, points to  head

{

    node* new_node= new node(); //new_node is a pointer 

    new_node->data= new_data; //its data is new data

    new_node->next= (*head_ref); //its next is head pointer

    (*head_ref) = new_node;   //head points to new node

    

} //push fends

void printlist(node* node)

{

    while(node!=NULL) //till there is a node 

    {

        cout<< node->data<< " "; //cout the data

        node=node->next; //move poiinter by unit1

    } //w ends

    

} //f ends

int main() {

node *head= NULL; //make head pointer point to null

push(&head, 20);

push(&head, 13); 

    push(&head, 13); 

    push(&head, 11); 

    push(&head, 11); 

    push(&head, 11); 

printlist(head);  //list before duplicate removal

remdupli(head);   //function which removes the duplicate

printlist(head); //list after duplicate removed

return 0;

}

Method3: Detect and remove ll(hashing)

 We will use hashing method to hash the address of the nodes. 

1. first hash the address of the nodes in the map

2. Traverse the list 

3. We find a loop if any element matches

4. Make the next of the pointer point to null

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

struct node{

    int key;

     struct node* next;

    

};

node *newnode(int key)

{

    node *temp= new node; temp->key= key; temp->next= NULL;

    return temp;

    

} //newnode ends

void printlist(node* head)

{

    while(head!=NULL)

    {

        cout<<head->key<< " ";

        head=head->next;

        

    } // while ends

    cout<<endl;

} //f ends

void hashandremove(node* head)

{

    unordered_map<node*, int>node_map;

    node* last= NULL;

    while(head!=NULL) 

    {

        if(node_map.find(head)==node_map.end())

        {

            node_map[head]++; last= head; head=head->next; 

            

        } //if ends

        else {

            last->next= NULL; break;

        }

        

        

    } //while ends

    

} //f ends

int main() {

node* head= newnode(50);

head->next= head;

head->next->next= newnode(20);

head->next->next = newnode(15);

    head->next->next->next = newnode(4);

    head->next->next->next->next = newnode(10);

 

    /* Create a loop for testing */

    head->next->next->next->next->next = head->next->next;

 

    // printList(head);

    hashandremove(head);

 

    printlist(head);

return 0;

}

Method2: Detect and remove loop(count nodes)

 By counting number of nodes in the loop

1. Detect loop

2. Count no of nodes in the loop.(say k)

3. Put 1 pointer on head and other at k units apart from pointer1.

4. Get the start node of the loop

5. Make the next of the start node point to NULL.

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

struct node{

    int data;

    struct node* next;

};

void remloop(struct node*, struct node*);

int detandremloop(struct node* list)

{

    struct node *sp= list, *fp=list;

    while(sp && fp && fp->next)

    {

        sp=sp->next;

        fp= fp->next->next;

        if(sp==fp) {

        remloop(sp, list);

            return 1;

        } //if ends

        

    } //while ends

    return 0;

} //int ends

void remloop(struct node* loop_node, struct node* head)

{

    struct node* ptr1= loop_node;

    struct node* ptr2= loop_node;

    

    unsigned int k=1;

    while(ptr1->next!=ptr2)

    {

        ptr1= ptr1->next;

        k++;

        

    } //while ends

    

    ptr1= head;

    for (int i=0; i<k ; i++)

    ptr2= ptr2->next;

    

    while(ptr2!=ptr1) {

        ptr1=ptr1->next; ptr2= ptr2->next;

    } //whhileends

    

    while(ptr2->next!=ptr1)

    ptr2=ptr2->next;

    ptr2->next = NULL;

    

} //f ends

void printlist(struct node* node)

{

while (node!=NULL)

{

    cout<< node->data<< " ";

    node=node->next;

    

} //whileends

} //f ends

struct node* newnode(int key)

{

    struct node* temp= new node();

    temp->next= NULL; temp->data= key;

    return temp;

} //newnode ends

int main() {

  struct node* head= newnode(50);

  head->next= newnode(20);

head->next->next= newnode(15);

head->next->next->next= newnode(4);

head->next->next->next->next= newnode(10);

head->next->next->next->next->next= head->next->next;

detandremloop(head);

printlist(head);

return 0;

}

Method1: Detect and remove loop in a linked list

1. detect loop

2. store the address of the common node in a pointer

3. put slow pointer on head

4. move both pointers by unit 1

5. Now make the next of the common node found again point to null.

Detect loop using Floyd cycle detection algorithm and then 

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

struct node{

    int data;

    struct node* next;

};

void remloop(struct node*, struct node*);

int detandremloop(struct node* list)

{

    struct node *sp=list, *fp=list;

    while(sp&& fp&& fp->next)

    {

        sp= sp->next;

        fp= fp->next->next;

        if(sp==fp) {

            remloop(sp, list);

            return 1;

        } //if ends

        

    } //while loop ends

   return 0; 

} //int ends

void remloop(struct node* loop_node , struct node* head)

{

    struct node *ptr1;

    struct node *ptr2;

    ptr1= head;

    while(1)

    {

        ptr2 = loop_node;

        while(ptr2->next !=loop_node && ptr2->next != ptr1)

        ptr2= ptr2->next;

        if(ptr2->next==ptr1) break;

        ptr1=ptr1->next;

    } //while loop ends

        ptr2->next= NULL;

    

} //f ends

void printlist(struct node* node)

{

    while(node!= NULL){

    cout<<node->data<< " ";

    node=node->next;} //while ends

} //f ends

struct node* newnode(int key)

{

    struct node* temp= new node();

    temp->data= key;

    temp->next= NULL;

    return temp;

    

} //newnode ends

int main() {

struct node* head = newnode(50);

head->next= newnode(20);

head->next->next= newnode(15);

head->next->next->next= newnode(4);

head->next->next->next->next= newnode(10);

head->next->next->next->next->next= head->next->next;

detandremloop(head);

printlist(head);

return 0;

}

Detect and remove a LL Loop: 4 METHODS

There are a lot of approaches that we can use to detect and remove a loop. 

This is the question which is asked in many good companies. So make sure to practice it before going to an interview.

LOOP DETECTION: Floyd Cycle detection algorith is the most commonly used algorith to detect a loop in a linked list. 

Floyd cycle detection algorithm: In this algorithm, we use tortoise and hare pointers. 

Tortoise_pointer-> next; //moves by one unit

hare_pointer->next->next; //moves by 2 units

At the point when both the two-pointer are at the same node, there is a loop. If not there is no loop in the linked list.

Code: to be added later

Method 1 for Loop Removal: 

Let's say we detected the loop and now our task is to remove the loop from the list. We got the common point/node which is also a node of the loop. We will store the address of this common point/node in a pointer say, pointer_2. Put a pointer (say pointer_1) at the head of the Linkedlist. 

Now check for the nodes 1 by 1 if they are reachable to pointer_2. If we are able to find a node which is reachable to the pointer_2, then that node is the starting node of the loop found in the Linked List.

With this starting node we can find the previous node of this node, and make that last node point to NULL. 

For this, we will use two more pointers. We will find the last node of the loop and make it point to NULL. 

last_nodeof_loop->next= NULL;

Idea: the very first node whose next node is visited is the last node.

 

Method 2: By counting the no of nodes of loop

First detect loop using Floyd cycle detection algorithm. Set a pointer on the common node/point found while loop detection. Count the number of loops. Lets say the count is n. 

Fix one pointer to the head and another to a nth node from the node. Move both the pointers at the same pace. Soon they will meet at the starting node of the loop. 

So we got the start node of the loop, the n we can get the last node of the loop. Then make the last node to point to NULL. This is it. 

Method 3: Optimised method of method 2

Without counting the nodes in loop

Let us say we have detected the loop usign floyd cycle detection algorithm. Put slow_pointer on head. Now we will move both the slow and fast pointer with a same pace until they meet again.

Method 4:  Hashing

We will hash the address of the linked list node in an unordered map. We will check if the element already exists in the map. If yes, then we found the start node of the loop. Then we will make the last pointer of the loop to point to NULL.

Swiggy app Case study from uiuxdesign.cc

 https://uxdesign.cc/swiggy-food-order-delivery-app-a-heuristic-evaluation-case-study-435b3aa8022d

Point to be noted

1. Well labelled icons: well-labelled icons are really helpful for the end-users as they do not need to learn the use of the icons.

2. Availability of Feature to remove the cart dish for the current screen: This is the best feature in the Swiggy app that you can remove a cart dish from the current screen. So you do not need to go back to the cart in order to delete the dish. This is the feature which is missing in many of the companies.

3. Confirmation feature at the time of address deletion:  So if you want to delete an address, you cannot undo it but the app reconfirms for the same action.

4. Food search box Suggestions: The search box shows the recent searches of the user so that they can directly reorder the dishes they have ordered before. This feature can be of great help for the regular users of the app.

5. Well defined "Apply coupon" section: When you click on apply coupon button, you are redirected to the coupon page. There you can see all the coupon codes and their corresponding benefits. You can choose accordingly and use it instantly.

In other apps, they redirect the user to the coupon page and then you have to search for the coupons by searching manually. 

6. Areas for improvement: There were no sorting/ filtering options for restaurants; like lexicographically/alphabetically, cost, relevancy, rating, or delivery time. 

No category/search options for large menu restaurants: It is tedious to search manually for the dishes in large menu lists. It is much better to provide "Dish Category feature".

7. Error diagnostics: The frequent problem of the users is the "currently unserviceable" error. For this Swiggy does not provide any kind of explanation like the location too far/ restaurant closed etc. 

8. FAQ section: Swiggy has a well-documented faq section and support section. It is very easy to initiate a live chat.

FLOYD CYCLE FINDING ALGO for loop detection in linked list

 //FLOYD CYCLE FINDING ALGO

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

//create node with class

class node{

   public: int data;

    node* next;

};

//create funtion to push data later

void push(node** head_ref, int new_data)

{

    node* new_node= new node();

    new_node->data= new_data;

    new_node->next= (*head_ref);

    (*head_ref)= new_node;

}// push ends

//main algo

int detloop(node* list)

{

    node* slow_p= list, *fast_p= list;

    while(slow_p && fast_p && fast_p->next)

    {

        slow_p=slow_p->next;

        fast_p=fast_p->next->next;

        if(slow_p==fast_p) {return 1;}

    }// while ends

return 0;

} //intends

int main() {

node* head= NULL;

push(&head, 20);

push(&head, 4) ;

push(&head, 15);

push(&head, 10);

//create a loop for testing

head->next->next->next->next= head;

if(detloop(head)) cout<<"loop found";

else cout<<"no loop";

return 0;

}

DP OR Dynamic programming

 DP or dynamic programming is an optimization of a recursive solution. Recursive solution means a functional solution in which you made a function to solve a problem.

Before going to a interview make sure you solve a good amount of dp problems. Most of the initial interview round questions ask classical dp problems. 

detect a loop in linked list using hashing

1. HASHING

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

//hashing to detect a  loop in a linklist

struct node{

    int data; struct node* next;

};

void push(struct node** head_ref, int new_data)

{

    struct node* new_node= new node(); new_node->data= new_data;

    new_node->next= (*head_ref); (*head_ref)= new_node;

} //f ends

//returns true if a loop is detected

bool detectloop(struct node* hash)

{

    unordered_set<node*> set;

    while(hash!=NULL) {

        if (set.find(hash)!=set.end()) return true;

        set.insert(hash); //if we are visiting a new node , insert in hash

        hash= hash->next;

        

    } //while ends

    return false;

} //bool ends

int main() {

 struct node* head= NULL; //start with empty linkedlist

 push(&head, 20);

  push(&head, 4);

   push(&head, 15);

    push(&head, 10);

 

   //create a loop for testing

   head->next->next->next->next=head;

   if(detectloop(head)) cout<< "Loop found";

   else cout<< "No loop here";

return 0;

}

Frequency of data in Linked list

 2 Approaches

1. Normal traverse o (n)

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

//normal traversing approach

class node{

    public:

    int data;

    node* next;

};

void push(node** head_ref, int new_data)

{

    node* new_node= new node(); new_node->data= new_data;

    new_node->next= (*head_ref); (*head_ref)= new_node;

    

} //f ends

int count(node* head, int search_for)

{

    node* current = head; int count =0;

    while(current!=NULL) 

    {

        if(current->data== search_for) count++; current= current->next;

        

    } //while ends

    return count;

}//count ends

int main() {

  node* head= NULL;

  push(&head, 1);

   push(&head, 3);

    push(&head, 1);

     push(&head, 2);

      push(&head, 1);

     cout<<count(head, 1)<<endl;

return 0;

}

2. HASHMAP

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

//using hashmap key:value

struct node{

    int data;

    struct node* next;

};

//global var to count frequency of element k

int freq;

void push(struct node** head_ref, int new_data)

{

    struct node* new_node= new node(); new_node->data= new_data;

    new_node->next= (*head_ref); (*head_ref)= new_node;

} //f ends

int count(struct node* head, int key)

{

    if(head==NULL) return freq; 

    if(head->data==key) freq++; return count(head->next, key); 

} //count ends

int main() {

struct node* head= NULL;

push(&head, 1);

push(&head, 2);

push(&head, 3);

push(&head, 4);

push(&head, 1);

cout<< count(head, 1)<<endl;

return 0;

}