Basic Data Structures in Java— Arrays, Lists, Sets, Stacks, Queues, and Maps

I will cover the data structures including Arrays, Lists, Sets, Queues, and Maps here. Depending on whether the order of items matters, how items are sorted, and whether the list can contain duplicates, we can choose the suitable collection type that fits our needs.

Data Structure is a collection of values that allows us to organize the data, so we can go back to that data and retrieve the data. We can say the collection is a database, which keeps data in the heap memory (and on disk).

I would summarize the characteristics of each data structure first before providing a practical example and applying each of these data structures to the example.

Arrays:

Arrays organize items sequentially, one after another in memory. Arrays are immutable which means they are unchangeable, and arrays allow duplicate elements. Arrays are good for fast lookups because each item is indexed (zero-based), fast push/pop, and the list is ordered. However, the array is fixed size, which means that you have to declare the number of the array list items initially when you first create the array, and the default values are assigned for each element automatically upon creation like 0 and null. Otherwise, if we do not know the size yet or the size may grow and shrink, we use collections instead in such a situation.

Lists:

Lists are flexible in size with the ability to grow and shrink as needed, it also allows fast insertion and deletion, and the list is ordered and allows duplicates. The most common list is called ArrayList. A list is like a shopping list, you can add the item you want at the end of the list, remove an item, or fetch an item from the list by getting its index. Unlike arrays, lists are empty when instantiated, you need to add the values in the list; otherwise, the list itself is empty upon creation.

• an ordered collection
• allows duplicate entries
• access using the index

LinkedList:

• read/add/remove from both the beginning and/or end of the LinkedList
• not a good structure for iteration

Sets:

Sets have a slightly different purpose than lists. The list is an ordered collection while the set is an unordered collection, the list allows duplicates while the set does not. A set is a collection that cannot contain duplicates. If you insert a duplicate in the set, it will replace the older value. Any implementation of a set in Java will only contain unique elements. Unlike the list that maintains the insertion order of elements, items within a set cannot be accessed by index, only by iteration, you can not actually pull something out by its index number; instead, iterating and check if it exists. Sets are flexible in size but are empty when instantiated, you need to add the values in the set; otherwise, the set itself is empty upon creation. Popular implementations of the set include HashSet (Order not assured), LinkedHashSet (By sequence), and TreeSet (Automatic sorting).

• similar to the List
• does not allow duplicates

Stacks

• First-In-Last_out (FILO)
• Call Stack: an execution stack to keep track of its place
• Stack Overflow: buffer overflow error that occurs when excessive memory space in the call stack has been allocated to that stack.
• Useful cases: “Undo/Redo” in word processing, stack trace, browser history

Queues

• First-In-First-Out (FIFO)
• Adding is called enqueue, and Removing is called dequeue
• We use Queue when we intend to sort the data before processing, or we intend to add or remove elements in a specific order.
• Useful cases: Buffers in networking, Scheduling in Operating Systems

Maps:

A map is a data structure that contains key-value pairs like a dictionary with its words and definitions (in fact it is called a dictionary in Python and an object in JavaScript). Maps are not part of the collection. The map associates values with unique keys which means it may not have duplicate keys, but duplicate values are fine. Key in all Maps is unique. Add a duplicate key, then it will be overwritten. Maps are flexible in size but are empty when instantiated, you need to add the values in the map; otherwise, the map itself is empty upon creation. Popular implementations of the map include HashMap (Order not assured), LinkedHashMap (By sequence), and TreeMap (Automatic sorting).

• stores every object with a key (key-value collection)
• HashMap: does not maintain insertion order, O(1)
• LinkedHashMap: maintain insertion order, O(1)
• TreeMap: sorted ascending order based on keys, not elements, O(log N)

Photo by Procreator UX Design Studio on Unsplash

Coding Example:

I would like to create some data structures that store my personal data while applying the topics we have covered in the lesson.

Array:

Since I would like to only store my top three hobbies, I know the fixed size of the array.

String[] topThreeHobbies = {“Eat”, “Sleep”, “Code”};

Lists:

I am using ArrayList as an example for creating my bucket list and using the iterator to remove the element once I complete it.

List<String> bucketList = new ArrayList<>();
bucketList.add("Visit Alaska");
bucketList.add("Visit Hawaii");
bucketList.add("Visit China");
bucketList.set(2, "Visit Japan");   //replace visit China
for (String list : bucketList) {
System.out.println(list);
}

Sets:

​While a set cannot contain duplicate elements, my example here will be logging the date when I learn to code as I know that each date is unique, no date can repeat. It would also be helpful if I want to check whether a specific date I have studied for coding or not, I can iterate through the set and check if the data exists. I will use LinkedHashSet here for my example, since it is ordered, and elements iterate and will print in insertion order.

Set<String> codingJournal = new LinkedHashSet<>();
codingJournal.add("2/10/2021");
codingJournal.add("5/11/2021");
codingJournal.add("7/31/2021");
//Check whether have studied on that date
System.out.println(codingJournal.contains("7/30/2021"));    //false
System.out.println(codingJournal.contains("7/31/2021"));    //true
//Traversing the LinkedHashSet
Iterator<String> trace = codingJournal.iterator();
while(trace.hasNext()) {                 //elements iterate in insertion order
System.out.println(trace.next());   //printout dates that have logged for learning to code
}

Maps:

I am using HashMap as an example to store the languages I have learned and the classes I have taken at BU in key-value pairs. Since there will be more classes I take and more languages I learn, then I can add more values as the list to the specific key accordingly. Also, items are in unpredictable order in HashMap, which is fine because I do not need an ordered structure for the purpose of my example here.

Map<String, ArrayList<String>> BU = new HashMap<>();
ArrayList<String> languages = new ArrayList<>();
languages.add("Java");
languages.add("SQL");
ArrayList<String> classes = new ArrayList<>();
classes.add("CS520");
classes.add("CS669");
BU.put("Languages", languages);
BU.put("Classes", classes);
System.out.println(BU.get("Languages"));    //[Java, SQL]
System.out.println(BU.get("Classes"));  //[CS520, CS669]