In this article, we will be discussing about the different core concepts of different data structures such as Lists, Sets, Maps and queues in Java. We will be also discussing about the advantages and disadvantages of these different structures and appropriate scenarios where these data structures should be used efficiently.
What is Data Structure
A data structure is a way of collecting and organizing data. We must have a good knowledge of data structure in order to develop efficient software. Hence, choosing the right data structure to develop software increases the performance and efficiency of the overall software.
Data Structure In Java
Java has numerous inbuilt data structures known as Collection types. The different core interfaces it provides are Collection, List, Set, Queue, Map, NavigableSet, SortedSet, SortedMap and NavigablMap. Below are the concrete implementation classes of these interfaces.
- Map
- HashMap
- HashTable
- TreeMap
- LinkedHashMap
- Set
- HashSet
- LinkedHashSet
- TreeSet
- List
- ArrayList
- Vector
- LinkedList
- Queues
- PriorityQueue
Apart from these there some utilities classes such as Collections, Arrays that can be used to perform different operations on collection types in Java.
ArrayList stores objects and can grow and shrink.
LinkedList uses poointers to keep track of elements.
Vector similar to arraylist but provides synchronization
Stack operates in Last In First Out (LIFO)
Queue operates in First In First Out.
Pros and Cons
Different data structure offers different advantages and disadvantages. Some offer quick insertions and deletions but slower fetches. Let's discuss the pros and cons of each of them.
ArrayList and Vector Advantages
- Provides fast iteration of elements using indexing.
- It provides memory coherance meaning the elements are stored in a sequential memory location.
- Fast random access of elements due to memory coherance.
- Provides an optional option to define the size during it's creation.
ArrayList and Vector Disadvantages
- Addition or deletion of data from the middle is time consuming as data needs to be shifted to update the list
- Due to memory coherance, for larger elements a list will need significant contiguous blocks of memory. Hence, memory wastage is found.
- Resizing of an arraylist when it reaches it's capacity with it initial capacity which is 10 is a costlier process as the elements will be copied from old to new space with 50% more capacity.
Advantages of LinkedList
An implementation of Linked List in Java can be found in this article.
- Very efficient for fast removal and addition of elements.
- Efficient Memory Utilization ,i.e no need to pre-allocate memory.
Disadvantages of LinkedList
- Slow iteration of elements as compared to ArrayList.
- Inefficient random access.
- Extra memory overhead is rquired to keep track of the pointer to the next element of the list.
Advantages of HashSet
- HashSet allows null value and contains only unique values.
Disadvantages of HashSet
- HashSet doesn't maintain the insertion order..
Advantages of LinkedHashSet
- LinkedHashSet maintains insertion order of elements.
- LinkedHashSet gives the performance of order O(1) for insertion, removal and retrieval operations.
Disadvantages of LinkedHashSet
- Not memory efficient as LinkedHashSet maintains LinkedList along with HashMap to store its elements.
Advantages of TreeSet
- Allows unique elements.
- Provides faster access and retrieval of elements.
- Stores elements in ascending order.
Advantages of HashMap
- Allows insertion of key value pair.
- HashMap is non synchronized.HashMap cannot be shared between multiple threads without proper synchronization.
- HashMap is a fail-fast iterator.
- Faster access of elements due to hashing technology.
Disadvantages of HashMap
A custom implementation of HashMap in Java can be found in this article.
- Potential of collision when 2 distinct keys generate the same hashCode() value worse the performance of the hashMap.
- Occasionally HashMaprequires resizing when the original size of HashMap buckets are full. Resizing takes O(n) time as the elements from the previous hashtable/HashMap are transferred to a new bigger HashMap.
Advantages of LinkedHashMap
- Manintains insertion order.
- Faster iteration with LinkedHashMap.
Disadvantages of LinkedHashMap
- Slower than HashMap for adding and removing elements.
Advantages of TreeMap
- TreeMap stores key-value pairs in a sorted ascending order(based on the key).
- Lets you define a custom sort order.
- The retrieval speed of an element out of a TreeMap is fast, even in a TreeMap with a large number of elements.
Conclusion
In this article, we discussed about different data structures in Java and learned thier pros and cons while using it.
