Collection framework in Java

Beknazar
7 min readJan 28, 2021

--

The collection framework is a framework to work with a collection of data in Java.

If you are new to programming then you need to start with Array which is a core data structure to work with a collection of data.

The collection framework is a set of interfaces and concrete classes. We can use it to store and manipulate a group of objects. It supports built-in sorting and searching algorithms. We can say that the collection framework is ready APIS for various data structures. The collection framework is in core java libraries. We just need to import them from java.util package.

Before we get started to discuss each collection separately, There are a few common features you need to know:

  • Collections can work(hold) only with Objects, primitives are not allowed.
  • Collections framework heavily utilize generics concept. For example, if you want to create ArrayList which can hold a collection of Strings, we can do it like this: ArrayList<String> list = new ArrayList<>();
    If you don’t specify a type it will assume as a collection of Objects.
  • It’s common to use polymorphic way of creating instances from collections. ex: List<String> list = new ArrayList<>();

List interface

As you can see in the above scheme, List is an interface that has 3 concrete classes. The List is a dynamic size ordered data structure. It allows duplicate values.

Basically, collections allow us to work with a group of data. The same way as array does. Let’s see the differences in creating array and List.

// import statements and valid code aboveint[] numberArray = new int[3];
numberArray[0] = 1;
numberArray[1] = 3;
numberArray[2] = 7;
System.out.println(Arrays.toString(numberArray)); // [1, 3, 7]
List<Integer> colorsList = new ArrayList<>();
colorsList.add(1);
colorsList.add(3);
colorsList.add(4);
System.out.println(colorsList); // [1, 3, 7]

In the above example, we created an array of int with values [1, 2, 3] and we created a List of Integer with values [1, 2, 3].

  1. When we created an array of int we specify a size because an array is a fixed-size data structure, however, we don’t specify a size in the collections. We can think that collections have a dynamic size.
  2. As you can see in the List example to specify the data type of it we need to use <> operator. It uses generics in java.
  3. An array can be created as a primitive data type but Collections do not allow primitives, they can hold only objects.

The list is an interface so it has many abstract methods and a List has three concrete classes that implement it. Why do we need three different implementations of the List? Because the way they implemented is different each implementation can be good for a specific scenario. Specifically ArrayList and LinkedList implementations.

ArrayList is the implementation of List. It’s based on an array internally and it can grow and shrink dynamically — resizable-array implementation. ArrayList not synchronized(it’s not threaded safe). If multiple threads will manipulate with the same ArrayList instance, java does not guarantee that it will behave as expected. It’s good to use when you don’t have to change(adding & removing) the number of elements inside significantly and it’s good for accessing elements by index. Why? Because it’s based on Array internally. Read this article on Data Structures for more information.

LinkedList implementation is based on a doubly-linked list. Because it’s based on a linked list internally, it has a dynamic size by nature of data structure. It’s not synchronized. It’s good to use when you don’t know the exact number of elements in advance and you don’t access different elements by index often. Why? Because it’s based doubly-linked list internally.

Vector. This class is roughly equivalent to ArrayList, except that it is synchronized.

Well, we discussed three main implementations of the List interface. Now, you just need to learn the methods(APIs) of List and you are good to go.

I used ArrayList implementation in the above example. It will be the same for all other implementations.

Set Interface

Set does not allow duplicate values. There is no get(index) method in the Set interface. Overall, the performance of Set implementation classes is very high. It has three main implementations: HashSet, LinkedHashSet, TreeSet.

HashSet is the implementation of a Set interface. It based on hast table data structure. It does not guarantee insertion or iteration order. It allows one null value. HashSet has a constant-time performance. It doesn’t matter how large is collection, it will take constant time to perform basic operations as add, remove, contains, and size. It’s incredible! HashSet is good when you don’t care about ordering or sorting the data and If you don’t need to read by index.

LinkedHashSet is exactly similar to HashSet except it will maintain insertion order. LinkedHashSet also guarantees constant-time performance. Performance is likely to be just slightly below that of HashSet, due to the added expense of maintaining the linked list.

TreeSet is ordered set implementation. It follows the natural ordering. What is natural ordering? Let’s first discuss the order itself. The data can be ordered differently. For example, it can be ordered alphabetically if it’s a collection of strings or it can be in ascending order if it’s a collection of numbers. And so on. If it’s a collection of custom objects, how it should be ordered? So in order to resolve this problem “How to order things?” Java has a Comparable interface which has only one method compareTo. Every object that should be ordered can implement this interface and all other mechanisms of ordering in Java will be able to order your data. The same pattern for our TreeSet — it will order data based on the compareTo method of the set data type.

Queue, Stack, and Dequeue

These collections are designed for holding elements prior to processing.

Queue is a First In First Out data structure. To understand a Queue data structure, you can always think about people waiting in the queue in the coffee shop. Who comes first will get served first and will be out of the queue first.

offer(e) adds to the back, poll() removes from the head

There are three main methods to work with the Queue interface:

  1. offer(e) adds a new element to the back of the queue if possible otherwise. it will return false.
  2. poll() method will remove the element from the head and return it.
  3. peek() method returns, but do not remove, the head of the queue.

Stack is the Last In First Out data structure. Java does not have Stack interface, it has a Stack class. Most of the time stack(LIFO) data structure is implemented by using Dequeue.

Think of a stack of plates. We always put a plate on top of the stack and when we need to take it from the top as well.

Photo by Mick Haupt on Unsplash

There are three main methods to work with the Stack:

  1. push(e) Pushes an item onto the top of this stack.
  2. pop() Removes the object at the top of this stack and returns that object as the value of this function.
  3. peek() method returns an object from the top, but do not remove it.

Dequeue is an interface that can behave as a Queue and as a Stack data structure as well.

Map interface

The map is a key value based data structure. In some programming languages, it’s known as a dictionary. Keys are unique in the map. The map is part of the collection framework(it does not extend Collection or Iterable).

Diagram of the Map and some of its implementations

HashMap class is a hash table based implementation of the Map:
1. Does not maintain any order.
2. Allows one null as a key and any number of null as a value.
3. Unsynchronized.

Hashtable. This class implements a hash table, which maps keys to values. Any non-null an object can be used as a key or as a value:
1. Does not maintain any order.
2. Does not allow null as key and value.
3. Synchronized.

LinkedHashMap class is almost the same as HashMap except it does maintain insertion order.

TreeMap class — Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

All the links and references are from Java 8.

--

--