DEV Community: Scaler Topics

What is Foreign Key in DBMS?

Pranjali Nandan — Fri, 04 Mar 2022 10:15:22 +0000

Before understanding the concept of foreign keys, let’s understand what a key is. So, as we know, in a database, we store our data in the form of tables, in the form of rows and columns in a table. What if we want to connect two or more tables with each other? For that, we need to understand the concept of a key. So, using the concept of primary key and foreign key Let's understand what the foreign key is in this article.

A foreign key is a column or a group of columns in a database table which must match with some other column in another table. In simple words, we can say a column which is common in two tables can be considered a foreign key. Let’s understand more clearly what foreign keys are using an example given below.

This is a student table, in which we have roll no, name, class, and age as attributes. This type of storage of data is seen in our databases (in the form of tables). Let's explore another table named "Student Info Table."

As we can see, it is a table containing information about a student, such as fees, status, contact information, and address. If you see, both tables (student and student info) have a common column, which is Roll No. So rolling no column in the student info table will work as a foreign key and rolling no column in the student table will work as a primary key. Using the concept of a foreign key and a primary key, we can connect both the tables.

Foreign Key Query in MySQL

Let’s see how we can write code of foreign key in MySQL.
CREATE TABLE Student info ( Roll no int NOT NULL, Fees status varchar (30), Contact no int NOT NULL, Address varchar (50) NOT NULL, PRIMARY KEY (Roll no), FOREIGN KEY (Roll no) REFERENCES Student (Roll no) );

Let’s explore how we can add content to these tables.

INSERT INTO Student VALUE (21,’Ramesh’, ‘10th’,15); INSERT INTO Student VALUE (22,’Atul’, ‘3rd’,8); INSERT INTO Student VALUE (23,’Rahul’, ‘8th’,13); INSERT INTO Student VALUE (24,’Piyush’, ‘12th’,17); INSERT INTO Student VALUE (25,’Arnav’, ‘7th’,13);

Remove the Foreign Key Constraint

If we want to write a SQL command to drop a foreign key constraint, then we will write the following command.

ALTER TABLE Student DROP FOREIGN KEY

Why do we need Foreign Key?

Using the concept of a foreign key, we can connect two or more tables as we can create a relationship between those tables with a common attribute.
Foreign keys also help us to maintain the referential integrity of the database.

How does Foreign Key maintain Referential Integrity?

Let's understand this concept with the help of two tables? One is the student table, which contains the roll number, name, and address of a student, and the other table is the course table, which contains information about a student's course.

So, roll no in the course table (referencing table) will work as a foreign key and roll no in the student table will work as a primary key. Here, the student table is the reference table and the course table is the referencing table. So, the main thing we'll learn in this topic is what happens if we insert, update, or delete something in this table. So, let's explore that part also.

Insert – If we insert any entry into our base table, that is, the student table, then it will not create any issue. We can insert as many entries as we want, and it won’t create any issue for insertion. As a result, there is no violation in insertion.
Delete – If we delete any entry from our base table, like if any student leaves an organization, then we have to delete that data from our table. Let’s consider that roll no. 1 leaves the organization, and we delete that entry from the student table. But in the course table, we see that roll no. 1 is currently studying network subjects. So directly deleting will create an issue. Integrity will be lost in this case. But if we consider a case where we insert a new entry, let’s say roll no 4, and then we delete that roll no, then it will not create any issue. So, deletion may create a violation.

So, what do you think will be the solution to this issue? So, we have a concept of a delete cascade where the row that we are deleting will be automatically deleted from other tables also. Another method is to delete set null where the row we are deleting is found, and if the same row is found in another table, then we set the foreign key value null on that set. Another method is to delete data with no action. As the name suggests, it will not do any action, so data will be deleted in this case.

Update – If we want to update any row, then it will create an issue, like if we have to update that data in other related tables, as we saw in the deletion. We can use the same method that we perform on deletion, that is, on update cascade, on update set null, on update no action. Updating may result in a violation.

To learn more about the concepts of primary key and the distinction between primary key and foreign key on Scaler Topics

Author: Arnav Bhardwaj

Difference Between
and
Tag in HTML

Pranjali Nandan — Thu, 24 Feb 2022 11:09:14 +0000

Introduction

Suppose you want your webpage to show the below message with the same format, How will you write it in HTML?

If you are planning to use carriage return (ENTER key) to produce line breaks, then let me tell you that it won’t work because HTML will ignore any carriage return and extra spaces.

You can use the br tag which is used to produce line breaks in HTML and here are the two possible ways of using br tag.

Snippet 1:

<div> Hello <br> Welcome to <br> the blog<br> </div>

Snippet 2:

<div> Hello <br/> Welcome to <br/> the blog <br/> </div>

