Free C++ course with real-time projects Start Now!!
C++ Data structures is a vast and inevitable part of programming. Just like we human beings are dependent on cells, the smallest unit of life for various types of cellular activities. The entire C++ program is dependent on the basic unit of programming called “data”. The data operations we perform include data representation, storage, organization and many more in a meaningful manner is performed by the implementation of data structures. In this article, our aim is to inculcate the core concepts of data structures to beginners passionate about C++.
1. C++ Data Types
A data type is nothing but a group of similar data under a single name. Similar data types share similar characteristics and behave in a similar fashion, like occupying the same amount of computer memory, being used to achieve the same purpose.
For example, the address of a house contains alphabets as well as numbers. Therefore, it is categorized under the data type called “string”.
We can categorize data types into two broad categories:
- Primitive data type – These data types are also referred to as fundamental data types. These are pre-defined data types and convey a specific meaning to the C++ compiler. For example int, float, char, string, double, etc.
- Non-primitive data type – These data types are composed of primitive data types. These are also referred to as user-defined data types as they are not pre-defined by the C++ compiler. For example arrays, structures, unions, class, linked lists, enumeration, etc.
2. Different Types of Data Structures in C++
After understanding the classification of data types in C++, let us carry on our discussion on data structures. The use of C++ data structures gives the programmer the provision to combine the various data types in a group as well as process this group treated as a single unit thereby making things convenient and easily comprehensible.
Data structures in C++ are broadly classified into 3 different types which we will discuss in detail in this tutorial.
2.1 Simple Data Structures
These types of data structures in C++ are generally built from primitive data types like int, float, double, string, char. For instance, an array is a data structure of similar data type, a structure is also a data structure with the allowance to hold different data types and a class that can hold data elements for various types and member functions as well with any return type.
2.2 Compound Data Structures
The user can build these types of data structures by combining simple data structures. It is further classified into two types:
- Linear data structure – A data structure is said to be linear only if it has its elements formed in an ordered sequence. Some of the popular linear data structures that we widely use in C++ are stacks, queues, and linked lists.
- Non-linear data structure – Non-linear data structures are basically multilevel data structures. Some of the popular non-linear data structures are trees and graphs.
2.3 Static and Dynamic Data Structures
Technology is evolving rapidly!
Stay updated with DataFlair on WhatsApp!!
These data structures that have a constant size and structure associated with some specific memory locations fixed at the compilation time are referred to as static data structures. For example, arrays.
On the other hand, data structures that expand or contract as and when required according to the convenience of the programmer during the execution of the program are referred to as dynamic data structures. For example, pointers.
3. Operations Associated with Data Structures in C++
The basic operations that we can perform on data structures are as follows:
- Insertion: This operation refers to the addition of a new data element into the data structure.
- Deletion: Delete or remove an existing data element from the data structure.
- Traversal: Process and display all the data elements in the data structure.
- Searching: Search for a specific data element in the data structure.
- Sorting: Arrange all the data elements in the data structure either in ascending or descending order or any other logically sequential order.
- Merging: Combine similar data elements from two or more data structures, thus resulting in a newly formed data structure.
It’s the right time to uncover the concept of Arrays in C/C++
4. C++ Arrays
Now, that we have understood what are data types, data structures, and its types and the operations associated with it, let us further carry on our discussion by trying to get an idea of some of the most popular data structures used in C++.
Arrays are one of the most important and fundamental data structures available in C++.
In programming terminology, an array is a group of items that we can identify as a similar type due to similarities in properties such as they essentially have the same data type.
In simple words, an array is a series of elements of the same type placed in contiguous memory locations that we can access with the help of their array index and the unique identifier name of the array.
This is how elements are sequentially arranged in an array.
For example, we consider an array with identifier name Array [5], then:
As discussed earlier, we can access these elements with the help of the identifier name of the array and the corresponding index of the array.
For example, if you want to access the 4th element of the array, that is, 9, you would write this statement in C++:
cout << array [3];
Since the indexing of an array starts from 0, the range of the index would be from 0 to (size of the array – 1)
Also, arrays are based on the concept of static memory allocation. It means that the size of the array is fixed throughout the entire program run.
5. Linked Lists in C++
Linked lists are also one of the most popular and significant data structures in C++. Since linked lists are dynamic in nature, they overcome the drawback of arrays, that is, memory in an array is allocated statically.
In a linked list, the first data element points to the memory address of the second data element in the list which points to the memory address of the third element and so on.
In simpler words, the next element in a linked list is embedded in the current element.
This is how we can store data in a linked list:
Explore the Concept of Linked List in C
6. Stacks and Queues in C++
Stacks and queues are another popular data structures in C++. The terms “Stacks and Queues” go hand in hand but they are two different concepts which we will discuss briefly:
In programming terminology, a stack is both an abstract data type as well as a data structure that follows the LIFO rule (Last In First Out). It means that the element inserted at the last is the first one to be deleted.
In simple words, the insertion and deletion of data elements in a stack can only be done from one end, that is, the top.
A queue is also an abstract data type as well as a data structure but it follows the FIFO rule (First In First Out). It means that the element inserted first will be the first one to be deleted. In simple words, insertion and deletion of data elements in a queue take place from two ends – deletion from front and insertion from the rear.
Still confused? Take a deep breath and have this – Stacks and Queues in C/C++
7. C++ Trees
This is also a popular data structure we use in C++ although it is a bit complicated in comparison to what we saw previously.
In mathematical terms, a tree is referred to as a finite and non-empty set of elements. It can also be regarded as an abstract model of a hierarchical structure that follows a parent-child relationship.
In programming terminology, a tree is nothing but a non-linear data structure that has multiple nodes, rather than just one like we saw in a linked list, stack, and queue.
When we talk about trees, we generally discuss binary trees as it is of logical relevance in programming.
8. Quiz on C++ Data Structures
0 of 15 Questions completed Questions: You have already completed the quiz before. Hence you can not start it again.
Quiz is loading… You must sign in or sign up to start the quiz. You must first complete the following:
0 of 15 Questions answered correctly
Your time:
Time has elapsed
You have reached 0 of 0 point(s), (0)
Earned Point(s): 0 of 0, (0) #include<bits/stdc++.h> using namespace std; int search(int a[], int n, int ele) { int i; for (i = 0; i < n; i++) if (a[i] == ele) return i; return -1; } int main() { int a[] = {1, 4, 0, 6, 3}; int size = 5; int find = 6; int pos = search(a, size, find); if (pos == – 1) cout << “not found”; else cout << “Found”; return 0; } #include<bits/stdc++.h> using namespace std; int insert(int a[], int n, int ele) { a[n] = ele; return (n + 1); } int main() { int a[5] = {1, 4, 0, 6}; int pos = 5 ; int ele = 10; int ret = insert(a, pos, ele); cout<<a[pos]; return 0; } #include <bits/stdc++.h> using namespace std; struct Node { int ele; Node* left, *right; }; Node* insert(int ele) { Node* node = new Node; node->ele = ele; node->left = node->right = NULL; return (node); } int main() { Node* root = insert(10); root->left = insert(20); root->right = insert(30); root->left->left = insert(40); cout <<root->left->left->ele << endl; return 0; } #include <bits/stdc++.h> using namespace std; struct Node { int ele; Node* left, *right; }; Node* insert(int ele) { Node* node = new Node; node->ele = ele; node->left = node->right = NULL; return (node); } int sum(Node* root) { if (root == NULL) return 0; return (root->ele + sum(root->left) + sum(root->right)); } int main() { Node* root = insert(10); root->left = insert(20); root->right = insert(30); root->left->left = insert(40); int sum1 = sum(root); cout <<sum1 << endl; return 0; } #include <bits/stdc++.h> using namespace std; struct Node { int ele; Node* left, *right; }; Node* insert(int ele) { Node* node = new Node; node->ele = ele; node->left = node->right = NULL; return (node); } int main() { Node* root = insert(10); root->left = insert(20); root->right = insert(30); root->left->left = insert(40); cout <<root->right->left->ele << endl; return 0; } #include <bits/stdc++.h> using namespace std; void Print(queue<int>& Q) { while (!Q.empty()) { cout << Q.front(); Q.pop(); } } void reverse(queue<int>& Q) { stack<int> S; while (!Q.empty()) { S.push(Q.front()); Q.pop(); } while (!S.empty()) { Q.push(S.top()); S.pop(); } } int main() { queue<int> Q; Q.push(1); Q.push(2); Q.push(3); reverse(Q); Print(Q); } #include<iostream> using namespace std; void nex(int arr[], int n) { int next, i, j; for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if (arr[i] < arr[j]) { next = arr[j]; break; } } } cout<<next ; } int main() { int arr[] = {2,6,7,1}; int n = 4; nex(arr, n); return 0; } #include<iostream> using namespace std; void nex(int arr[], int n) { int next, i, j; for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if (arr[i] > arr[j]) { next = arr[j]; break; } } } cout<<next ; } int main() { int arr[] = {2,6,7,1}; int n = 4; nex(arr, n); return 0; } #include<bits/stdc++.h> using namespace std; int main() { stack<char> s; s.push(‘1’); s.push(‘2’); s.push(‘3’); while (!s.empty()) { char p=s.top(); s.pop(); cout << p; } return 0; } #include<bits/stdc++.h> using namespace std; void Delete(stack<char> &s, int n, int curr=0) { if (s.empty() || curr == n) return; char x = s.top(); s.pop(); Delete(s, n, curr+1); if (curr != n/2) s.push(x); } int main() { stack<char> s; s.push(‘1’); s.push(‘2’); s.push(‘3’); Delete(s, s.size()); while (!s.empty()) { char p=s.top(); s.pop(); cout << p; } return 0; } Which among the following is a FIFO structure? Which among the following is LIFO structure? What data structure shall be used in case of sequential access and frequent size variation? Which among the following is not a data structure supported by C++? Which of the following is a non linear data structure consisting of nodes and edges?
Quiz Summary
Information
Results
Results
0 Essay(s) Pending (Possible Point(s): 0)
Categories
1. Question
2. Question
3. Question
4. Question
5. Question
6. Question
7. Question
8. Question
9. Question
10. Question
11. Question
12. Question
13. Question
14. Question
15. Question
9. Summary
In this tutorial, we began our discussion on data types. After developing an understanding of what data types are, we carried on our discussion on the different types of data structures available in C++ with examples. Thereafter, we discussed some of the basic operations that we can perform in a data structure. Then, we gave a brief description of the 4 most popular data structures used by C++ programmers, that is, arrays, linked lists, stacks and queues, and trees.
After completing this tutorial, it is safe to say that we got a basic idea of what data structures are. For any further queries, feel free to leave a comment below.
Now its time to move on with an amazing tutorial of Pointers in C/C++