Data Structures and Algorithms (DSA) is an important part of Computer Science that deals with the organization of data values and code optimization. To understand more about DSA, let’s break down the word DSA into two parts:
- Data Structures
- Algorithms
A data structure is used for the storage and organization of data values for further use in an application. Talking about an algorithm, it is a stepwise process to solve a problem.
Now, let’s look at some of the most commonly used data structures:
| Data Structure | Meaning |
|---|---|
| Array | It is one of the basic data structures that is like a linear list of data points of the same type. |
| Linked List | This is similar to an array but here it has two fields: Data Field: For data values Reference Field: For storing address |
| Trees | A collection of nodes is a tree. A node is a data point connected with other points with the help of edges. The top of a tree is the root node. |
| Stacks | Imagine a pile of chairs. If you want to add another chair, for that, you will have to add the chair at the top. That’s a stack. Insertion or deletion takes place at the top of the stack of data values. It follows Last-In-First-Out (LIFO) Principle. |
| Queues | A queue in English is a line. Similarly, in DSA, it is a line of data values that follows the FIFO ( First in First out) Principle. |
| Graphs | A graph is a collection of nodes connected to one another via edges. It forms a network of nodes like in the case of a journey from one source to a destination. |
Data Structures are used in a wide variety of fields. Some of the important applications include:
| Data Structure | Application |
|---|---|
| Array | Mobile phone contacts |
| Linked List | Next feature of Music Player |
| Trees | Indexing in databases |
| Stacks | Undo and Redo tasks in editors |
| Queues | In Operating Systems for FCFS scheduling |
| Graphs | Google Maps, Facebook, and LinkedIn |
Here is a list of some of the best resources that can help you learn the inside-out of the DSA:
| Books | Data Structures and Algorithms Made Easy Narshima Karumanchi. Introduction to Algorithms (Cormen) |
| Youtube Channels | Abdul Bari Tushar Roy Apni Kaksha Neso Academy Jenny’s Lectures Kunal Kushwaha |
| Online Sites | Udemy Coursera GeeksforGeeks |
Now, let’s look at some of the important DSA questions.
A data structure is a way of storing and organization of data values for further use in an application. Examples include Graph, Trees, Arrays, Linked List, etc.
Data structures are of two types:
| Linear | Array, Stack, Queue, Linked-List |
| Non-Linear | Graphs, Trees |
Dynamic data structures are flexible and size changes can occur during insertion or deletion operations. Dynamic data structures play a key role in programming because they provide the programmer with the flexibility to adjust the memory consumption of programs.
Insert: Here, we add a new data item in a data structure.
Search: In this, we find an element in the data structure.
Sort: Simple sorting like arranging values in ascending or descending order. For example, arranging values in an array.
Delete: Here, we delete unwanted data points in a data structure.
Traversal: We access each data item exactly once so that it can be processed for further use.
Infix: We write expressions in infix notation, e.g. x+y - z, where operators are used in-between operands. For humans, it goes well, but for computing devices, it’s not preferred.
Prefix: Here, the operator is prefixed to operands, i.e. operator is written ahead of operands. For example, +xy instead of x+y.
Postfix: Here, we use the operator after the operands. For example, XY is written as XY.
- Linear Search.
- Binary Search.
- Jump Search.
- Interpolation Search.
- Exponential Search.
An array is a collection of data points of the same type stored at contiguous memory locations.
For example, an array of integers like 1,2,3,4,5. This array has 5 elements.
The index of an array usually starts with 0.
A dynamic array is an array with a modification that is automatic resizing. This means that the array expands when we add more elements. This helps to provide flexibility as size is not fixed. So, there’s no need to know the size in advance.
- Array elements are stored in contiguous memory blocks in the primary memory.
- Array name represents its base address.
- The base address is the address of the first element of the array.
- Array’s index starts with 0 and ends with size-1.
This is similar to an array but it consists of a node that has two fields:
Data Field: For storing data values.
Reference Field: For storing address.
A linked list is used in the next feature of a music player.
Ans: The different types of linked lists are:
- Singly Linked list
- Doubly Linked list
- Circular Linked list
- Doubly Circular Linked list
A collection of nodes is a tree. A node is a data point connected with other points with the help of edges. The top of a tree is the root node. Applications of trees include indexing in databases.
A graph is a collection of nodes connected to one another via edges. It forms a network of nodes like in the case of a journey from one source to a destination.
Uses:
- Google Maps
Ans: A tree structure is connected and can never have loops whereas in the graph there are no such constraints. A tree provides information about the relationship between nodes in a hierarchical manner and the graph follows a network model.
LIFO: (Last-In-First-Out) Last inserted element is removed first in the LIFO principle. Example: Stack follows LIFO.
FIFO: (First-In-First-Out) First Element (first to be inserted) is taken out first.
Example: Queue follows FIFO
A queue in English is a line. Similarly, in DSA, it is a line of data values that follows the FIFO ( First in First out) principle. Insertion is done at the rear end and deletion at the front end.
A priority queue is like a normal queue of elements but here each element has some priority. The elements in the priority queue occur in this order only.
Say, we have some values like 1, 2, 7, 8, 14, 31 inserted in a priority queue with an ordering based on least values to the greatest value. Therefore, the 1 number will have the highest priority while 31 will have the lowest priority.
A stack is a linear data structure having values that are inserted as per the LIFO principle. To make the point more clear, imagine a pile of chairs. You want to add another chair, for that, you will have to add the chair at the top. That’s a stack. Insertion or deletion takes place at the top of the stack of data values.
| Stack | Queue |
|---|---|
| Insertion and deletion in stacks take place only from one end of the list called the top. | Insertion and deletion in queues take place from the opposite ends of the list. The insertion takes place at the rear end of the queue and the deletion takes place from the front end. |
| Insert operation is called push in a stack. | Insert operation is called enqueue operation. |
| Delete operation is called pop in a stack. | Delete operation is called dequeue operation. |
A heap data structure is a complete binary tree that follows a specific order. Heaps are of two types:
- Max Heap
- Min Heap
- A binary heap is a complete binary tree that satisfies the heap ordering property.
- A Binary Heap can either be Min Heap or Max Heap.
- It’s a complete tree, thus it is suitable for being stored in an array.
An AVL tree is a type of binary search tree. It is named after its inventors Adelson, Velskii, and Landis. An AVL tree is a balanced binary search tree where the height of the two subtrees of a node differs by a maximum of one unit.
A Hash table is a data structure used to store data points in an associative manner. The values are stored in an array format. Hash tables are used to store keys/value pairs
Hash tables provide constant-time O(1) lookup on average, irrespective of the number of items(n) in the table.
- Stack
- Queue
- Linked List
- Binary Tree.
A dequeue is a double-ended queue. This queue data structure includes elements that can be inserted or removed from either end.
When a stack is completely full and we try to insert more elements onto the stack then this condition is called stack overflow condition. Here, top=maxsize-1, and no further elements can be inserted.
The postfix form of the given expression is XY+ZC-*
A tree is perfectly height-balanced if the left and right subtrees of any node are of the same height. We can also say that a tree is height-balanced if the heights of the left and right subtrees of each node differ by a maximum of one unit.
- Adjacency matrix
- Adjacency list
- And adjacency set.
- push() - Adds an element at the top of the stack.
- pop() - Deletes an element from the top of the stack.
- peek()- Displays the topmost element.
Queues are important in computer science. They are useful in transport, and operations research. They are also useful in a case where resource sharing takes place among a myriad of consumers. For example, FCFS scheduling.
Linear search is a technique in which we traverse a list in a sequential manner to find an element. When we find the element that is required, we return the index or position of that element.
In this type of search technique, we divide the sorted array or list into two halves. This is done to save time in searching. Here, we consider arrays in sorted form only.
Linear Search-O(N) Binary Search- O(log 2 N)
Tree traversal is a process that goes through the entire tree in a particular manner. Depending upon the order of traversal, we have different types:
- Inorder Traversal (Left, Root, Right)
- Preorder Traversal (Root, Left, Right)
- Postorder Traversal (Left, Right, Root)
Kruskal algorithm treats a graph as a forest and every node as an individual tree. A tree connects to another only and only if it has the least cost among all available choices without violating Minimum Spanning Tree (MST) properties.
Prim's algorithm treats each node as a single tree and continues to add new nodes to the spanning tree from the given graph.
It is a spanning tree that has the minimum weight among all the spanning trees of the same graph.
-
The Tower of Hanoi is a problem that comprises three rods and multiple disks.
-
At the start, all the disks are placed on one rod, one over the other in increasing order.
-
The aim of this problem is to move the stack of disks from the starting rod to another rod, following these rules as below:
- A disk cannot be placed on top of a smaller disk
- No disk can be placed on top of the smaller disk.
Recursion in general is a function calling itself. Extending the same logic for Algorithms, we can say that an algorithm that calls itself is a recursive algorithm. One good example of their use would be searching through a file system. Usually, they are used when the iterative approach is not useful for complex problems.
A stack is a recursive data structure because:
- A stack can either be empty or
- It will have a top pointer and the rest part apart from the top is also a stack by itself, thus it’s recursive.
The time complexity of MergeSort is O(n*log n)
Shell sort is a sorting algorithm based on the insertion sort algorithm.
This algorithm is highly efficient in sorting. This algorithm tries to avoid large shifts as in the case of insertion sort if the smaller value is to the far right and has to be moved to the far left.
Worst-case time complexity is O(n^2)
A red-black tree is a binary tree that has nodes represented by two colors: red and black. The tree follows specific properties.
These include:
- The root node of the tree is always black.
- Every path from the root to any of the leaf nodes should have the same number of black nodes.
- No two red nodes can be adjacent to each other.
It occurs when the picked pivot is an extreme (smallest or largest) element. Usually, when the input array is sorted or reverse sorted, it also leads to the worst case.
- For BFS - Queue Data Structure
- For DFS - Stack Data Structure
BFS Algorithm stands for Breadth-First Search. It is a vertex-based technique for finding the shortest path in the graph. For BFS, we use a Queue data structure.
DFS Algorithm stands for Depth First Search. It is an edge-based technique. In DFS, traversal can be started from any node. For DFS, we use a stack data structure.
Ans: The maximum nodes in a binary tree are: 2k+1-1 where k >= 1.
Ans: 1.Single linked list consist of nodes that has member which points to the address of the next node and there is no provision of coming back to the previous node.
2.Double linked list consists of nodes that has members to point to the address of the previous and next node along with the data of the list. The first node's previous member is NULL and last node's next member is NULL. Here, the list can be traversed in both directions.
3.Circular Linked list consists of nodes in which the last node's next member of the list points to the address of the first node and no previous member is present in the node. It is a single circular linked list.
4.Double circular linked list consists of both previous and next member in node and the next of last node points to address of the first node and previous of first node points to the address of the last node.
Need Help in Web-Development-Path-And-Resources
DSA path And Important Questions click here
11 Weeks Workshop on Data Structures and Algorithms Solution in python
11 Weeks Workshop on Data Structures and Algorithms Solution in C++
Join - https://discord.gg/gtYUZQSjTt
Show some ❤️ by giving 