Common C++ Data Structures (with examples)

Data structures and algorithms have always been controversial topics from the placement point of view. Many argue that DSA is very important for getting placed in product-based companies like FAANG, while some say that development is really what big tech companies expect. Data Structures and algorithms are the most fundamental concepts of any programming language and having a good knowledge of DSA can make your code run efficiently occupying less memory and a faster compile time. Today, we’ll be looking at some of the most common data structures in C++ that are mostly asked in coding interviews.

What Are Data Structures Anyways?🤷

Data structures can be defined as storage containers in which different types of data items can be stored, modified, and retrieved. You can use data structures to keep huge chunks of data and retrieve the data when required.

There are several types of data structures and depending on the type of problem you’re dealing with, you may choose one data structure over the other. Each data structure comes with its own merits and demerits so you have to be careful while picking one up.

Types of Data Structures

There are mainly two types of data structures:-

1. Linear data structures: Data elements are ordered systematically (one after the other) for easy access to data. Each element has an index number associated with it. Linked lists, stacks, arrays, and queues are examples of linear data structures.
2. Non-linear data structures: Unlike linear data structures, data elements are arranged in a hierarchical manner(arranged at different levels) and not sequentially like linear data structures. Some examples of non-linear data structures include trees, graphs, and tries.

Data Structures You Should Know📝

Given below are some of the frequently used data structures that you have to know to be a better programmer 👇:

Arrays

An array data structure is a collection of similar types of data elements that are stored sequentially in the computer memory. Arrays use the concept of indexing for accessing and storing elements. Array indexing starts from index 0 and not index 1, so one must be careful while accessing the data. So, if there are six elements in an array, the index of the first element is zero, and the index of the last element is five.

A diagrammatic representation of an array is shown below:

Elements are stored inside the array with memory locations. The given array is of integer type, so each address occupies 2 bits of memory. In C++, we can have arrays of integers and arrays of strings but we cannot have both in one array.

Furthermore, arrays are of three types namely one-dimensional array, two-dimensional and multi-dimensional array. Although, 2-D arrays are part of multi-dimensional arrays. Multi-dimensional arrays can be thought of as a matrix with rows and columns. The syntax for initializing an array of 1-Dimension is given below:

Datatype ArrayName[ArraySize]  =  Value;
Code language: C++ (cpp)

Now, let’s take an example and see a simple code to understand how the initialization and accessing of an array work. We have initialized an array named arr[] and given it some value. For printing the array, we used a for loop.

You can practice coding on our code Playgrounds.

Source Code:

#include <iostream>
using namespace std;

int main()
{
     //Declaring array
     int arr[] = {1,4,2,6,5,8};

     //Printing array
     for(int i = 0; i < 6; i++){
       cout<<arr[i]<<" ";
     }
 return 0;
}
Code language: C++ (cpp)

Output:

1 4 2 6 5 8
Code language: plaintext (plaintext)

Linked lists

A linked list data structure is a linear data structure that consists of a series of nodes and each node contains two fields, a data field for storing values and a pointer that points to the address of the next node. The first node is called the head node and the last node which is the tail node points to NULL indicating the end of the list.

There are three kinds of linked lists:

1. Singly-linked list: These are the linked lists that we just saw. A node contains a data space and an address of the next node.
2. Doubly-linked list: In a doubly linked list, there is an extra pointer that points back to the previous node, hence making it accessible in both forward and backward directions. A real-life example of a doubly linked list can be found in music players, where we can change to the next track or the previous one with a forward and backward button.
3. Circular linked list: Like the name suggests in a circular linked list, the pointer of the tail node points back to the first node making it a circle. Circular linked lists are used in computer networking.

The following code snippet shows the implementation of a node of a linked list:

struct node
{
   //initializing data field
   int value;
   struct node *next;
};
Code language: C++ (cpp)

Stack

Stack is a linear data structure that contains data elements in the form of vertical containers and follows the principle of LIFO (Last In First Out) which means that the last element entered will be removed first. Boxes kept on each other vertically can be thought of as a stack.

