Data Structure and Algorithms are two pillars of Programming. You may know that "Data Structure + Algorithms = Computer Program". They are also the most important ingredient of a good program and right choice of Data Structure and Algorithms can improve performance drastically, whereas a wrong choice can spoil the party, but do you know what exactly they are? Well, Data Structure are nothing but a way to store data, while Algorithms are ways to operate on that Data. There is a reason why Data Structure and Algorithms are taught in every single Computer Science classes, it doesn't matter whether you are learning Java, C++, Python, JavaScript, Golang, or any other programing language, those data structure and algorithm will be same everywhere. An hash table will always be a a way to associate one object with other and retrieve it in constant time whether you call it HashMap in Java or Dictionary in Python.
I have always encourage programmer to learn Data Structure and Algorithms and that's why you see many articles on these topics here. Sometimes I share a guide on a particular data structure like this one on array, while other times I share coding problems from interviews to test your skill and improve them further like this list of programming interview questions.
Whatever is the method of learning Algorithms and Data Structure the key is to learn and learn more. The best part of this topic is that it never get old, the time you invest on Data Structure will reward you for many years in your career.
Now that you know that Data Structure and Algorithms are important and constant learning is required, what is the minimum? What should a beginner programmer or fresh Computer Science graduate should aim?
I am going to answer this question on this article with a list of 10 most fundamentals and useful data structures every programmer should know. I'll first list down them and then give a brief overview of each them and share resources to learn further.
By the way, if you like to start with online courses, I have also shared best data structure and algorithms courses for programmers, if you need recommendations you can see that article as well.
10 Essential Data Structures Every Developer Should Learn
Here is the list of those data structure in the order they should be learned.
- Arrays
- Linked Lists
- Binary Tree
- Binary Search Tree
- Hash table
- Stack
- Queue
- Graph
- Trie
- Heap
Now, if you look at this list, many programmers are familiar with just first two. Some good ones will know till Queue and some excellent ones will know Graph, Trie and Heap. Your goal should be to know all of them. Let's go through them
1. Arrays
It is one of the most fundamental data structure. It stores data or elements in contiguous memory location, I mean adjacent memory location. For example, if you have 5 integers to store, you create an array of length 5 and they are stored adjacent memory location.
This means, if you know the address of any of those elements, you can figure out the address of others. This way of storing data provides one unique benefits, for example, the search is easy using index. Each element can be accessed in O(1) or constant time using index, but it also has some repercussions.
For example, adding and removing elements in an array is not possible? Why? because there is no guarantee that adjacent memory location will be free for array growth. The insertion and deletion is often achieved by creating a new array and then copying remaining element into them.
Here are some of the interesting array-based coding problems for practice:
Another important characteristic of array data structure is that it's ordered which means elements are stored in an order and they remain in that order. A key thing to learn and remember is when to use array as data structure in your program? Well, an array is good option
- when you know the size of your data in advance.
- and, when size of your data is not going to change
- you have enough single block of memory to store your elements in together
- and you need constant time access of your element.
These checkpoints should help you to decide when to use array but if you want to learn more, See this course which goes much more deeper in array than this article.
And, here are popular array based coding problems for practice:
- How to check if array contains duplicate element in Java? (solution)
- In a given array of 1 to 100, one number is missing? how to find that? (Solution)
- how to reverse a given array in place in Java? (Solution)
- How to find the first unique number in given array? (solution)
- How to merge two sorted arrays in Java? (solution)
- How to rotate an Array to left or right in Java? (solution)
These were common array based programming exercise which you can use for practice, and, If you need more coding problems, then you can also check-out this 30 array based coding questions where I have shared more advanced and hard array based coding problem for practice.
2. Linked Lists
This is another fundamental data structure which complements array, Yes I said compliment not oppose as it tries to address the shortcomings of array and provide an alternative or different way to store your data.
If you look closely, you cannot use array to store large number of items even if you have enough memory? Why, because those memory may not be available as a single block. Linked list solved that problem by linking nodes.
In linked list, data is stored in a node, which contains both actual data as well as memory address of next node. Remember, in array we don't need to store memory address of next element because you can calculate based upon index as they are just next to each other but that's not possible with linked list.
This means you need to bear the overhead of storing memory address along with the data but this provides some unique benefits. It's much easier for a linked list to grow than array. Anytime you can add or remove elements because you don't need to shift or create new array, all you need to do is just repoint some links, but this also has some repercussions.
Now, there is no way you can access data in constant time. If you need to get a particular element, you need to traverse through linked list starting from first node, known as head and compare data on each node until you reach to the node where you have the data you want. This means search will cost O(n) on linked list.
Now that you know about linked list data structure, the big question is when should you use it in your program? Let's try to answer that question. If you look closely, linked list offers better memory utilization but compromised the search in constant time ability. But, again it makes it easy to add and remove elements.
This means you should use linked list if
- you need to frequently add or remove data from store
- you rarely need to search data
- you don't know the size of your data in advance.
These points should help you to decide when to use a linked list but if you want to learn more, See this course to learn linked list in depth.
And, here are some linked list based coding problems for practice:
- How to reverse a singly linked list in Java? (Solution)
- How to find if a given linked list has cycle? (Solution)
- How to find length of a linked list in one pass? (Solution)
- How to find the 3rd element from end in a given singly linked list? (Solution)
- How to check if given linked list is palindrome? (Solution)
- How to reverse a linked list without recursion (solution)
- How to find union of two given linked list? (solution)
- How to remove duplicate nodes from an unsorted linked list? (solution)
- How to find the middle element of linked list in one pass (solution)
If you need more coding problems, then you can also check-out the Cracking the Coding interview book by Gayle McDowell which is like the holy grail of coding interview preparation.
Here are few more linked list based coding problems to get familiar with this data structure. One thing, I would like to highlight is that Recursion provides an easy solution of many linked list problems because a linked list is a recursive data structure.
I mean, when you take one node from linked list, remaining nodes are still a linked list, which means you can apply the same algorithm in the remaining linked list or data set.
3. Trees
Trees are one of the useful data structure which allows you to structure you data in a hierarchical way. This is the big difference between an array or linked list and a tree. Array and linked list both are linear data structure but tree is a hierarchical one, hence it is useful for storing hierarchical data like family trees, organization structure etc.
A tree data structure can be further divided into various trees depending upon their properties like N-ary Tree, Balanced Tree
Binary Tree, Binary Search Tree, AVL Tree, Red Black Tree, Radix tree etc. Out of these binary tree is most common one. IT's called binary tree because a node can have maximum of two children. Most of the tree algorithms provides log(N) performance, hence they are very fast as compared to linear data structure with O(n) performance.
4. Binary Search Trees
BST or Binary search tree is a special binary tree which holds its data in a ordered fashion. In BST, value of left node can be either equal to or less than root and value of right node can be equal to or greater than root. Because of this property, BST is very useful for sorting and arranging data.
You can use tree traversal algorithms like pre-order, in-order and post-order to traverse the tree and print values. Most of the tree algorithms can be easily implemented using recursion because trees are naturally recursive. You take one node of a tree and remaining is still a tree.
Here are some common binary search tree problems for practice for coding interviews:
- How to check if a given tree is a binary search tree in Java? (solution)
- Can you implement preorders traversal of binary tree in Java? (solution)
- Can you code post order traversal of binary tree in Java? (solution)
- Given in-order traversal of a binary tree, can you re-create the tree? (solution)
- How to count all the leaf nodes of a given binary tree in Java? (solution)
5. Hash Tables
It is one of my favorite data structure and probably the most versatile and useful of all data structure. It allows you to map one object to other, so that you can retrieve them in constant time. For example, id can be mapped to actual employee object and then it can be retrieved in constant time using id.
It's very similar to array, while array allows constant time access using index, hash table allows constant time access using key object. Hash tables can be implemented using array (known as bucket), where a hash function is used to generate the bucket index using key object.
The value object is stored on that index. If multiple object has to be stored in one bucket due to collision then a linked list or a binary tree can also be used.
Here are some commonly asked Hashing interview questions for practice:
- How to find symmetric pairs in an array? (solution)
- How to find if an array is a subset of another array? (solution)
- How to check if given arrays are disjoint? (solution)
And, here is a nice diagram from Wikipedia which explains how Hash table data structure works and how collision happens and resolved using chaining:
6. Stack
This is called a LIFO data structure or Last In First out because element inserted last are first to be retrieved. It is very similar to stack of plates on a dinner party, where plates are take from top. Similarly, elements are inserted and retrieved from the top of stack.
One of the most important use of Stack is to convert a recursive algorithm into iterative one because Stack represent a recursive call. Talking about implementation, you can use both array and linked list to implement a stack data structure.
Consumption from top of the stack takes O(1) time and so is insertion if underlying array is not resized.
Here are some of the frequently asked Stack interview questions for Practice
- How to implement stack using array? (solution)
- How to Evaluate postfix expression using a stack? (solution)
- How to Sort values in a stack? (solution)
- How to check balanced parentheses in an expression? (solution)
- How to implement Stack using Queue in Java? (solution)
7. Queue
Unlike Stack which are LIFO (Last In First Out) data structure, Queues are FIFO (First In First Out) data structure. If you have to process the elements on insertion order, you can use a queue. Queue allows you to insert at one end and consume at others which is another difference between stack and queue.
On stack, both insertion and deletion happens at the top of the stack. Some queues can also apply a priority on elements like PriorityQueue which allows you to process elements in a priority order. You can implement Queues using both array and linked list.
Here are some of the frequently asked Queues based questions from Programming Job interviews:
- How to implement stack using a queue?
- How to reverse first k elements of a queue?
- How to generate binary numbers from 1 to n using a queue?
8. Graphs
This is one data structure which is heavily used in real world. You can find distance between two cities or the shortest path using graphs. Even after its real-world application, programmer often has very little knowledge of graph data structure and struggle to implement when you asked them to create a class to represent a graph or code some of the graph algorithms.
Like tree, Graph is also set of nodes and edges. It can be directed or non-directed like one way or two-way road. A edge allows you to go from one node to another in graph. If there is no edge between two nodes then you cannot traverse there. You can use graph data structure to represent anything which has relationships for example from cities and highways, routers and ethernet cables to Facebook users and their friends.
As I said, a graph can directed or undirected, cyclic or acyclic, and weighted or unweighted. Some of the popular graph algorithms are BFS and DFS, which allows you to explore nodes in a graph. Most of the graph algorithms are O(n*lg(n)) or even slower hence also posses scalability challenges which means it may not be feasible to run graph algorithms for if the size of your graph increased significantly.
Here are some of the frequently asked Graphs interview questions for practice
- How to implement Breadth and Depth First Search Algorithms?
- How to check if a graph is a tree or not?
- How to count number of edges in a graph?
- How to find the shortest path between two vertices?
9. Tries
Trie is another lesser known but useful data structure which is used a lot in word matching and spell checking. It is also known as "Prefix Trees" because of its ability to find words with similar prefix faster.
It's a tree-like, hierarchical data structure which compactly store strings. It provides fast retrieval, and mostly used for searching words in a dictionary, providing auto suggestions in a search engine, and even for IP routing.
Here's an illustration of how three words "top", "thus" and "their" are stored in Trie:
Commonly asked Trie interview questions:
Here are some TRIE based coding problems from practice:
- How to Count total number of words in Trie?
- How to Print all words stored in Trie?
- How to Sort elements of an array using Trie?
- How to form words from a dictionary using Trie?
- How to build a T9 dictionary
If you want to learn more about Tries data structure, I suggest you to check this course.
10. Heap
This is one of the under-rated data structure and many programmer just don't know about it, but it can be very useful on finding the largest or smallest number or element in constant time. Similar to tree, its a hierarchical data structure and a type of binary tree, with only difference that the root of the tree always represent either highest node or lowest node.
There are two types of binary heap, max-heap and min-heap. In max-heap, root represent the maximum number while in min-heap it represent minimum value. Since, root is always the maximum or minimum you can access it in constant time but insert and delete require bit longer time because you need to re-adjust the heap to keep the maximum and minimum element at the right place.
This data structure can also be used to create Priority Queue, another useful data structure to process elements on priority.
Here are a couple of binary heap based coding problems for practice:
1. How to implement max heap and min heap in Java? (solution)
2. Implement the heap sort algorithm? (solution
3. Write a Program to check if a given array represent minimum heap or not? (solution)
4. How to convert a max-heap to min-heap in linear time?(solution)
You can further see Introduction to Algorithms book to learn more about heap data structure.
That's all about some of the must know data structure for programmers. A good knowledge of these fundamental data structure goes a long ways in becoming a better programmer and writing robust and performant software application. If you want to explore more data structure, you can also learn about different types of trees and queues like PriorityQueue.
Other Data Structure and Algorithms Articles you may like
- 100+ Data Structure Interview Questions with Answers
- 10 courses for Programming/Coding Job Interviews
- 75+ Coding Interview Questions for Programmers
- 30+ Array-Based Questions from Interviews
- 30+ LinkedList Based Java Interview Questions
- Grokking Algorithms - Book Review
- 21 String Programming Questions from Interviews
- How to solve scenario-based Algorithms Interview Questions
- Top 5 Data Structure and Algorithms Books for Programmers
- 20 Binary Tree Based Interview Questions
- 5 Best Courses to learn Data Structure and Algorithms in JavaScript
- My Favorite Python Data Structure and Algorithm Courses
Thanks a lot for reading this article so far. If you like this Data Structure and Algorithms tutorial for programmers then please share with your friends and colleagues. If you have any questions or feedback then please drop a note.
P. S. - And, if you are serious about taking your DSA skill to next level and looking for
some free courses, then you can check out this list of Free Data Structure and Algorithms Courses to start with.
No comments :
Post a Comment