Implement a bag class using a linked list

QUESTION

I need to implement a Bag class using a linked list:

size(): int: returns the number of items in the bag

empty(): bool: checks to see if the bag is empty

add(): void: add a new item to the bag

remove(item): void: removes an item from the bag

clear(): void: removes all items from the bag

count(item): int: counts the number of times an item is found in a bag

contains(item): bool: checks to see if the item is in the bag

Write a simple code in C++.

SUMMARY

A linked list which has nodes with integer data and pointers pointing to the next node is used to implement a class bag. This bag has certain functions defined to perform operations like insert, delete, check if empty, etc. on the linked list.

EXPLANATION

The class node has data and next as the members. Data is the integer variable and next is the self-referential pointer to the same class. The class named bag is implemented having the head node as its member. The add function is defined and is to insert a particular item in the bag list. If the bag is empty, it is made as the head node otherwise it is added at the last.

The remove method takes in an integer and checks if it is present in the bag. If present, that node will be removed from the bag list. Size method is defined and used to count the number of nodes in it and returns that value.

The method empty is used to return true or false if the bag list is empty or not. Method count is implemented to take in an integer and check how many times that element is present in the bag list.

The method clear is used to make the bag empty. The method contains is defined to take in an element and check if it is present in the bag or not.

CODE

#include <iostream>
using namespace std;
class node 
{
    public:
    int data;
    node *next;
    node()
    {
        data=0;
        next=NULL;
    }
};
class Bag 
{
    public:
    node *head;
    Bag()
    {
        head=NULL;
    }
    /* to add a new node to the bag */
    void add(int nd)
    {
        node *newnode=new node;
        newnode->data=nd;
        newnode->next=NULL;
        if(head==NULL)
        head=newnode;
        else 
        {
            node *front=head;
            while(front->next!=NULL)
            front=front->next;
            front->next=newnode;
        }
    }
    /* removing an item from the bag */
    void remove(int item)
    {
        /* if the item is head */
        if(head->data==item)
        {
            head=head->next;
            return;
        }
        /* if the item is not head */
        node *prev=head;
        node *front=head->next;
        while(front!=NULL)
        {
            if(front->data==item)
            {
                prev->next=front->next;
            }
            prev=front;
            front=front->next;
        }
    }
    /* to count the number of elements */
    int size()
    {
        node *front=head;
        int c=0;
        while(front!=NULL)
        {
            front=front->next;
            c++;
        }
        return c;
    }
    bool empty()
    {
        if(head==NULL)
        return true;
        else 
        return false;
    }
    void clear()
    {
        head=NULL;
    }
    /* to count the number of times an element is present in the bag */
    int count(int ele)
    {
        node *front=head;
        int count=0;
        while(front!=NULL)
        {
            if(front->data==item)
            count++;
            front=front->next;
        }
        return count;
    }
    /* to check if element is present in the bag */
    bool contains(int ele)
    {
        node *front=head;
        while(front!=NULL)
        {
            if(front->data==item)
            return true;
            front=front->next;
        }
        return false;
    }
};
 
int main()
{
    Bag ba;
    ba.add(10);ba.add(20);ba.add(30);ba.add(40);ba.add(50);
    cout<<"Size of bag: "<<ba.size()<<endl;
    ba.remove(10);
    cout<<"Size of bag: "<<ba.size()<<endl;
    ba.add(20);
    cout<<"Count of 20: "<<ba.count(20)<<endl;
    cout<<"Empty? : "<<b.empty()<<endl;
    cout<<"Contains(40) : "<<ba.contains(40)<<endl;
    ba.clear();
    cout<<"Size of bag: "<<ba.size()<<endl;
}

OUTPUT

Size of bag : 6

Size of bag : 5

Count of 20 : 2

Empty? : 0

Contains(40) : 1

Size of bag : 0

Also read: Make a complete observation and analysis for this program based on a given budget.