Sumit MalviyaKnowledge of data structures is a must for any developer. While a lot of beginners and experienced programmers avoid learning Data Structures and Algorithms. Most of them, due to its complexity, think there is no use of all the above stuff in real life.
In this article, we’ll go over some of the most commonly used data structures in programming and explain what they are. Our goal is to help you understand the most common data structures and their applications so that you can choose the best data structure for the problems you encounter most frequently.
What is data structure? Why should developers know about it?
“A data structure is a container for storing data in a specific way. Nearly every programme of any size uses data structures in some ways”.
Put simply, data structures are used to store and retrieve data, solve problems, organize data, and provide performance and efficiency. They are also used for security purposes. In short, data structures are a must-know for any backend developer!
If you want to become a programmer, you should master the basics of data structures. By adding one in-demand skill to your resume, you will stand out from the crowd. I think that, in any type of development, knowledge of data structures is an essential skill. In backend development, it greatly enhances your code reusability and improves code efficiency.
Commonly used Data Structures by developers:
- Arrays
- Stacks
- Queues
- Linked lists
- Trees
- Heaps
- Graphs
Arrays
Arrays is the simplest and most commonly used data structure in programming. In C/C++ or any other programming language, an array is a group of related data items stored in adjacent memory regions, and its elements can be retrieved at random using an array’s indices. They can be used to hold a collection of primitive data types of any type, including int, float, double, char, etc.
Let’s look at some basic C# array declarations. The simplest dynamic array of integer types without a fixed size is defined by the next piece of code.
int[] intArray;
C#
The declaration of an array begins with the type of array, followed by a square bracket ([]), then the array name, as you can see from the code excerpt above.
The code snippet depicts an array that can store 5 items only starting from index 0 to 4.
int[] intArray;
intArray = new int[5];
C#
The bit of code that follows declares an array with a capacity of 100 elements, ranging from index 0 to 99.
int[] intArray;
intArray = new int[100];
Stacks
Stacks is a structure where you store the previous states of your work (which is limited to a specific number) in the memory in such an order that the last one appears first. As many apps rely heavily on stack. In data structures, stacks are a linear sort of data structure that adheres to the LIFO (Last-In-First-Out) principle and enables insertion and deletion operations from one end, and the top.
For example: Let’s say you have a stack of 10 books in ascending order.
Only the top book, number 10, which is kept at the top of the stack, is visible.
If you wish to insert a new book first, say 1. You must update the top before inserting a new text
Furthermore, you must also remove the top book from the stack if you want to reach out to any other book other than the 10th-highest.
Linked Lists
On the surface, linked lists look similar to arrays, but they differ in memory allocation, internal structure, and the way they perform basic insertions and deletions. There are nodes in a linked list, which are stored at random in memory.
A linked list is similar to a chain of nodes, with each node containing information such as data and a pointer to the next node in the chain. Because linked lists allocate memory dynamically, they are frequently used to overcome the limitations of arrays. Where size is no longer an issue and users do not need to specify its size when declaring.
When to use Linked list…
Linked List is often preferred over arrays, as there is no need to shift every member after insertion or deletion in a Linked List, these operations are fairly simple. The only address that has to be modified is the one in the pointers. While the elements in an array must be moved.
There are various types of linked lists, including single, double, and circular linked lists.
Singly Linked Lists
Singly linked lists are used to store sequential data, like a list of items.
Because they are not as efficient as arrays, singly linked lists have some drawbacks:
- They do not have random access
- They can only be traversed in order (starting at the first element)
public class Linked List Examples
{
Node head; // head of list
static class Node
{
int data;
Node next;
Node(int d) { data = d; next=null; }
}
}
/* This function prints contents of the linked list starting from head */
public void display()
{
Node n = head;
while (n != null)
{
System.out.print(n.data+” \n”);
n = n.next;
}
}
Doubly Linked Lists
A doubly linked list is a linked list in which each element has two pointers, one each to its predecessor and successor. It consist of 3 components:
*prev – address of the previous node
data – data item
*next – address of next node
Circular linked list
Creating a circular linked list is the same as creating a singly linked list. One difference is that instead of the last element pointing to NULL, we’ll have it point to the head.
linkedListTraversal(head);
head = insertAtFirst(head, 54);
head = insertAtFirst(head, 58);
head = insertAtFirst(head, 59);
printf(“Circular Linked list after insertion\n”);
linkedListTraversal(head);
Refer to this output:
Circular Linked list before insertion
Element is 4
Element is 3
Element is 6
Element is 1
Circular Linked list after insertion
Element is 59
Element is 58
Element is 54
Element is 4
Element is 3
Element is 6
Element is 1
Queues
Another linear data structure is queues, which store elements sequentially. Similar to stacks. It is only the use of the First in First Out (FIFO) method in Queue that distinguishes it from Stacks.
In simple words, a queue is defined as a list in which all additions to the list occur at one end and all deletions occur at the other. The operation is performed on the element that is first pushed into the order.
Example:
A single-lane, one-way road where the car enters first and exits first can work as a realistic example of a queue.
Trees
Trees are hierarchical data structures with vertices (nodes) and edges connecting them. A tree is like a graph, but the key difference is that a tree cannot have cycles. Various complex algorithms and Artificial Intelligence algorithms use trees to store and solve problems efficiently. The uppermost node in a tree data structure is referred to as the root node. Data of any type is present in each node.
It can be understood by viewing an organizational hierarchy:
As the employee’s name is contained in the node of the tree structure shown above, a string is the appropriate data type.
Binary Search Trees
Binary Search Trees (BST) are a data structure that can be used to store elements in a sorted manner. The BST is a binary tree where each node has at most 2 children. Each node also contains an integer field called key, which stores the value of the key of its parent node.
Heaps
Heaps are special types of binary trees. It is often called a complete binary tree in which all levels except the last one, the leaf node, are completely filled. They are used to implement priority queues and heapsort, which can be thought of as an ordered version of bubble sort.
Let’s understand with an example:
Heaps are implemented as a linked list, with each node having a value and a left and right child. Each node also has an upper bound (the maximum number below which it will not grow) and an internal tag identifying what kind of data it contains:
- The root node has no tags; this is the base case for adding new nodes to the heap.
- Nodes with one or two children have their tags set according to their data type; if they’re integers then they’re represented by ints; if they’re strings then they’re represented by chars; etcetera…
- Nodes with three or more children use an array holding references to all their substrings in order from left-to-right (or right-to-left if you prefer).
Graphs
Graphs are used to model relationships between objects. A graph consists of nodes and edges, which can be connected by properties that define the nature of these connections.
For example, a flight route might be represented as an undirected graph with no edges connecting each node, except for one destination-to-destination edge connecting two nodes.
This graph has a set of verticals (nodes) V= {A, B, C, D, E } and a set of edges= { (AB), (AC), (CD), }
In addition to being useful for representing real-life situations like flight routes and social networks, graphs have been applied in areas such as AI research and even cryptography!
Key takeaways for choosing the right data structure
The primary function of most computer programs does not involve calculations, but rather the storage and retrieval of information, usually as quickly as possible. Learning about data structures and algorithms is at the heart of development.
We read linear data structures, such as arrays, linked lists, stacks, and queues, that arrange elements sequentially. Hierarchical data structures like trees and heaps. While each data structure is used for a different kind of data. The right choice will lead to more efficiency.
Here are the key considerations:
Type of data needs to be stored: Some types of data might be best suited to a particular data structure.
Cost of operations: When it comes to the most frequently performed operations, we want to minimize the cost associated with them.
Memory usage: Often, we want data structures that use less memory.
I hope that, with the right knowledge, you will be able to make the most of your data and make it a more effective part of your application.
Vadita
Add comment