Both will give the same output, but what is the difference between br and br/?

But before that let’s look at some pointers.

br tag is used to produce line breaks in an HTML document and it is a self-closing tag.
When a tag is used with nothing between it, then a self-closing tag (or empty tag) can be used. br is one such self closing tag, which means there is no need of closing tag ( /br) while using br.
Generally, TAG/ (not to be confused with /TAG) is used as a condensed way of writing TAG.../TAG.

So from the above pointers, it is evident that br and br/ will provide the same results when used in HTML.

But, whenever we are using XHTML (which is more strict than HTML), it doesn’t allow leaving tags open (like you cannot write just br, you have to close it also but /br doesn't make sense since it is a self-closing tag ), hence br/ will be used in that case.

Also using br is less effective when it comes to code neatness and readability than br/. Hence br/ is generally preferred over br

To sum up, the key differences between br and br/ in HTML can be understood with the help of the following table:

Difference between br and br/ Tag

Browser Compatibility

Let’s look at its browser compatibility now

Desktop Browsers

Conclusion

Both br and br/ produces the same result i.e line break. But br/ is preferred because it can be used with strict rules as well(like while writing XHTML document) and the latter looks cleaner and readable.

Read more about other self-closing tags on Scaler topics.

Author: Rdiddhi Suteri

Advantages of Doubly Linked List in Data Structure

Bikash Daga — Mon, 21 Feb 2022 10:06:10 +0000

Introduction

A linked list contains nodes in which each node has a data part and the reference to the next node. Each node in a linked list is connected via links. The operations that can be performed on a linked list are search, insert, delete, traverse, etc. There are various kinds of linked lists like singly link list, doubly link list and circular link list.

In this article, we will see the most used doubly link list and its advantages.

What is a Doubly Linked List?

Doubly linked list is a variation of linked list in which we can move forward and backward. We can define a doubly linked list using the following terms -

Link: Each link of a linked list can store a data called an element.
Next: Each link of a linked list contains a link to the next link called Next.
Prev: Each link of a linked list contains a link to the previous link called Prev.
LinkedList: A Linked List contains the connection link to the first link called First and to the last link called Last.

An example of a doubly linked list is the tabs in the browser, you can move to any tab forward or backward.

So if a Linked List ⇒ A → B → C
Then a Doubly Linked List ⇒ A ⇆ B ⇆ C

Representation of a Doubly Linked List in Data Structure

A class node is created that contains a data variable to hold the value of a node. A next pointer to store the address of the next linked node in the list.

A prev pointer to store the address of previously linked nodes in the list.

C++ Code

class Node
{
    public:
    int data; // value of a node in linked list 
    Node* next; // Pointer to next node in DLL
    Node* prev; // Pointer to previous node in DLL
};

C Code

struct Node // create a structure for C ll 
{
    int data; // value of a node in linked list 
    struct Node* next; // Pointer to next node in DLL
    struct Node* prev; // Pointer to previous node in DLL
};

Operations on a Doubly Linked List

The following are some various operations that can be performed in a doubly linked list -

Add a Node in the Front Steps involved -

Allocate node
Put in the data
Make next of new node as head and previous as NULL
Change prev of head node to new node
Move the head to point to the new node

Add a Node After a Given Node Steps involved -

Check if the given previous node is NULL
Allocate new node
Put in the data
Make next of new node as next of previous node
Make the next of previous node as new_node
Make previous node as previous of new_node
Change previous of new_node's next node

Add a Node in the End Steps involved -

Allocate node and put in the data
This new node is going to be the last node, so If the Linked List is empty, then make the new
Else traverse till the last node
Change the next of last node
Make last node as previous of new node

Add a Node in the End Steps involved -

Check if the next_node is NULL or not. If it’s NULL, return from the function because any new node can not be added before a NULL
Allocate memory for the new node, let it be called new_node
Set the value of data to the new node
Set the previous pointer of this new_node as the previous node of the next_node, new_node->prev = next_node->prev
Set the previous pointer of the next_node as the new_node.
Set the next pointer of this new_node as the next_node.
If the previous node of the new_node is not NULL, then set the next pointer of this previous node as new_node.
Else, if the prev of new_node is NULL, it will be the new head node.

Code to Demonstrate the Insertion Operations

CPP

#include <bits/stdc++.h>
using namespace std;
class Node // Create a doubly linked list 
{
    public:
    int data; // value of a node 
    Node* next;// next pointer 
    Node* prev;// previous pointer of node 
};


void push(Node** head_ref, int new_data) // insert a node in front of list 
{
    /* 1. allocate node
    Node* new_node = new Node();

    /* 2. put in the data */
    new_node->data = new_data;

    /* 3. Make next of new node as head
    and previous as NULL */
    new_node->next = (*head_ref);
    new_node->prev = NULL;

    /* 4. change prev of head node to new node */
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;

    /* 5. move the head to point to the new node */
    (*head_ref) = new_node;
}


void insertAfter(Node* prev_node, int new_data) // function to insert after a node 
{
    /*1. check if the given prev_node is NULL */
    if (prev_node == NULL)
    {
        cout<<"the given previous node cannot be NULL";
        return;
    }

    /* 2. allocate new node */
    Node* new_node = new Node();

    /* 3. put in the data */
    new_node->data = new_data;

    /* 4. Make next of new node as next of prev_node */
    new_node->next = prev_node->next;

    /* 5. Make the next of prev_node as new_node */
    prev_node->next = new_node;

    /* 6. Make prev_node as previous of new_node */
    new_node->prev = prev_node;

    /* 7. Change previous of new_node's next node */
    if (new_node->next != NULL)
        new_node->next->prev = new_node;
}


void append(Node** head_ref, int new_data) // function to add a new node at the end 
{
    /* 1. allocate node */
    Node* new_node = new Node();

    Node* last = *head_ref; /* used in step 5*/

    /* 2. put in the data */
    new_node->data = new_data;

    /* 3. This new node is going to be the last node, so
        make next of it as NULL*/
    new_node->next = NULL;

    /* 4. If the Linked List is empty, then make the new
        node as head */
    if (*head_ref == NULL)
    {
        new_node->prev = NULL;
        *head_ref = new_node;
        return;
    }

    /* 5. Else traverse till the last node */
    while (last->next != NULL)
        last = last->next;

    /* 6. Change the next of last node */
    last->next = new_node;

    /* 7. Make last node as previous of new node */
    new_node->prev = last;

    return;
}


void printList(Node* node)// function to print the doubly linked list 
{
    Node* last;
    cout<<"\nTraversal in forward direction \n";
    while (node != NULL)
    {
        cout<<" "<<node->data<<" ";
        last = node;
        node = node->next;
    }

    cout<<"\nTraversal in reverse direction \n";
    while (last != NULL) // traverse the list in reverse direction 
    {
        cout<<" "<<last->data<<" ";
        last = last->prev;
    }
}

int main() // Main function
{

    Node* head = NULL; // currently the list is empty 
    append(&head, 6); // insert 6 in the beginning 
    push(&head, 7); // insert 7 before 6 
    push(&head, 1);

Output:

Created Doubly linked list is: 
Traversal in forward direction 
 1  7  8  6  4 
Traversal in reverse direction 
 4  6  8  7  1

Deletion in Doubly Linked List The deletion of nodes can be divided into three categories - head, middle and last node deletion.

Steps to be performed for deletion

Let the node be Deleted be D.
If the node to be Deleted is the head node, then change the head pointer to the next current head.
Set next to previous to D, if previous to D exists.
Set prev of next to D, if next to D exists.

CPP Code to Perform Deletion Operation

#include <bits/stdc++.h>
using namespace std;
class Node // create a doubly linked list 
{
    public:
    int data; // value of the node 
    Node* next; // next pointer of the node 
    Node* prev; // previous pointer to the node 
};

void deleteNode(Node** head_ref, Node* del) // function to delete a node in DLL
{
    /* base case */
    if (*head_ref == NULL || del == NULL)
        return;

        if (*head_ref == del)
        *head_ref = del->next;

    if (del->next != NULL)
        del->next->prev = del->prev;

    if (del->prev != NULL)
        del->prev->next = del->next;

    /* Finally, free the memory occupied by del*/
    free(del);
    return;
}

void push(Node** head_ref, int new_data) // function to insert data into the DLL
{

    Node* new_node = new Node();

    /* put in the data */
    new_node->data = new_data;

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

    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;

    (*head_ref) = new_node;
}

void printList(Node* node) // function to print the content of the DLL
{
    while (node != NULL) // iterate till the end of DLL 
    {
        cout << node->data << " "; // print node data 
        node = node->next;
    }
}

int main() // main function 
{
    Node* head = NULL; // currently head is NULL 

   // DLL created =  10<->8<->4<->2 
    push(&head, 2);
    push(&head, 4);
    push(&head, 8);
    push(&head, 10);

    cout << "Original Doubly Linked list ";
    printList(head); // print original DLL

    /* delete nodes from the doubly linked list */
    deleteNode(&head, head);

Output:

Original Doubly Linked list 10 8 4 2 
Modified Doubly Linked list 8

Advantages of a Doubly Linked List

As we have seen the operations of a DLL, below are the advantages -

It becomes easier to iterate in both directions.
Deletion of a particular node is easy as we have access to the previous node.
Performing a reverse operation is easy.
A DLL can grow and shrink dynamically.
It is beneficial in implementing other data structures like binary trees, hash tables, stacks, etc.
It provides the flexibility to perform undo/redo operations.
It can also be used in gaming like playing deck of cards.
Traversing a DLL in a bidirectional manner is easy as compared to singly linked lists.
In the operating system, a thread scheduler manages a doubly linked list of all the processes.
The concept of DLL can be applied in forward and backward navigation areas.

Disadvantages of a Doubly Linked List

It stores an extra pointer to store the address of previously linked nodes. Hence, it consumes more memory when compared to a singly linked list.
Due to extra pointers more time is required in handling the overhead.
We can't randomly access elements in a doubly linked list.

Conclusion

A doubly linked list has three parts: the data, next and a previous pointer. We can perform various operations on a doubly linked list like add a node in front, add a node in last, delete a node in front, delete a node in the lost, insert a node after a given node, insert a node before a given node, etc.

The main benefit of a doubly linked list is its iteration in backward and forward direction. Also a DLL can shrink dynamically. Doubly linked list examples are - a music playlist in which songs can be changed by moving backward and forward, the undo and redo functionality in a word file, etc.

Reference: Scaler Topics

What is RDBMS ?

Pranjali Nandan — Thu, 17 Feb 2022 10:42:13 +0000

RDBMS stands for Relational Database Management System. Also called RDB (Relational Database), it is a database that stores data in tables (rows and columns) so that it can be used to form relations with other tables. The only difference between relational databases and simple databases is that we can easily create relationships with other tables using RDB. Most databases used these days are relational databases.
We can perform any type of operation on RDB, such as updating, deleting, viewing, and so on. Most relational databases use SQL as a language to access the database. SQL (Structured Query Language) is a programming language that is used to communicate with databases. It helps us create, update, or delete data in relational databases. The syntax of SQL is also very simple, making it easy to learn.

Let’s make RDB clear with the help of a simple example. Let's assume we have two tables; one is a student table in which we have student name and student roll number, and the other table is an info table, which has roll number and total marks. So, we can make a relationship between these two tables and find out the total marks of individual students. Note that we have a common column (student roll number) in these two tables. Some of the examples of relational database management systems are mentioned below:-

MySQL
Oracle DB
PostgreSQL
SQLite
SQL Server

RDBMS Operation

A relational database management system works in tables; it stores data in the form of tables. There can be any number of tables that contain rows and tables. Every table in database has unique primary key. As we know, tables have rows and columns, so let’s understand the role of these rows and columns. So, a row records the data of an individual entity, and a column holds the data for a specific field. Using SQL, we can run a query to show some specific results. SQL has a term called SQL Constraints. They are used for some rules for data before it enters the table. Let's explore some constraints given below:-

NOT NULL - It ensures that a column doesn’t have any empty values or NULL values.
UNIQUE - It ensures that no two values in a given column are the same.
PRIMARY KEY - A primary key is a group of columns in a table that uniquely identify the row.
CHECK – This function ensures that columns adhere to any given condition.

Why RDBMS?

The relational database management system is very safe. If for any reason, our programme crashes, our data will remain safe. There are many security layers, so the data will remain safe.
In relational databases, accessing the data is easy and if we want to perform any action like deleting, updating, etc., such a type of action is easy to implement.
A relational database can manage large amounts of data and this data is stored in the form of rows and columns in a table.
Using a foreign key, we can link two or more tables and then work on them according to our requirements.
We can also give permission to multiple users so that they can work individually according to their needs.
Management of relational databases is also very clean and effective as data is stored in the form of rows and columns.

RDBMS Advantages

Below are some of the advantages of relational databases:

Relational databases are very flexible in nature. Let's understand this by taking an example. Assume that we have an employee table, and if we need to update any information about an employee, rather than updating it in each file, we simply update it in the main file, and RDBMS automatically updates this information in every file of the database. By doing this, we can save a lot of time.
Relational databases can be accessed at any time, and they are also very easy to use. Relational databases allow database admins to control their events, like maintaining data, updating data, etc. Backing up data is also simple with the help of RDBMS and some automation tools.
The database admin of a relational database has control over the database and can give specific access to the required user. It cannot give all access to all users. Access is given according to the user’s need.
As we know, relational databases use rows and columns to store their data, so tables are very comfortable for users to understand. Also, writing queries for RDBMS is easy.

RDBMS Disadvantages

A relational database has many advantages, but it also comes with some disadvantages. For example, to implement a relational database, we need some special software, so some special software needs to be purchased. This results in an extra cost. Also, to setup a relational database, we have to write millions of lines of code into RDBMS tables. For that, we need some extra programmers. Also, while doing this, we must take care that our data doesn’t fall into the wrong hands. Also, sometimes combining multiple tables can become more complicated in some cases.

Indexing in RDBMS

To get faster access to data, indexes are used. Suppose you have an employee table with 10 employees. If we sort the data in increasing order, we can easily find out the nth salary using indexes.

DBMS vs. RDBMS

Now let's explore the key difference between DBMS and Relational DBMS as given below:

In DBMS, only one user is accepted at a time, but in the case of relational databases, multiple users are allowed at a time.
Relational databases necessitate greater investment in software and hardware than DBMS.
As we know, relational databases make relational between multiple tables, so they can manage large amounts of data easily, but DBMS only manage a small amount of data as compared to RDBMS.
A relational database stores its data in the form of tables (using rows and columns), while a DBMS stores its data in hierarchical form.
Relational databases support distributed databases (it is a type of database that is present on multiple sites, i.e., on multiple computers or over a network of computers; it is not limited to only one user), while DBMS doesn’t support distributed databases.
Relational databases can be normalized, but in the case of DBMS, it is difficult to normalize them.
Relational databases follow ACID properties (Atomicity, Consistency, Isolation, Durability) while storing the data, while the DBMS doesn’t follow ACID properties.

For a better understanding of difference between DBMS and RDBMS, refer to Scaler Topics

Author - Arnav Bhardwaj

How to Prevent Deadlock in DBMS?

Pranjali Nandan — Thu, 10 Feb 2022 11:39:48 +0000

Before proceeding directly to the prevention of deadlock in DBMS, let's understand what deadlock is. Deadlock is a condition where one or more processes are waiting for a resource indefinitely, where this resource is acquired by another process.
For greater clarity, consider the following scenario: we have two resources, say R1 and R2, and we can have two processes, say P1 and P2. P1 has R2 resource, and P2 has R1 resource; therefore, P1 requires both R1 and R2 resources to complete its process, and P2 requires both R1 and R2 resources to complete its process. P1 process now holds R2 resource and waits indefinitely for R1 resource, similar to P2 process. So, these conditions are deadlock conditions where some processes are blocked because they hold some resources and are waiting for other processes that were held by other processes, so this waiting will never end until resolved.

So, we need to understand the conditions that can lead to a deadlock. So, according to Coffman, there are four conditions where deadlock can occur, which are mentioned below:

Mutual exclusion
Circular waiting situation
Condition of hold and wait
There is no preemption condition.

Prevention of Deadlock

When any transaction starts to execute, the database management system will inspect all its operations so that a deadlock condition will not occur. If it finds in any condition that a deadlock condition can occur, then that transaction is not allowed to be executed.
We can avoid deadlock by avoiding one or more of the four Coffman's conditions.

Removing mutual exclusion, i.e., all the resources must be shareable.
Removing the hold and wait condition
Preemption of resources
Avoid the condition of circular waiting.

Methods for Preventing Deadlocks

Deadlock prevention is very suitable for large databases. If all the resources were arranged in such a manner that the process did not need to wait for resources, then the deadlock could be prevented. The database management system analyses the situation of operations of a transaction and if there is any chance of deadlock occurring, then that transaction will never be executed. Let’s look at some methods of prevention:

Wait-Die
Wound-Wait

Wait-Die

The Wait-Die scheme is a non-preemptive technique to use for preventing deadlock. Suppose we have two transactions, T1 and T2.
When T1 requests data currently held by transaction T2, in this case, T1 is allowed to wait if and only if its timestamp is smaller than the timestamp of T2.
(In simple words, it means T1 is older than T2). If not, then T1 is going to die or be killed.
That is why this scheme is known as the "WAIT-DIE SCHEME."

In this technique, two possibilities may occur:

a) T1 timestamp < T2 timestamp = It means if T1 is older than T2, then T1 is allowed to wait until the resource is not provided to T1.
b) T1 timestamp > T2 timestamp = It means if T1 is younger than T2, then T1 is going to die. It is not allowed to wait.

So more precisely, we can say that if the transaction is older than the other transaction, then it has the right to wait, otherwise it is going to die.

Example
Let's consider this example. It will clear up all your doubts and the above theory in a simple manner.

Suppose we have a transaction T1, T2, T3 having a timestamp of 2, 4, 6, respectively.

If T1 requests a resource that is held by T2, then T1 has the right to wait. What's the deal? because the T1 timestamp is earlier than the T2 timestamp
If T3 requests a resource that is held by T2, then T3 is going to die. What's the deal? because the T3 timestamp is more recent than the T2 timestamp

I hope it is clear to all of you now.

Wound-Wait

The Wound-Wait scheme is a preemtive technique used in the prevention of deadlock in DBMS. It is the total opposite of the wait-die scheme.
Suppose we have two transactions, T1 and T2. If T1 requests data or a resource which is held by T2, then T1 is allowed to wait if and only if T1's timestamp is greater than T2. Otherwise, in this case, T2 is going to die instead of T1.
That means T2 is wounded by T1. That is why this scheme is known as the "Wound-wait" scheme in DBMS.

In this technique, 2 possibilities may occur, like in the wait-die scheme:
a) T1 timestamp < T2 timestamp = In this case, T2 is going to be killed by T1 and it will restart at a random delay but with the same timestamp.
b) T1 timestamp > T2 timestamp =It means if T1 is older than T2, then T1 is allowed to wait until the resource is not provided to T1.

