Questions
When writing a data structure, what should be our guidelines for choosing the right Java Collection?
1. Collections
Before I discuss the guidelines for choosing the right Java Collection, it is necessary to introduce concrete collections. “There are two fundamental interfaces for collections: Collection and Map” (Horstmann, 2019, p.664). Below are the classes that implement the Collection interface and Map interface.
2. Guidelines
This part will introduce the definitions and usage scenarios of ArrayList, LinkedList, HashSet, LinkedHashSet, TreeSet, Queue, Deque, PriorityQueue, Map, HashMap, LinkedHashMap, and TreeMap in detail.
2.1.1 List
The elements stored in the List are ordered but not necessarily in ascending or descending order. Elements can be repeated. For example [a, c, b, c].
2.1.2. ArrayList
Advantage: ArrayList can store objects except for primitive types. The number of objects that an ArrayList can store can be expanded. ArrayList supports fast random access, that is, its elements can be accessed by index.
Disadvantage: However, “ArrayList suffers from a major drawback. Removing an element from the middle of an ArrayList is expensive since all ArrayList elements beyond the removed one must be moved toward the beginning of the ArrayList. The same is true for inserting elements in the middle” (Horstmann, 2019, p. 668).
2.1.3. LinkedList
Advantage: “Removing an element from the middle of a linked list is an inexpensive operation - only the links around the element to be removed need to be updated” (Horstmann, 2019, p. 670). “The only reason to use a linked list is to minimize the cost of insertion and removal in the middle of the list” (Horstmann, 2019, p. 677).
Disadvantage: “Linked lists do not support fast random access. If you want to see the nth element of a linked list, you have to start at the beginning and skip past the first n - 1 elements. There is no shortcut. For that reason, programmers don’t usually use linked lists in situations where elements need to be accessed by an integer index” (Horstmann, 2019, p. 676).
2.1.4. Summary
(1) If we want to access elements randomly, we can use ArrayList;
(2) if we want to insert or remove elements efficiently, we can use LinkedList.
2.2.1. Set
Elements in a Set cannot be repeated and they might or might not be in some definite order (Eck, 2019).
2.2.2. HashSet
Advantage: “HashSet is a class that implements a set based on a hash table” (Horstmann, 2019, p. 685). The hash table is a data structure conducive to quickly finding elements, and HashSet is implemented based on the hash table. Hence, HashSet is suitable for situations where elements need to be quickly found.
Disadvantage: “The drawback is that the hash table gives one no control over the order in which the elements appear. Hence, one would only use a HashSet if he/she doesn’t care about the ordering of the elements in the collection” (Horstmann, 2019, p. 685).
2.2.3. LinkedHashSet
Advantage: LinkedHashSet is implemented based on linked hash table. “It can remember in which order we inserted items” (Horstmann, 2019, p. 708). Therefore, when we iterate over the elements in the LinkedHashSet with an iterator, the output order is the insertion order.
2.2.4. TreeSet
Advantage: TreeSet is a class that implements a set based on a red-black tree. “The TreeSet class is similar to the hash set, with one added improvement. A tree set is a sorted collection. We can insert elements into the collection in any order. When we iterate through the collection, the values are automatically presented in sorted order” (Horstmann, 2019, p. 687).
Disadvantage: Compared with HashSet, adding an element to TreeSet takes longer than adding an element to HashSet (Horstmann, 2019).
2.2.5. Summary
(1) If we want to find an element quickly, we can use HashSet, but when traversing, the outputs are not in a definite order;
(2) LinkedHashSet improves this shortcoming, in other words, the output order is the insertion order when traversing;
(3) TreeSet also improves this shortcoming, the output elements have a definite order, but adding elements to a TreeSet takes longer than adding elements to a HashSet.
2.3.1. Queue
A Queue is a data structure that allows adding data from the head and removing data from the tail. But we cannot add data from the middle.
2.3.2. Deque
Deque is a double-ended queue, which means we can add or remove data from the head and add or remove data from the tail.
2.3.3. PriorityQueue
“A PriorityQueue retrieves elements in sorted order after they were inserted in arbitrary order. That is, whenever we call the remove method, we get the smallest element currently in the priority queue” (Horstmann, 2019, p. 695).
2.3.4. Summary
(1) Since Queue has the characteristic of first in, first out, “Queues are typically used in a computer when only one item can be processed at a time, but several items can be waiting for processing” (Eck, 2019, p . 457). For example, when a web server processes web requests, those pending requests are stored in the Queue.
(2) PriorityQueue has some special usage scenarios because its remove() method always removes the smallest element in the current PriorityQueue. For example, a typical application of PriorityQueue is job scheduling. “Each job has a priority. Jobs are added in random order. Whenever a new job can be started, the highest priority job (priority 1) is removed from the queue” (Horstmann, 2019, p. 696).
2.4.1. Map
Advantage: Map is a data structure that stores key/value pairs. We can find the corresponding value according to the key. “A set is a collection that lets you quickly find an existing element. However, to lookup an element, you need to have an exact copy of the element to find. That isn’t a very common lookup - usually, you have some key information, and you want to look up the associated element. The map data structure serves that purpose. A map stores key/value pairs. You can find a value if you provide the key” (Horstmann, 2019, p. 697).
2.4.2. TreeMap
Advantage: “If the map is a TreeMap, then the key set of the map is a sorted set, and the iterator will visit the keys in ascending order” (Eck, 2019, p. 509).
Disadvantage: Operations on elements in TreeMap take longer than operations on elements in HashMap. For example, accessing elements in a TreeMap takes longer than accessing a HashMap.
2.4.3. HashMap
Advantage: Operations on elements in HashMap take less time than operations on elements in TreeMap. For example, accessing elements in a HashMap takes less time than accessing a TreeMap.
Disadvantage: “For a HashMap, the keys are visited in an arbitrary, unpredictable order” (Eck, 2019, p. 509).
2.4.4. LinkedHashMap:
Advantage: LinkedHashMap is an improvement of HashMap. “The LinkedHashMap classes remember in which order we inserted items” (Horstmann, 2019, p. 708). In other words, the keys are visited in insertion order.
2.4.5. Summary
(1) If we need to access keys in order, we can use TreeMap or LinkedHashMap. If there is no requirement for visiting order, HashMap is recommended to save operation time.
3. In conclusion
(1) For List, if we want to access elements efficiently, we can use ArrayList; if we want to insert or remove elements efficiently, we can use LinkedList.
(2) For Set, if we want to find an element quickly, we can use HashSet; if we need the output elements to have a definite order, we can use LinkedHashSet or TreeSet.
(3) For Queen, there are different application scenarios according to their characteristics. Specifically, Queue follows the “First in, First out” Policy. Deque can add or remove elements at the head or tail. The Remove() method of PriorityQueue will always remove the smallest element.
(4) For Map, If we need to access keys in order, TreeMap or LinkedHashMap is good. If there is no requirement for visiting orders, HashMap is better to save operation time.
Word count: 1292
References
1.Eck, D. J. (2019). Introduction to Programming Using Java.
http://math.hws.edu/javanotes
2.Horstmann, C. S. 2019. Core Java Volume I–Fundamentals (11th ed.). Pearson.