C++ Polymorphism | DSA in C++ - Software Development PDF Download

Introduction

Polymorphism is derived from the Greek words "poly," meaning many, and "morph," meaning form. In programming, polymorphism refers to the ability of objects of different types to be treated as objects of a common base type.
At its core, polymorphism allows us to write code that can work with objects of different types, as long as they share a common set of behaviors or properties. This enables us to write more flexible and reusable code.

Polymorphism in DSA with Inheritance

In DSA, we often work with various data structures such as arrays, linked lists, trees, and graphs. These data structures can be implemented using classes in C++. To achieve polymorphism, we can use inheritance.

Consider the following example, where we have a base class called 'DataStructure':

class DataStructure {

public:

    virtual void insert(int value) = 0;

    virtual void remove(int value) = 0;

    virtual bool contains(int value) = 0;

};

Here, 'DataStructure' is an abstract base class that defines three pure virtual functions: 'insert', 'remove', and 'contains'. These functions represent common operations that any data structure should provide.
Now, let's create a derived class 'Array' that implements the 'DataStructure' interface:

class Array : public DataStructure {

private:

    int* data;

    int size;

public:

    Array(int maxSize) {

        data = new int[maxSize];

        size = 0;

    }

    void insert(int value) override {

        // Insert implementation for arrays

    }

    void remove(int value) override {

        // Remove implementation for arrays

    }

    bool contains(int value) override {

        // Contains implementation for arrays

    }

};

Similarly, we can create other derived classes like 'LinkedList', 'BinaryTree', etc., that implement the 'DataStructure' interface.
Now, we can create objects of different data structures and treat them as objects of the base class:

DataStructure* ds = new Array(100);

ds->insert(42);

ds->remove(17);

bool result = ds->contains(42);

This code demonstrates polymorphism in action. We can use the 'DataStructure' pointer 'ds' to call the common functions 'insert', 'remove', and 'contains', regardless of the specific type of the object it points to.

Virtual Functions and Dynamic Binding

To enable polymorphism in C++, we use virtual functions. Virtual functions allow a derived class to override the implementation of a base class function. They are declared in the base class using the 'virtual' keyword.

In the previous example, the 'DataStructure' class declares its functions as virtual:

virtual void insert(int value) = 0;

virtual void remove(int value) = 0;

virtual bool contains(int value) = 0;

The '= 0' at the end of each function declaration makes them pure virtual functions, which means they have no implementation in the base class and must be overridden by derived classes.

Dynamic binding, also known as late binding, is a mechanism that determines the actual function to be called at runtime based on the type of the object, rather than the type of the pointer or reference. It allows us to call the appropriate derived class function through a base class pointer or reference.

In our example, when we call a virtual function through the 'DataStructure' pointer 'ds', the actual implementation of the function in the derived class (e.g., 'Array') is executed.

Polymorphic Data Structure

Let's put the concepts of polymorphism and DSA together in a practical example. We'll create a polymorphic stack data structure that can work with different underlying implementations, such as arrays or linked lists.
First, let's define the base class 'Stack':

class Stack {

public:

    virtual void push(int value) = 0;

    virtual int pop() = 0;

    virtual bool isEmpty() = 0;

};

Next, we'll create a derived class 'ArrayStack' that implements the stack using an array:

class ArrayStack : public Stack {

private:

    int* data;

    int top;

    int capacity;

public:

    ArrayStack(int stackSize) {

        data = new int[stackSize];

        top = -1;

        capacity = stackSize;

    }

    void push(int value) override {

        // Push implementation using array

    }

    int pop() override {

        // Pop implementation using array

    }

    bool isEmpty() override {

        // IsEmpty implementation using array

    }

};

Similarly, we can create another derived class 'LinkedListStack' that implements the stack using a linked list.
Now, we can use the polymorphic stack in our code:

Stack* stack = new ArrayStack(100);

stack->push(42);

int value = stack->pop();

bool empty = stack->isEmpty();

Here, we create a stack object 'stack' using the 'ArrayStack' implementation, but we can easily switch to 'LinkedListStack' or any other implementation by changing the type of the pointer 'stack'.

Sample Problems and Solutions

Here are a few sample problems to practice polymorphism in DSA:

Problem 1: Implement a polymorphic queue data structure that can work with arrays and linked lists.

class Queue {

public:

    virtual void enqueue(int value) = 0;

    virtual int dequeue() = 0;

    virtual bool isEmpty() = 0;

};

// Implement derived classes ArrayQueue and LinkedListQueue

Problem 2: Write a function that takes a pointer to the base class 'DataStructure' and performs a common operation on it.

void performOperation(DataStructure* ds) {

    ds->insert(42);

    ds->remove(17);

    bool result = ds->contains(42);

}

// Usage:

DataStructure* ds = new Array(100);

performOperation(ds);

These sample problems will help you practice using polymorphism in DSA and reinforce your understanding of the concepts discussed in this article.

Conclusion

Polymorphism is a powerful concept in C++ that allows objects of different types to be treated as objects of a common base class. In the context of DSA, polymorphism enables us to create generic data structures that can work with various types of data. By using virtual functions and dynamic binding, we can write code that is flexible, reusable, and easy to maintain.
Remember, polymorphism is just one of the many tools in the C++ toolbox, and mastering its usage will enhance your ability to design and implement complex software systems. So, keep exploring and experimenting with polymorphism in DSA to unlock its full potential in your programming journey.