Example
Let's consider this example. It will clear up all your doubts and the above theory.
Suppose we have a transaction T1, T2, T3 having a timestamp of 2, 4, 6, respectively.

If T1 requests a resource that is held by T2, then T1 is going to force T2 and it will wound T2.
If T3 requests a resource that is held by T2, then T3 has the right to wait.

For a better understanding of deadlocks, Read more about it on Scaler Topics

Virtual base class in c++

Amod Nazirkar — Fri, 04 Feb 2022 06:07:55 +0000

Introduction

Let’s start with an example of the hybrid inheritance, in which there is a base class, let's say A, and it has two derived classes, let's say class B and class C. Now as there is hybrid inheritance so there may be another class, let’s say D which inherits properties of both class B and class C.

As a child class can access the member functions or properties of the parent class or even the properties of the parent class’s parents which implies D can access the member functions of its parents B and C, also there parent A. But the problem is A is the parent of both B and C so there are two ways for objects of class D to access the properties of A either via class B or via class C. When a function call is made from object of class D to the function of class A then the compiler will get confused about the path to approach class A this leads to an error.

Let’s see the code of above defined scenario

#include <bits/stdc++.h>
using namespace std;
// defining class A
class A 
{
public:
    void hello_A()
    {
        cout<<"This is class A"<<endl;
    }
};

