Last Updated on December 14, 2022 by Prepbytes
What are Data structures?
Data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently.
Depending on your requirement and project, it is important to choose the right data structure for your project. For example, if you want to store data sequentially in the memory, then you can go for the Array data structure.
Data Structures and Algorithms is an important part of Programming. Get a better understanding of problems by watching these video tutorials created by expert mentors at Prepbytes.
Types of Data Structures
Basically, data structures are divided into two categories:
- Linear data structure
- Non-linear data structure
Let’s learn about each type in detail.
In linear data structures, the elements are arranged in sequence one after the other. Since elements are arranged in particular order, they are easy to implement.
However, when the complexity of the program increases, the linear data structures might not be the best choice because of operational complexities.
Popular linear data structures are:
Array:
Arrays are defined as the collection of similar types of data items stored at contiguous memory locations. It is one of the simplest data structures where each data element can be randomly accessed by using its index number.
In C programming, they are the derived data types that can store the primitive type of data such as int, char, double, float, etc. For example, if we want to store the marks of a student in 6 subjects, then we don’t need to define a different variable for the marks in different subjects. Instead, we can define an array that can store the marks in each subject at the contiguous memory locations.
Representation of an array
We can represent an array in various ways in different programming languages. As an illustration, let’s see the declaration of array in C language –
As per the above illustration, there are some of the following important points –
Index starts with 0.
The array’s length is 10, which means we can store 10 elements.
Each element in the array can be accessed via its index.
Implementation:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int arr[6]={11,12,13,14,15,16};
// Way 1
for(int i=0;i<6;i++)
cout<<arr[i]<<" ";
cout<<endl;
// Way 2
cout<<"By Other Method:"<<endl;
for(int i=0;i<6;i++)
cout<<i[arr]<<" ";
cout<<endl;
return 0;
}
Linked List:
Linked list is a linear data structure that includes a series of connected nodes. Linked list can be defined as the nodes that are randomly stored in the memory. A node in the linked list contains two parts, i.e., first is the data part and second is the address part. The last node of the list contains a pointer to the null. After array, linked list is the second most used data structure. In a linked list, every link contains a connection to another link.
struct node
{
int data;
struct node *next;
} Representation of a Linked list
Linked list can be represented as the connection of nodes in which each node points to the next node of the list. The representation of the linked list is shown below –
Linked list is useful because –
It allocates the memory dynamically. All the nodes of the linked list are non-contiguously stored in the memory and linked together with the help of pointers.
In the linked list, size is no longer a problem since we do not need to define its size at the time of declaration. List grows as per the program’s demand and is limited to the available memory space.
Types of Linked list
Linked list is classified into the following types –
Singly-linked list – Singly linked list can be defined as the collection of an ordered set of elements. A node in the singly linked list consists of two parts: data part and link part. Data part of the node stores actual information that is to be represented by the node, while the link part of the node stores the address of its immediate successor.
Doubly linked list – Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly-linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer), and pointer to the previous node (previous pointer).
Circular singly linked list – In a circular singly linked list, the last node of the list contains a pointer to the first node of the list. We can have circular singly linked lists as well as circular doubly linked lists.
Circular doubly linked list – Circular doubly linked list is a more complex type of data structure in which a node contains pointers to its previous node as well as the next node. Circular doubly linked list doesn’t contain NULL in any of the nodes. The last node of the list contains the address of the first node of the list. The first node of the list also contains the address of the last node in its previous pointer.
Implementation:
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
};
// This function prints contents of linked list
// starting from the given node
void printList(Node* n)
{
while (n != NULL) {
cout << n->data << " ";
n = n->next;
}
}
// Driver's code
int main()
{
Node* head = NULL;
Node* second = NULL;
Node* third = NULL;
// allocate 3 nodes in the heap
head = new Node();
second = new Node();
third = new Node();
head->data = 1; // assign data in first node
head->next = second; // Link first node with second
second->data = 2; // assign data to second node
second->next = third;
third->data = 3; // assign data to third node
third->next = NULL;
// Function call
printList(head);
return 0;
}
Stack:
A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end, whereas the Queue has two ends (front and rear). It contains only one pointer top pointer pointing to the topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. In other words, a stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack.
Working of Stack
Stack works on the LIFO pattern. As we can observe in the below figure there are five memory blocks in the stack; therefore, the size of the stack is 5.
Suppose we want to store the elements in a stack and let’s assume that stack is empty. We have taken the stack of size 5 as shown below in which we are pushing the elements one by one until the stack becomes full.
Since our stack is full as the size of the stack is 5. In the above cases, we can observe that it goes from the top to the bottom when we were entering the new element in the stack. The stack gets filled up from the bottom to the top.
When we perform the delete operation on the stack, there is only one way for entry and exit as the other end is closed. It follows the LIFO pattern, which means that the value entered first will be removed last. In the above case, the value 5 is entered first, so it will be removed only after the deletion of all the other elements.
Standard Stack Operations
The following are some common operations implemented on the stack:
- push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs.
- pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state.
- isEmpty(): It determines whether the stack is empty or not.
- isFull(): It determines whether the stack is full or not.’
- peek(): It returns the element at the given position.
Implementation:
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> stack;
stack.push(21);
stack.push(22);
stack.push(24);
stack.push(25);
stack.pop();
stack.pop();
while (!stack.empty()) {
cout << stack.top() <<" ";
stack.pop();
}
}
We tried to discuss Data Structures in C++ in this article. We hope this article gives you a better understanding of basics in Data Structures and Algorithms. Prepbytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program that will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.