Actually, why is this article and for whom? For those who are just starting their journey in learning Java. In this article, I will not delve into the details of each collection separately, because in order to start using them, it is enough to understand at least on a basic level what it is and what it is “eaten with”.

Should we start by defining what is a collection in Java?

Wikipedia gives us the following definition:

“A collection is a program object that contains, in one way or another, a set of values ​​of one or different types, and that allows you to access these values.”

But I would say more simply that a collection is essentially a regular container that stores elements, and a collection allows us to perform some useful actions on these elements. Collections are usually used to store a group of objects of the same type, subject to processing with the help of a certain logic.

Example:

Let’s imagine a situation when an ordinary array will not help us much. We have some class that has a method that takes a number and should store it in itself. After all, we do not know how many times our method will be called and how many numbers will be stored in our class.

This is where collections come to the rescue, because they can dynamically increase. Below you can see how it looks in the code:

public class GradeCounter {
   private static List<Integer> grades;

   public static void addGrade(int grade) {
       if (grades == null) {
           grades = new LinkedList<>();
       }

       if (grade >= 0 && grade <= 10) {
           grades.add(grade);
       }
   }

   public static void printGrades() {
       grades.forEach(e -> System.out.print(e + " "));
   }
}

Why am I providing the List field grades implementation of LinkedList will become clearer when I talk about all List implementations in general and their pros and cons.

Briefly: because we will add only to the end, and LinkedList is a bidirectional list, so the operation of adding an element to the beginning or end has a constant O(1) complexity.

Here is another visual example, we have a certain hierarchy, at the top of which is the Eatable interface, as well as the classes that implement it. The logic is the same as in the example above: there are two methods, one that takes a class that implements Eatable and adds it to the collection, and another that calls the eat method on each class.

The implementation is below:

public class SomeClassName {
   private static List<Eatable> eatableList;

   public static void addEatable(Eatable e) {
       if (eatableList == null) {
           eatableList = new LinkedList<>();
       }
       eatableList.add(e);
   }

   public static void printEatableList() {
       eatableList.forEach(Eatable::eat);
   }
}

interface Eatable {
   void eat();
}

class Cat implements Eatable {
   @Override
   public void eat() {
       System.out.println("I eat fish");
   }
}

class Dragonfly implements Eatable {
   @Override
   public void eat() {
       System.out.println("I eat insects");
   }
}

ps Let’s omit the point that these classes could be made casual, the idea of ​​collections is more important here.

Below is a general collection hierarchy:

It should be noted that if ArrayList, LinkedList, Vector, and Stack implement the List interface, they implement all methods declared in List.

I will list the main ones:

1. add(E e) – adding an element to the end of the collection.

2. addAll(Collection c) – adding all elements of another collection to the end.

3. clear() – delete all elements of the collection.

4. contains(Object o) – returns the result of whether the object is in the collection.

5. get(int index) – returns the element by index.

6. indexOf(Object o) – returns the index of the element in the collection.

7. remove(int index) – removal by index.

8. remove(Object o) – object removal.

9. isEmpty() – check if the collection is empty.

10. size() – returns the actual number of elements in the collection.

11. iterator() – returns an Iteratorwhich allows you to safely iterate over a collection and modify it in a loop.

The main implementations of List:

ArrayList – A collection based on a regular array. But ArrayList has a special mechanism for working with it:

1. When the internal array is filled, ArrayList creates a new array in itself, the size of which is calculated according to a special formula: Size of the new array = (size of the old array * 1.5) + 1.

2. Then all the data is copied from the old array to the new one.

3. The old array is removed by the garbage collector.

When to use: due to the peculiarities of its implementation, it provides fast access to data, because we can get any element almost instantly, knowing its index, because inside it is a regular array. However, adding and removing items, especially in the middle of the list, can be relatively slow, as you have to move the following items. In general, if you often need to access elements by index, it is better to choose ArrayList, but if the main operations are insertion and deletion in the middle, then it is better to use LinkedList, which will be discussed later.

LinkedList differs from ArrayList in its internal structure. In addition to LinkedList implementing the List interface, it also implements the Deque interface. “Under the hood” is a bidirectional list whose elements are Node.

Node is a class that stores any data and pointers to the next node and to the previous one. Here is the Node implementation code directly from the LinkedList class:

That is, when removing or adding an element, it is only necessary to “reassign” the reference to the next and previous element, which is faster than moving the elements of the array in the ArrayList.

However, I must say about the main, in my humble opinion, minus of this collection. It lacks instant access by index like ArrayList. This class has a get(int index) method, because it also implements a List, but in fact there is a regular loop that moves by links, increasing its index counter until it becomes equal to the desired one. Therefore, in the general case, the complexity of this operation is O(n), when in ArrayList it is O(1).

In the general case, ArrayList is more often used, since the operation of shifting the elements of the array is performed by a very fast low-level operation System.arraycopy(). However, it is worth noting that if you use an iterator to traverse a LinkedList and constantly insert new elements (or remove), it is faster than with an ArrayList.

Vector

Vector is an implementation of a dynamic array, just like ArrayList, but it has the following disadvantages:

1. Contains many deprecated methods that are part of the Collection Framework.

2. It is very slow because the methods are synchronized.

3. Doubles the size of the default array when ArrayList increases the size of the array by 50%. Depending on the usage, we can get a big performance hit.

If you are not working in a multi-threaded environment, then you should look towards “ArrayList”.

Stack

This class is a subclass of Vector that implements a standard LIFO (last-in, first-out) stack. The stack includes all methods of the Vector class, but adds its own specific ones for implementing a “classic” stack.

It defines the following methods, in addition to those from the Vector class:

1. peek() – returns the element at the top of the stack without removing it.

2. pop() is the same as peek, but in addition to returning, it also removes.

3. push(E e) – allows you to put an element on top of the stack.

The stack is used quite rarely, but in some tasks it makes our life noticeably easier, let’s say for such.

I will put the implementation on the stack:

public static boolean balancedParenthesis(String inputStr) {
   Stack<Character> stack = new Stack<>();
   char[] charArray = inputStr.toCharArray();
   for (char current : charArray) {
       if (current == '{' || current == '[' || current == '(') {
           stack.push(current);
           continue;
       }
       if (stack.isEmpty()) {
           return false;
       }
       char popChar;
       switch (current) {
           case ')' -> {
               popChar = stack.pop();
               if (popChar == '{' || popChar == '[') {
                   return false;
               }
           }
           case '}' -> {
               popChar = stack.pop();
               if (popChar == '(' || popChar == '[') {
                   return false;
               }
           }
           case ']' -> {
               popChar = stack.pop();
               if (popChar == '(' || popChar == '{') {
                   return false;
               }
           }
       }
   }
   return (stack.isEmpty());
}

I hope everything has become a little clearer. In the following parts, I will write Queue, Set and Map for sale.