Введение в коллекции Java
Собственно говоря, зачем эта статья и для кого? Для тех, кто только начинает свой путь в изучении Java. В этой статье я не буду сильно углубляться в детали каждой коллекции в отдельности, ведь чтобы начать ими пользоваться, достаточно хотя бы на базовом уровне понять, что это такое и с чем это «едят».
Следует начать с определения, что же такое коллекция в Java?
Википедия нам даёт следующее определение:
«Коллекция — программный объект, содержащий в себе, тем или иным образом, набор значений одного или различных типов, и позволяющий обращаться к этим значениям».
Но я бы сказал проще, коллекция — это по своей сути обычный контейнер, в котором хранятся элементы, а также коллекция позволяет нам выполнять над этими элементами некоторые полезные действия. Обычно коллекции используются для хранения группы однотипных объектов, подлежащих обработке с помощью определенной логики.
Например:
Представим себе ситуацию, когда обычный массив нам не очень поможет. У нас есть какой-либо класс, у которого есть метод, который принимает число и должен его у себя сохранить. Ведь мы не знаем, сколько раз будут вызывать наш метод и сколько чисел будет храниться в нашем классе.
Тут то и приходят на помощь коллекции, ведь они умеют динамически увеличиваться. Ниже можно увидеть как это выглядит в коде:
public class GradeCounter {
private static List 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 + " "));
}
} Почему я присваиваю полю List
Вкратце: т.к. у нас будет добавление только в конец, а LinkedList — это двунаправленный список, то в начало или конец операция добавления элемента имеет константную O (1) сложность.
Вот ещё наглядный пример, у нас есть определенная иерархия, на вершине которой есть интерфейс Eatable, а также классы, которые его реализуют. Логика та же, что и в примере выше: есть два метода, один, который принимает класс, реализующий Eatable, и добавляет его в коллекцию, а другой, который вызывает метод eat в каждом классе.
Реализация ниже:
public class SomeClassName {
private static List 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");
}
} p.s. Опустим момент того, что эти классы можно было бы сделать immutable, здесь больше важна идея коллекций.
Ниже показана общая иерархия коллекций:
Иерархия коллекций в Java
Следует отметить, что раз ArrayList, LinkedList, Vector и Stack реализуют интерфейс List, то они реализуют все методы, объявленные в List.
Перечислю основные из них:
add (E e) — добавление элемента в конец коллекции.
addAll (Collection c) — добавление в конец всех элементов другой коллекции.
clear () — удаление всех элементов из коллекции.
contains (Object o) — возвращает результат того, есть ли объект в коллекции.
get (int index) — возвращает элемент по индексу.
indexOf (Object o) — возвращает индекс элемента в коллекции.
remove (int index) — удаление по индексу.
remove (Object o) — удаление объекта.
isEmpty () — проверка на то, пустая ли коллекция.
size () — возвращает фактическое количество элементов в коллекции.
iterator () — возвращает Iterator
, который позволяет безопасно итерироваться по коллекции и модифицировать её в цикле.
Основные реализации List:
ArrayList — коллекция, в основе которой лежит обычный массив. Но у ArrayList«а есть специальный механизм по работе с ним:
Когда внутренний массив заполняется, ArrayList создает внутри себя новый массив, размер которого рассчитывается по специальной формуле: Размер нового массива = (размер старого массива * 1.5) + 1.
Затем все данные копируются из старого массива в новый.
Старый массив удаляется сборщиком мусора.
Когда следует использовать: из-за особенностей своей реализации он предоставляет быстрый доступ к данным, так как мы можем получить любой элемент практически мгновенно, зная его индекс, ведь внутри обычный массив. Однако добавление и удаление элементов, особенно в середине списка могут быть относительно медленными, так как при этом приходится сдвигать последующие элементы. В целом, если вам часто требуется обращаться к элементам по индексу, то лучше выбрать ArrayList, однако если основные операции — это вставка и удаление в середине, то лучше использовать LinkedList, речь о котором пойдёт дальше.
LinkedList отличается от ArrayList своим внутреннем строением. Помимо того, что LinkedList реализует интерфейс List, так ещё и интерфейс Deque. «Под капотом» лежит двунаправленный список, элементы которого являются Node.
Node — это класс, который хранит в себе какие-либо данные и указатели на следующую ноду и на предыдущую. Вот код реализации Node непосредственно из класса LinkedList:
Node from LinkedList
То есть, при удалении или добавлении элемента необходимо лишь «переприсвоить» ссылки на следующий и предыдущий элемент, что быстрее, нежели сдвигать элементы массива в ArrayList.
Однако, нужно сказать о главном, по моему скромному мнению, минусе этой коллекции. Это отсутствие мгновенного доступа по индексу, как это в ArrayList. Метод get (int index) у этого класса есть, ведь он же реализует List, однако в реальности там обычный цикл, который передвигается по ссылкам, увеличивая свой счётчик индекса, пока не станет равным искомому. Поэтому в общем случае, сложность этой операции O (n), когда в ArrayList O (1).
В общем случае, чаще пользуются ArrayList, так как операция сдвига элементов массива выполняется очень быстрой низкоуровневой операцией System.arraycopy (). Однако стоит отметить, что если вы с помощью итератора проходитесь по списку LinkedList и постоянно вставляете новые элементы (или удаляете), то это быстрее чем с ArrayList.
Vector
Vector является реализацией динамического массива, как и ArrayList, однако он содержит следующие недостатки:
Содержит много устаревших методов, которые не являются частью Collection Framework.
Он очень медленный, так как методы синхронизированы.
Увеличивает размер массива по умолчанию в два раза, когда ArrayList увеличивает размер массива на 50%. В зависимости от использования, мы можем получить большой удар по производительности.
Если вы не работаете в многопоточной среде, то стоит посмотреть в сторону «ArrayList».
Stack
Этот класс является подклассом Vector, который реализует стандартный стек LIFO (last-in, first-out). Стек включает все методы из класса Vector, однако добавляет свои специфические для реализации «классического» стека.
В нем определены следующие методы помимо тех, которые из класса Vector:
peek () — возвращает элемент на верхушке стека, при этом не удаляя его.
pop () — то же самое, что и peek, однако помимо возвращения ещё и удаляет.
push (E e) — позволяет положить элемент на верхушку стека.
Стек довольно редко используется, однако в некоторых задачах он заметно облегчает нам жизнь, допустим, для такой
Приведу реализацию на стеке:
public static boolean balancedParenthesis(String inputStr) {
Stack 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());
} Надеюсь, все стало немного понятнее. В следующая частях напишу про реализации Queue, Set и Map.