// defining class B
// class B inherits from class A
class B : public A
{
public:
    void hello_B()
    {
        cout<<"This is class B"<<endl;
    }
};

// defining class C
// class C inherits from class A
class C : public A
{
public:
    void hello_C()
    {
        cout<<"This is class C"<<endl;
    }
};

// defining class D
// class D inherits from both class B and C
class D : public B, public C
{
public:
    void hello_D()
    {
        cout<<"This is class D"<<endl;
    }
};

int main()
{
    // creating the object of class D
    D obj; 

    // calling the function of the class A using object of class D
    obj.hello_A();
}

Error

HelloWorld.cpp: In function 'int main()':
HelloWorld.cpp:52:9: error: request for member 'hello_A' is ambiguous
     obj.hello_A();
         ^~~~~~~
HelloWorld.cpp:7:10: note: candidates are: void A::hello_A()
     void hello_A()
          ^~~~~~~

We get an ambiguous error here as the compiler has no idea which path it has to choose to reach class A. This problem is known as diamond problem, when there is diamond-like shape in our hybrid inheritance then there will be ambiguous error and to remove this error we define the parent class as the virtual class with the help of virtual keyword which means virtual base class is a way of defining virtual inheritance to prevent the multiple instances of a class.

How to declare virtual base class in C++?

