7
10 Essential Data Structure Every Developer Should Learn
source link: https://javarevisited.blogspot.com/2022/09/10-data-structure-programmer-learn.html#axzz8BAMo4CGb
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
10 Essential Data Structure Every Developer Should Learn
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.
Loaded: 0.16%
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 Structure 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
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. You take one node from linked list, remain nodes are still a linked list, which means you can apply the same algorithm in the remaining 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 pre-order 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?
- How to find if an array is a subset of another array?
- How to check if given arrays are disjoint?
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?
- How to Evaluate postfix expression using a stack?
- How to Sort values in a stack?
- How to check balanced parentheses in an expression?
And, here is how the stack changes when you push or pop elements form stack data structure, starting from empty Stack.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK