Data Structures in C++

As we know that the C++ programming language offers several exciting and useful features and functionalities to its users. And it also does support object-oriented programming. With this technique, you can perform some major methods such as Encapsulation, Abstraction, Inheritance, Polymorphism etc. In C++, data structures are a useful and inescapable part of programming. With the help of data structures, we perform operations on data such as data representation, storage, organization and many more.

What are Data Structures

With the help of data structures, you can organize data in a particular way so that it can be used effectively. There are several ways to organize the data in memory.

Let me tell you that it is not a programming language, it is a set of algorithms which one can use to structure data into memory in any programming language.

Below, we stored a list of items using the array data structure.

Data Types C++

It is just a group of similar data under a single name. Data types that are similar share similar characteristics and behave in a similar way.

For example, if you want to store the address of a person or house then you should use ‘string’ data type.

Data types are categorized into two broad categories:-

1. Primitive Data Type:- These are pre-defined data types. It is also known as fundamental data types. Example:- int, float, double, char, string etc.

2. Non-Primitive Data Type:- These are user-defined data types. Example:- array, structures, unions, structures, linked lists etc.

Types of Data Structures in C++

In C++, data structures are further categorized into 3 types.

1. Simple Data Structures

These data structures are built from primitive data types like int, float, double, char etc.

Example:- An array is a data structure that holds the same data type and the structure is also a data type that holds different data types.

2. Compound Data Structures

You can also build compound data structures by combining simple data structures. Compound data structures are classified into:-

a. Linear Data Structure:– If the elements of a data structure are ordered in sequence then it is a linear data structure. Example:- stacks, queues and linked lists.

b. Non-Linear Data Structure:– These data structures are not linear. These are multilevel data structures. Example:- trees, graphs etc.

3. Static and Dynamic Data Structures

Static data structures are constant in size and structure. It is associated with specific memory locations fixed at compilation time.

You can expand or contract a data structure according to your needs during the execution of the program. And these types of data structures are known as Dynamic Data Structure.

Operations on Data Structures

Below are the basic operations which you can perform on the data structures in C++:-

• Insertion: Adding a new data element into the data structure.
• Deletion: This operation is about deleting or removing an existing data element from the data structure.
• Traversal: This operation is about processing and displaying all the data elements in the data structure.
• Searching: Searching a specific data element in the data structure.
• Sorting: This operation is about arranging all the data elements in the data structure either in ascending or descending order.
• Merging: This operation is about combining similar data elements from two or more data structures.

C++ Arrays

Arrays are simply a collection of similar data types stored at contiguous memory locations. It can store primitive types of data like int, char, float, double etc. With the help of the arrays, a programmer can access the elements very easily.

Suppose, you want to store marks of 20 students then you might try to declare 20 variables like student1_marks, student2_marks etc. But what if i tell you that you can do all those with a single variable named array. With the help of a few lines of code, you can access those elements.

0                                                     1                                               2                                                3                                  4

   Array of size 5

Syntax for declaring an array:-

dataType array_name[arraySize];

So, if you want to access the second element of the above array, then you have to do:-

cout<<array[1]

Example:-

#include<iostream>
using namespace std;
int main()
{
int numbers[3] = {2, 3, 4};
cout<<"First number is: "<<numbers[0]<<endl;
cout<<"Last number is: "<<numbers[2];
}

Output:-

C++ Linked List

A linked list can be defined as a collection of connected nodes. It is a linear data structure. A linked list contains two parts such as:-

• Data Part:- Contains the data of the user.
• Pointer Part:- It points to the next member of the linked list.

In the above image, Head contains the address of the first node. And the last node in the linked list points to NULL.
Nodes are stored at different locations.

There are three types of linked list such as Singly Linked List, Doubly Linked List and Circular Linked List.

Below, we have created a singly linked list of three members.

// Node Initializing!
struct node *HEAD;
struct node *ONE = NULL;
struct node *TWO = NULL;
struct node *THREE = NULL;

// Allocating memory!
ONE = malloc(sizeof(struct node));
TWO = malloc(sizeof(struct node));
THREE = malloc(sizeof(struct node));