Virtual base class is declared with the help of the virtual keyword.

Syntax

Syntax 1: Adding virtual keyword before public keyword

class child_class : virtual public parent_class 
{
};

Syntax 2: Adding virtual keyword after public keyword

class chid_class : public virtual parent_class
{
};

In the above syntax we defined a child class which inherits from the parent class public members and to make it virtual base class we just added virtual keyword by two ways either before public keyword or before access specifier or we can define it after access specifier as we have done in second syntax.

Let’s implement our above code by declaring class A as virtual parent class

#include <bits/stdc++.h>
using namespace std;
// defining class A
class A 
{
public:
    void hello_A()
    {
        cout<<"This is class A"<<endl;
    }
};

// defining class B
// class B inherits from class A
class B : virtual public A
{
public:
    void hello_B()
    {
        cout<<"This is class B"<<endl;
    }
};

// defining class C
// class C inherits from class A
class C : public virtual  A
{
public:
    void hello_C()
    {
        cout<<"This is class C"<<endl;
    }
};

// defining class D
// class D inherits from both class B and C
class D : public B, public C
{
public:
    void hello_D()
    {
        cout<<"This is class D"<<endl;
    }
};

int main()
{
    // creating the object of class D
    D obj; 

    // calling the function of the class A using object of class D
    obj.hello_A();
}

