Collections are an important part of most programming languages. From the humble Array to the complex HashMap, most languages that have even a passing relationship with objects and object oriented structures will have at least a few types of collections. Collections can be very useful and have many applications, but one of the most important parts of using collections is understanding how to access a given item. The first part is simple, you just call the collection with the appropriate index for the item you want. But how do you know where in the collection your item is? This is where things get complex. Many programming classes will cover the complexities of how you might write your own search algorithms and which one is most efficient. But searching and sorting collections are fairly common occurrences, so library functions already exist to perform many common types of searches and sorting. While some situations may require you to write your own sort functions, it is also useful to understand some basic sorting functions so you don’t try to re-invent the wheel. We will discuss sorting in several languages, but to start with let’s talk about Java.
Java has many useful collection types, that fall into a few main categories: Lists, Sets, and Maps. There are a few others, but some of those are less commonly used, so for now we will stick to the types you will most often encounter. To start with, let’s look at the difference between Lists and Sets. The basic difference between a List and a Set is that a Set has no duplicates or repeats. But in Java this means that a Set is actually built differently than a List. For our example we will use an ArrayList, but most Lists will have similar methods. Items in an ArrayList are stored sequentially, in a certain order. They have indexes starting at 0 and incrementing by 1. If you iterate over an ArrayList you will encounter the items in a specific, expected order. But Sets are not stored in any specific sequence. They do not have numerical indexes like a List. A HashSet, for example, may contain many items, but no matter what order they are added, the HashMap will not be organized. Lists and Sets are both important, but serve different purposes. For example, here’s how we set up an ArrayList:
ArrayList<String> fruits_list = new ArrayList<String();
fruits_list.add(“Apple”);
fruits_list.add(“Pear”);
fruits_list.add(“Orange”);
Now let’s create a HashSet:
HashSet<String> fruits_set = new HashSet<String();
fruits_set.add(“Apple”);
fruits_set.add(“Pear”);
fruits_set.add(“Orange”);
These are very similar, which is to be expected. They both have many of the same methods, but let’s discuss why sometimes Sets might be more useful than Lists. If we have a List containing several kinds of fruit, and we want to check if it includes another type of fruit, there is a simple method, contains:
fruits_list.contains(“Apple”);
This works, and it will tell us that the list does contain the word “Apple”. But it has to check every single item in the list. Our list is very small, but with a large list this could have a significant impact on the run time. This is what makes Sets special. Because Sets are not ordered they are more like a HashMap without values. Here’s we could perform the same check using a HashSet:
fruits_set.contains(“Apple”);
This looks the same, but in fact the set is only checking if that key is assigned a place in the set, and does not need to check every item in the set. This version has a much faster runtime, and is the preferred method of checking for the existence of an item.
Checking every item in a Lists can be a hassle, and Sets are just one of the ways of getting around that. Sorting is another useful way to find an item. In Java, Lists have a built in method called sort(), which has a default functionality for primitive types:
ArrayList<String> counts = new ArrayList<String();
counts.add(5);
counts.add(2);
counts.add(9);
Collections.sort(counts);
Originally counts would be in the order [5,2,9], but after sorting will be [2,5,9]. This makes sense for numbers, but what about strings? As it happens there is also default functionality for sorting strings. If we run a sort on our earlier list of fruits:
Collections.sort(fruits_list);
It will now read [“Apple”,”Orange”,”Pear”]. The default sort fo strings will sort them alphabetically. It is possible to use the sort() method to sort in more complex ways by writing a custom Comparator, but to explain that might require it’s own article.
Top comments (0)