Data structure and algorithms is a branch of computer science that deals with creating machine-efficient and optimized computer programs. The term Data Structure refers to the storage and organization of data, and Algorithm refers to the step by step procedure to solve a problem. By combining "data structure" and "algorithm", we optimize the codes in software engineering.

A data structure is defined as a particular way of storing and organizing data in our devices to use the data efficiently and effectively. The main idea behind using data structures is to minimize the time and space complexities. An efficient data structure takes minimum memory space and requires minimum time to execute the data.

A 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.

Classification of Data Structure:

Linear data structure: Data structure in which data elements are arranged sequentially or linearly, where each element is attached to its previous and next adjacent elements, is called a linear data structure.Examples of this data structure are queue, stack, array,etc

Non-linear data structure: Data structures where data elements are not placed sequentially or linearly are called non-linear data structures. In a non-linear data structure, we can’t traverse all the elements in a single run only. Examples of non-linear data structures are trees and graphs.

Popular types of Data Structures:

• Array
• Linked List
• Stack
• Queue
• Binary Tree
• Binary Search Tree
• Heap
• Hashing
• Graph
• Matrix
• Misc
• Advanced Data Structure

Algorithm is defined as a process or set of well-defined instructions that are typically used to solve a particular group of problems or perform a specific type of calculation. To explain in simpler terms, it is a set of operations performed in a step-by-step manner to execute a task.

The word Algorithm means ” A set of finite rules or instructions to be followed in calculations or other problem-solving operations ” Or ” A procedure for solving a mathematical problem in a finite number of steps that frequently involves recursive operations”.

Algorithms can be simple and complex depending on what you want to achieve.

Properties of Algorithm:

• It should terminate after a finite time.
• It should produce at least one output.
• It should take zero or more input.
• It should be deterministic means giving the same output for the same input case.
• Every step in the algorithm must be effective i.e. every step should do some work.

The first and foremost thing is dividing the total procedure into little pieces which need to be done sequentially.

The complete process to learn DSA from scratch can be broken into 4 parts:

• Learn about Time and Space complexities
• Learn the basics of individual Data Structures
• Learn the basics of Algorithms
• Practice Problems on DSA

Here comes one of the interesting and important topics. The primary motive to use DSA is to solve a problem effectively and efficiently. How can you decide if a program written by you is efficient or not? This is measured by complexities. Complexity is of two types:

1. Time Complexity: Time complexity is used to measure the amount of time required to execute the code.
2. Space Complexity: Space complexity means the amount of space required to execute successfully the functionalities of the code.

Both of the above complexities are measured with respect to the input parameters. But here arises a problem. The time required for executing a code depends on several factors, such as:

• The number of operations performed in the program,
• The speed of the device, and also
• The speed of data transfer if being executed on an online platform.

So how can we determine which one is efficient? The answer is the use of asymptotic notation.

Asymptotic notation is a mathematical tool that calculates the required time in terms of input size and does not require the execution of the code.

It neglects the system-dependent constants and is related to only the number of modular operations being performed in the whole program. The following 3 asymptotic notations are mostly used to represent the time complexity of algorithms:

• Big-O Notation (Ο) – Big-O notation specifically describes the worst-case scenario.
• Omega Notation (Ω) Omega(Ω) notation specifically describes the best-case scenario.
• Theta Notation (θ) – This notation represents the average complexity of an algorithm.

The most used notation in the analysis of a code is the Big-O Notation which gives an upper bound of the running time of the code (or the amount of memory used in terms of input size).

Here we have followed the flow of learning a data structure and then the most related and important algorithms used by that data structure.

1. Array

The most basic yet important data structure is the array. It is a linear data structure. An array is a collection of homogeneous data types where the elements are allocated contiguous memory. Because of the contiguous allocation of memory, any element of an array can be accessed in constant time. Each array element has a corresponding index number.

2. String

A string is also a type of array. It can be interpreted as an array of characters. But it has some special characteristics like the last character of a string is a null character to denote the end of the string. Also, there are some unique operations, like concatenation which concatenates two strings into one.

3. Linked Lists

As the above data structures, the linked list is also a linear data structure. But Linked List is different from Array in its configuration. It is not allocated to contiguous memory locations. Instead, each node of the linked list is allocated to some random memory space and the previous node maintains a pointer that points to this node. So no direct memory access of any node is possible and it is also dynamic i.e., the size of the linked list can be adjusted at any time.

4. Matrix/Grid

A matrix represents a collection of numbers arranged in an order of rows and columns. It is necessary to enclose the elements of a matrix in parentheses or brackets.

For example:

A matrix with 9 elements is shown below.

This Matrix [M] has 3 rows and 3 columns. Each element of matrix [M] can be referred to by its row and column number. For example, a23 = 6.

5. Stack

Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

The reason why Stack is considered a complex data structure is that it uses other data structures for implementation, such as Arrays, Linked lists, etc. based on the characteristics and features of Stack data structure.

6. Queue

A Queue is a linear structure which follows First In First Out (FIFO) approach in its individual operations.

A queue can be of different types like

• Circular queue – In a circular queue the last element is connected to the first element of the queue
• Double-ended queue (or known as deque) – A double-ended queue is a special type of queue where one can perform the operations from both ends of the queue.
• Priority queue – It is a special type of queue where the elements are arranged as per their priority. A low priority element is dequeued after a high priority element.

7. Heap

A Heap is a special Tree-based Data Structure in which the tree is a complete binary tree.

Types of heaps:

Max-Heap: In this heap, the value of the root node must be the greatest among all its child nodes and the same thing must be done for its left and right sub-tree also.