A representation of the stack is given below in which three elements are added and we are required to take out the third element from the stack.

While using a stack, we need to be familiar with some basic terms associated with it such as:

• .push() – this operation pushes an element into the stack.
• .pop() – this operation is used to pull out an element from the stack.
• .isFull() – this operation examines if the stack is full.
• .isEmpty() – examines if the stack is empty.
• .top() – this operation returns the top element of the stack.

How to implement a stack in C++?

Stack implementation:

struct stack
{
    //defining container
    int elements[20];
    //declaring top variable
    int upper;
};
typedef struct stack st;
Code language: C++ (cpp)

Queue

The queue data structure is a linear data structure that follows the principle of FIFO (First In First Out) which means that the first element inserted is removed first. A real-life example of the queue data structure can be thought of as students entering an examination hall. The student having the first roll number enters first and the student having the last roll number enters last.

While using a queue, we need to be familiar with some basic terms associated with it such as:

• .enqueue() – This operation pushes an element into the queue.
• .dequeue() – This operation pops an element from the queue.
• .isEmpty() – This operation examines if the queue is empty.
• .isFull() – This operation examines if the queue is full.

How to create a queue in C++?

Queue implementation:

//implementing a queue as a class
class Queue
{
   //declaring a queue array
   int queue1[10];
   int first, last;
};
Code language: C++ (cpp)

The main difference between a stack and a queue is that the stack uses LIFO and the queue uses the FIFO principle. And the stack uses push and pop operations while queue uses enqueue and dequeue operations for inserting and deleting elements.

Graphs

Graphs are non-linear data structures that consist of nodes containing data elements that are connected by edges. The nodes having some values are called vertex and lines joining the nodes are called edges. Graphs can reduce the time complexity in comparison with linear data structures having a greater time complexity.

A real-life example of the graph data structure is a social network where the user can be thought of as a node and is connected to other nodes(friends of the user) with the help of an edge. Social networks are examples of undirected graphs as there exists a two-way connection between users.

There are three kinds of graphs present:

1. Undirected graph: Undirected graphs are normal graphs that do not have any weights associated with the edges and do not have any direction. The above-shown graph is undirected.
2. Directed graph: A graph in which the edges are pointed in a single direction with an arrow is called a directed graph. In the figure below, the vertex D points back to itself and this type of graph is cyclic in nature.

3. Weighted graph: A graph in which the edges connected to the nodes have a value associated(called weights) is called a weighted graph. Weights can represent anything like distance, price, mass, etc. Generally, while solving problems, weighted graphs are given in the questions.

Graphs are used in many searching algorithms such as Depth-First search and Breadth-First Search. Many map applications use graphs for navigating.

Trees

While linear data structures are easy to implement sequentially but when working with large datasets, the time complexity increases which reduces the efficiency. Non-linear data structures like trees can reduce the time complexity.

Tree data structures are hierarchical structures that contain nodes that are present at different levels. You have a root node at the very top and it has child nodes and each of those child nodes has its child nodes and so on. Usually, when we talk about trees, we refer to binary trees. A binary means that each node cannot have more than two child nodes

In the picture shown above, node 1 is the root node which has two child nodes node 2 and node 3. Furthermore, node 1, node 2 and node 3 are parent nodes. node 4, node 5 and node 6 are the leaf nodes meaning that they do not have any further child nodes.

There are many applications of trees such as Binary search trees which are used to check whether an element is present or not. In a binary search tree, the value of the left node is always less than the value of the right node which makes it faster to search for any element. The compiler in a programming language also uses trees to check and validate for errors. Tries are also special types of trees that are used to retrieve routing data in routers. Tries store characters in their nodes and they act like a dictionary to find a word or different words quickly.

Conclusion🎀

In a nutshell, data structures are containers for storing data sets in any programming language. Mastering Data structure and algorithms help a programmer write better code that occupies less memory and time. Also, data structures play a vital role in coding interviews.

You can check out Learning Paths at codedamn here.

Adios & have a great day!🤞