Dynamic Arrays in Java

When creating programs of varying degrees of complexity, each developer uses many types of data, including arrays. This structure is well suited for storing a set of the same type, gives great performance, and is generally convenient. A significant disadvantage of arrays is their static nature: you must pre-set their size. However, programmers are not yet able to predict the future (unless, of course, AI appears that will process information incredibly quickly and be able to predict any events). For this reason, we created a structure that can change the size at the time the program is running. It's called a dynamic array .

Dynamic arrays in CodeGym course

Very intelligibly and clearly this topic is revealed at level 7 and partially at level 8 of the CodeGym course in the Java Syntax quest. Over the course of several lectures and as many as 18 tasks, key issues, types of dynamic arrays and the difference between them, including performance, are revealed. This topic is the most important, since dynamic arrays save the developer from depression, headaches and save an incredible amount of time.

What is a dynamic array?

A dynamic array is an array that can change its size during program execution. In Java, this role is mainly played by the ArrayList and LinkedList classes. Unlike arrays, ArrayList and LinkedList contain only reference data types, which means that only objects can be stored in them. Fortunately, Java has autoboxing and autoboxing mechanisms that allow you to store primitive types in dynamic arrays. Like a static array, a dynamic array is homogeneous, that is, it can store a single type of data. However, thanks to the inheritance mechanism and the competent use of interfaces, it is possible to store in one dynamic array a whole range of various classes that are inherited from one common one, but more on that below. That is, a static array works like this: Aa dynamic array in Java works like this (we continue the scheme from the third step): Java uses a special native function to copy an array, so such a “move” is not very expensive.

Why do we need a dynamic array?

A dynamic array in Java is used to handle sets of homogeneous data whose size is unknown at the time the program is written. For example, you might want to cache data for every client that your application is currently using. It is impossible to predict the number of such clients in advance. Without dynamic arrays, this problem can be solved by the following options:

1. Create a large array that will cover the need with 100% probability;
2. Create a static array that will act as a buffer;
3. Apply other dynamic structures, such as sets.

The first option is suitable only in the case of a strictly limited range. In other cases, such an array will take up a large amount of memory space, which is as inefficient as possible. The second will require the implementation of additional mechanics for clearing the buffer, reading, and so on. The third also has disadvantages due to the difference in functionality.

What makes a dynamic array work in Java

In the Java language, the ArrayList and LinkedList classes act as a dynamic array. The most commonly used is ArrayList, as it performs the role of a classic array, unlike LinkedList, which implements the concept of a doubly linked list. It will be discussed a little later.

ArrayList, LinkedList - concepts and rules of work

ArrayList is a classic array that can expand at the time of program execution. It is based on a regular array: its size when created is 10 elements. As the size increases, the capacity increases. Rules by which ArrayList works:

• Just like a static array, indexed from 0;
• Insertion at the end and access by index are very fast - O (1);
• To insert an element at the beginning or in the middle, you will need to copy all the elements one cell to the right, and then insert the new element at the desired position;
• Access by value depends on the number of elements - O(n);
• Unlike the classic array, it can store null;

In the case of LinkedList, things are a little more complicated: it is based on a doubly linked list. That is, structurally, this Java dynamic array is a number of scattered objects that refer to each other. It's easier to explain with pictures. Inside the LinkedList, we have the main object - Head, which stores information about the number of elements, as well as a link to the first and last elements: Now the field size = 0is , firstand last = null. Each element that is added to this list is the contents of a separate internal object. Let's add an element Johnny: Now we have a node with the value “Johnny”. For the main element, the first and last element references point to the new node. This object also has links to the previous and next elements. The link to the previous one will always be null, since this is the first element, and the link to the next one will always be null, because it does not exist yet. Let's fix it: A new element has been added, with the value "Watson", which has become the second one. Note that the first element has a field nextpointing to the next element, while the new element has a field previouspointing to the previous one. For the main element, the link to the last element now points to the new node. The following diagram shows how to add elements to the middle of a list: A new element "Hamish" has been added. To insert it in the middle of the list, it is enough to reassign the references to the elements, as shown in the figure. These illustrations explain how a doubly linked list works at the top level without going into too much detail. Summing up the story about LinkedList, we can derive several rules for its operation:

• Just like an array, indexed from 0;
• Access to the first and last element does not depend on the number of elements - O (1);
• Getting an element by index, inserting or deleting from the middle of the list depends on the number of elements - O (n);
• You can use the iterator mechanism: then the insertion and deletion will occur in constant time;
• Unlike the classic array, it can store null.

Code examples

Let's go through some examples. The code snippets include examples for both ArrayList and LinkedList.

Creation

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

Adding an element

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

At first glance, the add()AND methods addLast()perform the same functionality, but the method add()came to LinkedList from the interface List, and the method addLastcame from the interface Deque. LinkedList implements both of these interfaces. It is good practice in this case to use whichever method is more appropriate for the context. If LinkedList is used as a queue, then it is best to use the addLast. If LinkedList is being used as a list, it would be appropriate to use add().

Removing an element

// Удаление element по индексу
arrayList.remove(0);
// Удаление element по значению
arrayList.remove("Johnny");

// Удаление первого element в списке
linkedList.removeFirst();
// Удаление первого element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего element в списке
linkedList.removeLast();
// Удаление первого вхождения element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

If an object is deleted by index, the method returns the deleted object. If the object is removed by value (or the first or last element is removed from the LinkedList), the method returns true if the object is found and removed, false otherwise.

Accessing an element and searching in a list

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего element
String lastLinkedElement = linkedList.getLast();

// Поиск element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

Bypass in a loop

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

Here it is worth saying a few words about the search. Many novice developers, when searching for an element in the list, start the search in a loop, comparing all elements with the desired one, despite the presence of methods indexOf()and lastIndexOf(). You can also use the method contains()to get the fact that an element is in the list:

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

Links to further reading

1. Here is a great article about removing elements from an ArrayList. Due to the fact that this is a dynamic Java array , there are many subtleties in removing elements.
2. Here, the operation of ArrayList is illustrated in detail.
3. A little more about LinkedList.
4. A couple of Habr articles about ArrayList and LinkedList .