Output:

This is class A

We rewrite the code explained in the above section, only change is we define the base class (class A) as a virtual class using the virtual keyword while inheriting it in class B and class C that makes our code work properly.

Conclusion

Virtual base class is a way of defining virtual inheritance to prevent the multiple instances of a class.
When there is diamond-like shape in hybrid-inheritance, then there is a chance to get errors which can be prevented by declaring base class as virtual.
To declare a virtual class, a virtual keyword is used while inheriting it in child class.
To discover the virtual-base-class topic covered in detail please refer to this Scaler link.

Program to Implement Insertion Sort in Data Structure

Bikash Daga — Wed, 05 Jan 2022 13:33:12 +0000

Sorting is a technique to arrange the data in ascending, descending order or lexicographical order. Using an efficient sorting algorithm can improve the time complexity of the code.

The insertion sort is a famous and easy problem that is asked in various product based companies and semester exams. In this article, you will learn about insertion sort with real life examples with code demonstration.

Definition of insertion sort

Insertion sort is defined as a sorting algorithm that takes the ith element and places it in the correct position in the array. The insertion sort algorithm performs the same operation on the whole array by picking the element one by one and storing it in the right place.

One real world example of insertion sort is derived from playing cards in school. When a pack of cards is taken in hand, we take one card and place it in the correct position behind the large numbers.