Min-Heap: In this heap, the value of the root node must be the smallest among all its child nodes and the same thing must be done for its left ans right sub-tree also.

8. Hash

Hashing refers to the process of generating a fixed-size output from an input of variable size using the mathematical formulas known as hash functions. This technique determines an index or location for the storage of an item in a data structure.

9. Tree Data Structures

Tree data structure is similar to a tree we see in nature but it is upside down. It also has a root and leaves. The root is the first node of the tree and the leaves are the ones at the bottom-most level. The special characteristic of a tree is that there is only one path to go from any of its nodes to any other node.

Based on the maximum number of children of a node of the tree it can be –

• Binary tree –This is a special type of tree where each node can have a maximum of 2 children.
• Ternary tree –This is a special type of tree where each node can have a maximum of 3 children.
• N-ary tree – In this type of tree, a node can have at most N children.

Based on the configuration of nodes there are also several classifications. Some of them are:

• Complete Binary Tree – In this type of binary tree all the levels are filled except maybe for the last level. But the last level elements are filled as left as possible.
• Perfect Binary Tree – A perfect binary tree has all the levels filled
• Binary Search Tree – A binary search tree is a special type of binary tree where the smaller node is put to the left of a node and a higher value node is put to the right of a node
• Ternary Search Tree – It is similar to a binary search tree, except for the fact that here one element can have at most 3 children.

10. Graph Data Structure

A Graph is a non-linear data structure consisting of a finite set of vertices(or nodes) and a set of edges that connect a pair of nodes.

Each edge shows a connection between a pair of nodes. This data structure helps solve many real-life problems. Based on the orientation of the edges and the nodes there are various types of graphs.

Once you have cleared the concepts of Data Structures, now its time to start your journey through the Algorithms. Based on the type of nature and usage, the Algorithms are grouped together into several categories, as shown below:

1. Searching Algorithm

Searching algorithms are used to find a specific element in an array, string, linked list, or some other data structure.

The most common searching algorithms are:

• Linear Search –In this searching algorithm, we check for the element iteratively from one end to the other.
• Binary Search – In this type of searching algorithm, we break the data structure into two equal parts and try to decide in which half we need to find for the element.
• Ternary Search – In this case, the array is divided into three parts, and based on the values at partitioning positions we decide the segment where we need to find the required element.

2. Sorting Algorithm

Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of element in the respective data structure.

There are a lot of different types of sorting algorithms. Some widely used algorithms are:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Quick Sort
• Merge Sort

3. Divide and Conquer Algorithm

Divide and Conquer is an algorithmic paradigm. A typical Divide and Conquer algorithm solves a problem using following three steps.

1. Divide: Break the given problem into subproblems of same type.
2. Conquer: Recursively solve these subproblems
3. Combine: Appropriately combine the answers

This is the primary technique mentioned in the two sorting algorithms Merge Sort and Quick Sort which are mentioned earlier. To learn more about the technique, the cases where it is used, and its implementation and solve some interesting problems, please refer to the dedicated article Divide and Conquer Algorithm.

4. Greedy Algorithms

As the name suggests, this algorithm builds up the solution one piece at a time and chooses the next piece which gives the most obvious and immediate benefit i.e., which is the most optimal choice at that moment. So the problems where choosing locally optimal also leads to the global solutions are best fit for Greedy.

For example, consider the Fractional Knapsack Problem. The local optimal strategy is to choose the item that has maximum value vs weight ratio. This strategy also leads to a globally optimal solution because we are allowed to take fractions of an item.

5. Recursion

Recursion is one of the most important algorithms which uses the concept of code reusability and repeated usage of the same piece of code.

6. Backtracking Algorithm

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time

7. Dynamic Programming

The main concept of the Dynamic Programming algorithm is to use the previously calculated result to avoid repeated calculations of the same subtask which helps in reducing the time complexity.

8. Pattern Searching

The Pattern Searching algorithms are sometimes also referred to as String Searching Algorithms and are considered as a part of the String algorithms. These algorithms are useful in the case of searching a string within another string.

9. Bitwise Algorithms

The Bitwise Algorithms is used to perform operations at the bit-level or to manipulate bits in different ways. The bitwise operations are found to be much faster and are sometimes used to improve the efficiency of a program.

For example: To check if a number is even or odd. This can be easily done by using Bitwise-AND(&) operator. If the last bit of the operator is set than it is ODD otherwise it is EVEN. Therefore, if num & 1 not equals to zero than num is ODD otherwise it is EVEN.

For practicing problems on individual data structures and algorithms, you can use the following links:

• Practice problems on Arrays
• Practice problems on Strings
• Practice problems on Linked Lists
• Practice problems on Searching algorithm
• Practice problems on Sorting algorithm
• Practice problems on Divide And Conquer algorithm
• Practice problems on Stack
• Practice problems on Queue
• Practice problems on Tree
• Practice problems on Graph
• Practice problems on Greedy algorithm
• Practice problems on Recursion algorithm
• Practice problems on Backtracking algorithm
• Practice problems on Dynamic Programming algorithm

Apart from these, there are many other practice problems that you can refer based on their respective difficulties:

• School-level
• Basic level
• Easy level
• Medium level
• Hard level

You can also try to solve the most asked interview questions based on the list curated by us at:

• Must-Do Coding Questions for Companies
• Top 50 Array Coding Problems for Interviews
• Top 50 String Coding Problems for Interviews
• Top 50 Tree Coding Problems for Interviews
• Top 50 Dynamic Programming Coding Problems for Interviews

You can also try our curated lists of problems from below articles:

• SDE SHEET – A Complete Guide for SDE Preparation
• DSA Sheet by Love Babbar