// Assigning the values of data!
ONE->data = 23;
TWO->data = 34;
THREE->data = 90;

// Connecting nodes with each other!
ONE->next = TWO;
TWO->next = THREE;
THREE->next = NULL;

// Saving the address of first node
HEAD = ONE;

Stack in C++

Stack is known as a linear data structure. It follows the Last-In-First-Out rule. So, if you push something to the stack then the last value which you pushed, will be the first to pop out. The insertion and deletion operation on the stack will only take place from one end which is the top of the stack.

In 2 ways, you can implement a stack in C++:-

1. Statically:- You can implement a stack using an array. It allows static memory allocation of its data elements. In this, the stack inherits all the features of the array.

2. Dynamically:- You can also implement a stack using a linked list. It allows dynamic memory allocation of its data elements. In this, the stack takes over the characteristics of the linked list.

Queue in C++

Queue is known as a linear data structure. It follows the First-In-First-Out rule. So, if you push something to the stack then the first value of the stack will pop out. In the queue, the insertion operation is possible from the rear end(back) and the deletion is from the front.

In 2 ways, you can implement the queue:-

1. Statically:- You can implement a queue using an array. It allows static memory allocation of its data elements. In this, the queue inherits all the features of the array.

2. Dynamically:- You can also implement a queue using a linked list. It allows dynamic memory allocation of its data elements. In this, the queue takes over the characteristics of the linked list.

C++ Trees

It is a bit of a complex and complicated data structure.

A tree is known as a finite and non-empty set of elements in mathematical terms. Trees are hierarchical data structures. A tree includes multiple nodes. This data structure follows the parent-child relationship. It is not a linear data structure like array, structure, linked lists etc. It is a non-linear data structure.

C++ Structure

The structure is a user-defined data type. It works similarly like arrays. Structures help you in grouping items of different types in a single group. It stores the collection of different data types. Each element of structure is a member.

Defining a structure in C++:-

Before creating variables of structure, you have to define it first. You can use the struct keyword to define structures.

Syntax:-

struct name_of_the_structure 
{
    data_type member1;
    data_type member2;
    ...
    data_type memberN;
};

Example:-

struct bill
{
   float amount;
   int id;
   char address[100];
};

In the above example, we have defined a structure named bill. And the members of this structure are amount, id and address.

Accessing members of structures in C++:-

Before using the structure variables, you will have to access the members of the structure. There are 2 ways to access the member of the structure:-

• Use . operator
• Use -> operator (structure pointer operator)

Suppose, you want to access the amount member of the p1 variable from the above example then you can use . operator like below:-

p1.amount;

Example:- Accessing members of structures

#include <iostream>
using namespace std;
struct Tech{
  int a = 0;
  int b = 1;
};
int main()
{
  struct Tech t1;
  cout << "a: " << t1.a << " and b: " << t1.b<<endl;
  t1.a = 5;
  t1.b = 10;
  cout << "a: " << t1.a << " and b: " << t1.b;
  return 0;
}

Output:-

Structure as function arguments

You can also pass a function to structures. It helps you in making your coding better and efficient.

Example:- passing function to structures

#include <iostream>
#include <string.h>
using namespace std;
struct info {
   char student_name[50];
   char favorite_subject[20];
   int id;
};
void display( struct info each_student );
int main() {
   struct info s1;  	 
   strcpy( s1.student_name, "Tom Sawer");
   strcpy( s1.favorite_subject, "English");
   s1.id = 20;
// printing first student details!
   display(s1);
   return 0;
}

void display( struct info each_student ) {
   cout<<"Name of first student: "<< each_student.student_name<<endl;
   cout<<"Favourite subject of first student: "<<each_student.favorite_subject<<endl;
   cout<<"ID of first student: "<<each_student.id<<endl;
}

Output:-

Summary

In this tutorial, we discussed the data structures and data types in C++. We also discussed the different types of data structures such as simple, compound, static and dynamic data structures. Then we talked over the arrays, stack and queues, linked list, and trees in this tutorial.