Another example of insertion sort algorithm is placing suits at a garment store.

In the cupboard, the suits are placed in sorted order and the lower sized suits are placed below all the higher ones.

Advantages of insertion sort algorithm

1. Simple - The insertion sort code is easier to understand and implement.

2. Efficient for smaller data set - The algorithm sounds perfect for small sized arrays as we have not to search the exact place for the element.

3. Adaptive - The algorithm works appropriate for the sorted data sets.

Insertion sort example

Let us try to understand this algorithm working by taking the following array as an example -

Arr[] = [9, 6, 7, 3, 4]

- Operating the element arr[0]

We mark the section blue as sorted and the orange as unsorted, So we operare 9 and since this is the first element in the left array it remains sorted.

Arr[] = [9, 6, 7, 3, 4]

- Operating the element arr[1]

Now we take 6 and mark it as blue. So the left array has 2 elements 9 and 6. Since 6 is less than 9 we interchange to sort the left array.

Arr[] = [6, 9, 7, 3, 4]

- Operating the element arr[2]

Now we take 7 and mark it as blue. So the left array has 3 elements 9, 6, 7. Since 7 is less than 9 and greater than 6 we interchange to sort the left array.

Arr[] = [ 6,7, 9, 3, 4]

- Operating the element arr[3]

Now we take 3 and mark it as blue. So the left array has 4 elements 9, 6, 7, 3. Since 3 is the smallest we place it in the beginning.

Arr[] = [3, 6, 7, 9, 4]

- Operating the element arr[4]

Now we take the last element. 4 comes after 3 so we place it in second position.

Arr[] = [3, 4, 6, 7, 9]

For a better understanding in a picture mode you can visit

Pseudocode for insertion sort algorithm

insertionSortAlgorithm(array arr)
    mark First element as sorted and it comes in left array
    for each unsorted element A
        Store the element A
        for j <- lastSortedIndex down to 0
            if current element j > A
                move sorted element to the right by 1
        break loop and insert A here
end insertionSortAlgorithm

Explanation

Line 2: The first element is single so it is already in sorted format.
Line 3: Run a loop from start to end to operate each element in the array.
Line 4: Extract the element at position i i.e. array[i]. Let it be called A.
Line 5: To compare A with its right elements by running the loop j from i-1 to 0
Line 6, 7: Compare A with the left element, if A is lesser, then move arr[j] to right by 1.
Line 8: After finding the appropriate index for A insert into that position.

C code of insertion sort algorithm

#include <stdio.h>
// Function for insertion sort
void Insertion_Sort(int array[], int size)
{
    int temp, j, i;

    for(i = 1; i < size; i++)
    {
        temp = array[i];
        j = i - 1;

        // Do swapping
        while(j >= 0 && array[j] > temp)
        {
            array[j + 1] = array[j];
            j--;
        }

        array[j + 1] = temp;
    }
}

// Function to print elements of array
void Print_Array(int array[], int size)
{
    for(int i = 0; i < size; i++)
        printf("%d\t",array[i]);

    printf("\n");
}

// Driver Function
int main()
{
    int num;
    scanf("%d", &num);
    int array[num];
    for (int i = 0; i < num; i++) {
        scanf("%d", &array[i]);
    }
    Insertion_Sort(array, num);
    Print_Array(array, num);
    return 0;
}

Input:
num = 6
array = [1, 6, 3, 3, 5, 2]
Output:
[1, 2, 3, 3, 5, 6]

CPP Code for Insertion Sort Algorithm

#include <iostream>
using namespace std;

// Function for insertion sort
void Insertion_Sort(int array[], int size)
{
    int temp, j;

    for(int i = 1; i < size; i++)
    {
        temp = array[i];
        j = i - 1;

        // Do swapping
        while(j >= 0 && array[j] > temp)
        {
            array[j + 1] = array[j];
            j--;
        }

        array[j + 1] = temp;
    }
}

// Function to print elements of array
void Print_Array(int array[], int size)
{
    for(int i = 0; i < size; i++)
        cout << array[i] << " ";

    cout << endl;
}

// Driver Function
int main()
{
    int num;
    cin >> num;
    int array[num];
    for (int i = 0; i < num; i++) {
        cin >> array[i];
    }
    Insertion_Sort(array, num);
    Print_Array(array, num);
    return 0;
}

Input:
num = 6
array = [1, 6, 3, 3, 5, 2]
Output:
[1, 2, 3, 3, 5, 6]

Java Code for Insertion Sort Algorithm

import java.util.Scanner;

class Insertion_Sort_algo
{
    // function for insertion sort
    public static void InsertionSort(int[] array, int size)
    {
        int temp, j;

        for(int i = 1; i < size; i++)
        {
            temp = array[i];
            j = i - 1;

            // Do swapping
            while(j >= 0 && array[j] > temp)
            {
                array[j + 1] = array[j];
                j--;
            }

            array[j + 1] = temp;
        }
    }

    // function to print array
    public static void Print_Array(int[] array, int size)
    {
        for(int i = 0; i < size; i++)
            System.out.print(array[i] + " ");

        System.out.println();
    }

    public static void main(String[] args)
    {
        int num;
        Scanner s = new Scanner(System.in);
        num = s.nextInt();
        int array[] = new int[num];
        for (int i = 0; i < num; i++) {
            array[i] = s.nextInt();
        }
        InsertionSort(array, num);
        Print_Array(array, num);
    }
}

Input:
num = 6
array = [1, 6, 3, 3, 5, 2]
Output:
[1, 2, 3, 3, 5, 6]

Time Complexity of Insertion Sort Algorithm

From the code we have seen that insertion sort performs two operations - iterating in the right array and interchanging with the left one. This combined operation contributes to the time complexity of the algorithm.

- Best case

In best case the time complexity of insertion sort algorithm is O(N). This is the case when the whole array is already sorted. It becomes N case time complexity as the inner loop never gets executed. The outer loop will check and scan for each element which makes the time complexity to O(N).

- Worst case

The worst case time complexity is O(N*N). This is the case when the whole array is unsorted. In this case the inner loop will be executed till the end of the right array in order to place the arr[i] in the correct position.

- Average case

The average case time complexity is O(N*N). In this case, elements are mixed up neither fully sorted nor fully unsorted.

Space Complexity of Insertion Sort Algorithm

The space complexity of insertion sort algorithm is constant as it takes only one or two variables in the entire array. So, the space complexity of insertion sort algorithm is O(1).

Read more about Insertion Sort on Scaler Topics.

Happy Learning!

DEV Community: Scaler Topics

What is Foreign Key in DBMS?

Foreign Key Query in MySQL

Why do we need Foreign Key?

How does Foreign Key maintain Referential Integrity?

Difference Between and Tag in HTML

Introduction

Difference between br and br/ Tag

Browser Compatibility

Desktop Browsers

Conclusion

Advantages of Doubly Linked List in Data Structure

Introduction

What is a Doubly Linked List?

Representation of a Doubly Linked List in Data Structure

C++ Code

C Code

Operations on a Doubly Linked List

Code to Demonstrate the Insertion Operations

CPP

CPP Code to Perform Deletion Operation

Advantages of a Doubly Linked List

Disadvantages of a Doubly Linked List

Conclusion

What is RDBMS ?

RDBMS Operation

Why RDBMS?

RDBMS Advantages

RDBMS Disadvantages

Indexing in RDBMS

DBMS vs. RDBMS

How to Prevent Deadlock in DBMS?

Prevention of Deadlock

Methods for Preventing Deadlocks

Wait-Die

Wound-Wait

Virtual base class in c++

Introduction

How to declare virtual base class in C++?

Conclusion

Program to Implement Insertion Sort in Data Structure

Definition of insertion sort

Advantages of insertion sort algorithm

Insertion sort example

Pseudocode for insertion sort algorithm

C code of insertion sort algorithm

CPP Code for Insertion Sort Algorithm

Java Code for Insertion Sort Algorithm

Time Complexity of Insertion Sort Algorithm

Space Complexity of Insertion Sort Algorithm

Difference Between
and
Tag in HTML