Докладний аналіз класу ArrayList [Частина 1]

У цій статті буде детально розглянутий клас ArrayList з каркасу колекцій Collections Framework, який, мабуть, є найпростішим для розуміння, оскільки він заснований на базі звичайного масиву. Практично напевно на співбесіді Вам поставлять питання про цей клас та його реалізацію в Java. У другій частині ми розберемо методи, що залишабося, і напишемо свою реалізацію динамічного масиву для чисел. Клас ArrayList успадковується від класу AbstractList і реалізує такі інтерфейси: List, RandomAccess, Cloneable, Serializable. Докладний аналіз класу ArrayList [Частина 2] У класі ArrayList підтримуються динамічні масиви, які можуть збільшуватися при необхідності. Його необхідність та ефективність пояснюється тим, що звичайний масив має фіксовану довжину: після того, як він створений, він не може збільшуватися або зменшуватися, що накладає обмеження в тому випадку, якщо невідомо, наскільки великий масив буде потрібно. Фактично, клас ArrayList є списковий масив об'єктних посилань змінної довжини. Важливо розуміти, що автоматичного зменшення розміру (кількість осередків) внутрішнього масиву при видаленні елементів із нього не відбувається. Насправді зменшується значення змінноїsizeяка вказує на кількість дійсно наявних у масиві елементів. Допустимо, ми створюємо новий об'єкт класу ArrayList і додаємо туди 5 елементів. За промовчанням створюється масив на 10 елементів. В даному випадку, так званий capacity (розмір/обсяг) нашого об'єкта дорівнюватиме 10, але значення змінної sizeдорівнюватиме п'яти. І при видаленні елементів ми бачимо зміни значення змінної size, оскільки отримати доступ до внутрішнього масиву класу ArrayList і дізнатися про його довжину .lengthми не можемо. Розмір можна зменшити за допомогою додаткового методу trimToSize(), про який піде далі. Розглянемо поля класу.

• Поле, що відповідає за обсяг динамічного масиву за замовчуванням:

  private static final int DEFAULT_CAPACITY = 10

  При створенні нового об'єкта new ArrayList<>() (конструктор без параметрів) створюється всередині масив на 10 елементів.

• Поле, де зберігаються всі елементи колекції:

  transient Object[] elementData

  Позначено ключовим словом transient– поле не записується до потоку байт при застосуванні стандартного алгоритму серіалізації. Варто зазначити, що поле не відзначено ключовим словом private, а зроблено це для того, щоб полегшити доступ до цього поля вкладених класів (наприклад, SubList).

• Поле-лічильник, яке зберігає в собі кількість елементів, що дійсно знаходяться в масиві:

  private int size

  Значення збільшується/зменшується під час виконання таких операцій, як вставка та видалення.

У класі є ще 3 поля, але вони є додатковими, тому розглядати їх сенсу немає. У класу є три конструктори:

1. public ArrayList()- Створює порожній списковий масив об'ємом в 10 елементів;
2. public ArrayList(Collection < ? extends E > c)– створює обліковий масив, що ініціалізується елементами з переданої колекції (якщо хочемо створити новий ArrayList на базі якоїсь колекції);
3. public ArrayList(int initialCapacity)- Створює списковий масив, що має початкову ємність. Якщо переданий параметр initialCapacity більше 0, то створюється масив зазначеного розміру (внутрішньому полю elementData присвоюється посилання новий масив типу Object розміром initialCapacity). Якщо параметр дорівнює 0, то створюється порожній масив. Якщо заданий параметр менше 0, то генерується виняток IllegalArgumentException.

Створення об'єкту

List < String> list = new ArrayList<>();

Щойно створений об'єкт listмістить властивості (поля) elementDataі size. Сховище значень elementDataне що інше, як масив певного типу (вказаного в generic – <>), у разі String[]. Якщо викликається конструктор без параметрів, за замовчуванням буде створено масив для 10 елементів типу Object (з приведенням до типу, зрозуміло). Додавання елементів Класичне додавання елементів до спискового масиву здійснюється за допомогою перевантажених варіантів методу add().

public boolean add(E элемент)

Що ж, додаємо: list.add("0"); Усередині даного методу відбувається виклик перевантаженого варіанта методу add(), позначений як private, який у свою чергу на вхід приймає три параметри: елемент, що додається, внутрішній масив і його розмір (size). У закритому методі відбувається перевірка: якщо переданий параметр розміру дорівнює довжині внутрішнього масиву (тобто масив заповнений), то масиву присвоюється результат виконання методу (методу grow(int minCapacity)передається поточне значення поля size + 1, тому необхідно врахувати елемент, що додається), в якому внутрішньому масиву надається посилання на новий створений масив, отриманий в результаті копіювання елементів вихідного масиву:

Arrays.copyOf(elementData, newCapacity(minCapacity))

Як другий параметр методу copyOfми вказуємо результат роботи методу newCapacity(int minCapacity), всередині якого здійснюється обчислення нового розміру масиву. Він обчислюється за такою формулою: int newCapacity = oldCapacity + (oldCapacity >> 1) Для масиву з розміром за умовчанням буде справедливо: >> 1– побитовий зсув праворуч на одиницю (оператор, який зменшує до його половини). По суті, означає розподіл на 2 у ступені 1. Виходить, що ми ділимо 10 на 2 і додаємо 10. Отже, нова ємність масиву дорівнює 15, але оскільки ми додаємо 11 елемент, то 15+1 = 16. Повернемося до нашого списку і припустимо, що ми вже додали до нього 10 елементів і пробуємо додати 11. Перевірка покаже, що місця у масиві немає. Відповідно створюється новий масив і викликається Arrays.copyOf, який у собі використовує системний метод System.arraycopy(). Або ось такий наочний приклад з однієї статті на JavaRush: Після всіх цих перевірок та збільшення розміру масиву при необхідності далі в закритому методі до add()кінця масив додається новий елемент, а поточний параметр sizeзбільшується на одиницю. Старий масив надалі буде оброблений збирачем сміття. Таким чином і працює динамічний масив: при додаванні елементів ми перевіряємо, чи є в ньому ще місце. Якщо місце є, ми просто додаємо елемент в кінець масиву. Під кінцем мається на увазі не останній осередок в масиві, а той осередок, який відповідає значенню size. Додали перший елемент масив, він поміщається в комірку з індексом [0]. Значення поля sizeвиросло на одиницю = 1. Додаємо наступний елемент: дивимося, щоsize = 1відповідно елемент поміщаємо в комірку з індексом [1] і так далі. Є перевантажений варіант методу із двома параметрами:

public void add(int index, E element)

Ми можемо вказати позицію (індекс) осередку, у якому хочемо додати елемент. Спочатку здійснюється перевірка коректності зазначеного значення індексу, оскільки є ймовірність, що буде вказано неправильний індекс, який буде вказувати на комірку, де нічого немає, або якої просто не існує. Перевірка індексів: index > size || index < 0– якщо зазначений індекс більший за поточний розмір масив або він менший за 0, то викидається виняток IndexOutOfBoundsException. Далі у разі потреби збільшується розмір масиву, аналогічно прикладу вище. Ви, напевно, чули, що при операціях додавання/видалення в масиві щось кудись зрушується (праворуч або ліворуч). Так ось, зсув здійснюється за допомогою копіювання масиву: System.arraycopy(elementData, index, elementData, index + 1, s - index); Усі елементи, що знаходяться праворуч від зазначеного індексу, будуть зрушуватись на одну позицію вправо (index+1). І лише після цього у внутрішній масив під зазначеним індексом додається новий елемент. Так як ми зрушабо частину масиву вправо на одиницю (новий масив не створюється), то необхідна нам комірка звільниться для запису. Посилання на старий масив стирається і надалі їй займеться garbage collector. Вставляємо "maserati" в комірку [3], яка вже зайнята: Таким чином, коли відбувається вставка елемента за індексом і при цьому в масиві немає вільних місць, то виклик System.arraycopy()трапиться двічі: перший в grow()другий в самому методі add(index, value), що явно позначиться на швидкості всієї операції додавання. У результаті, коли необхідно записати у внутрішній масив ще один елемент, а місця там немає, то всередині ArrayList відбувається:

• Створюється новий масив розміром, в 1.5 рази більше вихідного плюс один елемент.
• Усі елементи зі старого масиву копіюються в новий масив.
• Новий масив зберігається у внутрішній змінній об'єкту ArrayList, а старий масив оголошується сміттям.

Місткість об'єктів типу ArrayList можна збільшувати вручну за допомогою методу:

public void ensureCapacity(int minCapacity)

Збільшивши ємність масиву заздалегідь, можна уникнути додаткового перерозподілу оперативної пам'яті згодом. Метод збільшує розмір внутрішнього масиву, щоб у нього вмістилася кількість елементів, переданих у minCapacity. Метод ensureCapacity()не впливає на поле size, він впливає на capacity(розмір) внутрішнього масиву. Вкотре наголошую, що sizeй capacityрізні речі і дуже важливо їх не плутати! Якщо потрібно зменшити розмір базового масиву, на основі якого будується об'єкт типу ArrayList, до поточної кількості елементів, що дійсно зберігаються, слід викликати метод trimToSize(). Після видалення елементів з колекції size()покаже кількість дійсно існуючих елементів, аcapacityпри цьому не зменшиться! Припустимо: ми ввели 100 елементів, видалабо перші 50, sizeстане рівним 50, а ось capacityтак і залишиться 100. Щоб зменшити і capacityнеобхідно використовувати метод trimToSize(), який підганяє весь наш capacity до поточного size. Як підганяє? Копіює наш масив так, що там не залишається порожніх осередків (довжина нового масиву просто дорівнює полю size). Також додавати елементи до нашої колекції можна за допомогою методів addAll.

public boolean addAll(Collection< ? extends E> c)
public boolean addAll(int index, Collection< ? extends E> collection);

Перший варіант дозволяє додати всі елементи із вказаної в параметрі методу колекції (наприклад, іншого аркуша) у вихідну колекцію (вставка в кінець), для якої було здійснено виклик методу. Передана колекція (вона може бути і безліччю) перетворюється на масив з допомогою методу toArray(). Звичайно, операція додавання здійснюється також за допомогою копіювання. У другому здійснюється додавання всіх елементів collectionдо списку, починаючи з індексу index. При цьому всі елементи зрушать праворуч на кількість елементів у списку collection. Видалення елементів Спочатку розглянемо класичні варіанти видалення елементів з ArrayList.

public E remove(int index)

Здійснює видалення за індексом та зміщує всі наступні (після елемента під зазначеним індексом) елементи вліво, тим самим закриваючи "дірки". Також повертає віддалений елемент (E), який попередньо перед видаленням записується в додаткову змінну, значення якої ми отримуємо в результаті роботи виклику методу. Щоб зрозуміти, що таке E, потрібно буде познайомитися з так званими узагальненими типами (generics). Позначення E вказує на те, що метод повертає той тип даних, який був вказаний при створенні об'єкта ArrayList (згадайте: , List <String> listвідповідно в даному випадку замість E "підставиться"String). Для загального розуміння рекомендую ознайомитися з узагальненими типами. Перевіряється коректність введеного індексу і далі всередині методу відбувається зовсім видалення елемента, а виклик приватного методу fastRemove(Object[] es, int i), у якому відбувається видалення. Методу на вхід ми передаємо наш масив та зазначений індекс. Копіюються елементи, використовуючи System.arraycopy(), зменшується розмір масиву, а далі надають останньому елементу null. Варто зазначити, що новий масив не створюється: System.arraycopy(es, i + 1, es, i, size - 1 - i); У наш же вихідний масив (es) копіюється та частина, яка знаходиться правіше за позицію під зазначеним індексом (i+1), і розташовується вона, починаючи з тієї самої позиції (i), де знаходився елемент , що підлягає видаленню. Таким чином, ми здійснабо зрушення вліво та затерли наш елемент. Спробуємо видалити елемент під індексом 3 з нижче: Розглянемо другий варіант методу:

public boolean remove(Object o)

Метод видаляє зі списку переданий елемент o, а якщо точніше, то об'єкт за вказаним посиланням. Якщо елемент є у списку, він видаляється, а всі елементи зміщуються вліво. Якщо елемент існує у списку та успішно видалено, метод повертає true, у протилежному випадку – false. Аналогічно варіанту з видаленням за індексом, викликається методу fastRemove(), де відбуваються такі самі дії. Різниця у цьому, що у методі remove(Object o)попередньо додатково здійснюється пошук потрібного об'єкта через методequals()класу Object. При видаленні за значенням у циклі проглядаються всі елементи списку, доки не буде знайдено відповідність. Видалений буде лише перший знайдений елемент. Підсумуємо: при видаленні елементів з динамічного масиву, дірок як у звичайному масиві не залишається (видалений осередок не буде порожнім). Всі наступні елементи (які були правіше від індексу) зсуваються однією позицію вліво. Є ще кілька додаткових методів, за допомогою яких можна тією чи іншою мірою видаляти елементи зі списку. Розглянемо їх коротко. Очищаємо нашу колекцію:

public void clear()

У простому циклі forперебираються всі елементи масиву, кожному з яких надаються null. Видалити елементи з нашої колекції, які містяться в іншій переданій колекції можна так:

public boolean removeAll(Collection< ?> c)

Якщо необхідно видалити кілька елементів, напевно, не варто робити це в циклі за умовою: зручніше та безпечніше скористатися методом removeAll(). Він приймає колекцію елементів, які будуть видалені зі списку. Колекція повинна містити елементи того ж типу, що зберігає цільовий список. У протилежному випадку буде викинуто ClassCastException. Метод поверне true, якщо список змінено в результаті виклику методу. Видаляє елементи, що не належать переданій колекції:

public boolean retainAll(Collection< ?> c)

Припустимо, є колекція:

List< String> listFirst = new ArrayList<>();
listFirst.add("White");
listFirst.add("Black");
listFirst.add("Red");

І друга:

List< String> listSecond = new ArrayList<>();
listSecond.add("Green");
listSecond.add("Red");
listSecond.add("White");

Тоді потім listSecond.retainAll(listFirst)залишиться listSecond:

"White"
"Red"

Так як пішов "Green", якого немає в listFirst. Але потім listSecond.removeAll(listFirst)залишиться listSecond:

"Green"
Удалабось все элементы, которые есть в listFirst.

Які не належать переданій колекції – означає, що якщо є елементи, яких немає в переданій колекції, потрібно видалити їх з першої (до якої застосовується метод). Належні переданій колекції - відповідно, якщо є елемент і в першій і другій (переданій) колекції, то дубль з першої знищується.

protected void removeRange(int fromIndex, int toIndex)

Видаляє зі списку всі елементи, які знаходяться між початковим вказаним індексом (включно) та кінцевим вказаним індексом (не включно). Варто зазначити, що метод не можна викликати безпосередньо на об'єкті класу ArrayList. Щоб його використовувати, необхідно успадкуватися від AbstractList/ArrayList. Метод також використовується іншим методом (subList, про який йтиметься далі).

public boolean removeIf(Predicate< ? super E> filter)

Видаляє елементи з колекції за заданим предикатом. Власне предикат — це певна функція/алгоритм/умова, на основі якої буде видалено один або кілька елементів, що відповідають заданій умові. Predicate- функціональний інтерфейс (містить лише один метод, тому може використовуватися у вигляді лямбди), працює за принципом "прийняв один параметр - повернув boolean". Насправді метод перевизначає реалізацію з інтерфейсу Collectionі реалізує наступну "стратегію": він перебирає елементи і позначає ті, які відповідають нашому Predicate; після цього він пробігається вдруге для видалення (і зсуву) елементів, які були відзначені в першій ітерації. Реалізуємо інтерфейс Predicate, який видаватиме true, якщо два об'єкти рівні:

class SamplePredicate< T> implements Predicate< T>{
  T varc1;
  public boolean test(T varc){
     if(varc1.equals(varc)){
       return true;
  }
  return false;
  }
}

В іншому класі створимо ArrayList Stringі об'єкт нашого класу, який реалізує Predicate:

ArrayList< String> color_list = new ArrayList<> ();
SamplePredicate< String> filter = new SamplePredicate<> ();

Запишемо в змінну varc1значення "White":

filter.varc1 = "White";

Додамо до списку кілька рядків:

color_list.add("White");
color_list.add("Black");
color_list.add("Red");
color_list.add("White");
color_list.add("Yellow");
color_list.add("White");

Виконаємо на списку метод removeIf, якому передамо наш об'єкт з умовою:

color_list.removeIf(filter);

В результаті зі списку будуть видалені всі рядки зі значенням "White", оскільки наш "предикат" порівнює їх на рівність. Підсумковий список: [Black, Red, Yellow]. Заміна елементів

public E set(int index, E element)

Здійснює заміну елемента у зазначеній позиції indexна переданий element. Індекс також повинен бути більшим за нуль і меншим за індекс останнього елемента, інакше буде викинуто виняток IndexOutOfBoundsException. Жодних копіювань внутрішнього масиву не відбувається. Просто замість елемента за вказаним індексом вставляється новий елемент, тобто. перезаписуємо значення.

public void replaceAll(UnaryOperator<e> operator)

Змінює всі елементи колекції (можна за умови). В основному використовується у поєднанні з лямбдами або анонімним класом (але для наочності на прикладі використовуємо просто клас, що реалізує інтерфейс), який реалізує інтерфейс UnaryOperatorта визначає його методи. Реалізуємо інтерфейс:

class MyOperator< T> implements UnaryOperator< T>{
   T varc1;
   public T apply(T varc){
     return varc1;
  }
}

В іншому класі створимо ArrayList Stringі об'єкт нашого класу, який реалізує UnaryOperator:

ArrayList< String> color_list = new ArrayList<> ();
MyOperator< String> operator = new MyOperator<> ();

Запишемо в змінну varc1значення "White":

operator.varc1 = "White";

Додамо до списку кілька рядків:

color_list.add("White");
color_list.add("Black");
color_list.add("Red");
color_list.add("White");
color_list.add("Yellow");
color_list.add("White");

Виконаємо на списку метод replaceAll, якому передамо наш об'єкт operator:

color_list.replaceAll(operator);

В результаті всі значення у списку були замінені на "White": [White, White, White, White, White, White]. А ось так, наприклад, можна прибрати всі прогалини з рядків, які є в колекції:

ArrayList< String> list = new ArrayList<>(Arrays.asList("A   ", "  B  ", "C"));
list.replaceAll(String::trim);

Інші методи: Перетворити обліковий масив ArrayList у звичайний масив можна за допомогою методу:

public Object[] toArray()

або

public < T> T[] toArray(T[] a)

— тут тип масиву, що повертається, визначається в runtime Цей метод дозволить:

1. прискорити виконання деяких операцій;
2. передавати масив як параметр методу, який не перевантажується, щоб приймати безпосередньо колекцію;
3. інтеграція нового коду, заснованого на колекціях, із успадкованим кодом, який не розпізнає колекції.

Повернути об'єкт-копію масиву:

public Object clone()

Слід звернути увагу, що метод clone()повертає тип Object, тому після його виклику потрібно зробити приведення до необхідного класу. Під час клонування створюється новий незалежний об'єкт. Перевірити колекцію на наявність у ній об'єкта:

public boolean contains(Object o)

Здійснює перевірку наявності об'єкта у списку (всередині за допомогою методу equals класу Object, тобто порівнює посилання), повертає true/false залежно від результату. Перебрати (звернутися до кожного елемента, а також виконати якусь дію) колекцію, крім звичних циклів, можна за допомогою:

public void forEach(Consumer< ? super E> action)

Ось так ми можемо вивести наш список:

List< Integer> numbers = new ArrayList<>(Arrays.asList(10, 20, 50, 100, -5));
numbers.forEach((number)-> System.out.println(number));

Без використання лямбд необхідно використовувати анонімний клас і перевизначати метод acceptінтерфейсу Consumer:

numbers.forEach(new Consumer< Integer>() {
  @Override
   public void accept(Integer integer) {
      System.out.println(integer);
          }
});

Отримати елемент за його індексом:

public E get(int index)

Використовується для доступу до елементів колекції. Повертає елемент, що знаходиться у списку під вказаним індексом. Якщо index < 0або index >=максимальна кількість елементів списку, буде викинуто виняток IndexOutOfBoundsException. Це основний метод отримання елемента зі списку, і час вилучення елемента за індексом завжди буде однаковим, незалежно від розміру ArrayList, оскільки відбувається звернення до конкретного осередку масиву. Пошук індексів для зазначених об'єктів:

public int indexOf(Object o);
public int lastIndexOf(Object o);

Методи повертають індекс першого (коли вперше зустрічається заданий об'єкт) або останнього входження (коли востаннє зустрічається заданий об'єкт) елемента у списку. Якщо елемент не існує у списку, методи повернуть -1. Перевірити колекцію на наявність у ній елементів:

public boolean isEmpty();

Метод повертає true, якщо список порожній (дивиться, чи поле size 0), інакше – false. Якщо у списку містяться лише елементи null, метод поверне false. Іншими словами, null елементи також враховуються цим методом. Дізнатися кількість елементів у списку:

public int size();

Повертає кількість елементів у списку (значення поля size). Кількість елементів може відрізнятись від обсягу списку (capacity). Отримати ітератор для списку:

public Iterator< E> iterator();

Повертає ітератор для списку для подальшого використання в циклі або за будь-якої іншої обробки. Ітератор реалізує fail-fast поведінку. Якщо він біжить колекцією і помічає якісь модифікації в ній (які були отримані не за допомогою методів ітератора), він відразу викидає виняток ConcurrentModificationException. У ітератора є так званий modification count. Коли ітератор пробігає колекцією після кожного next/hasNext/remove, він перевіряє цей лічильник. Якщо він не збігся з тим, що очікував побачити ітератора, він кидає виняток. Докладно розглядати ітератори тут я не буду.

public ListIterator< E> listIterator() и public ListIterator< E> listIterator(int index)

Повертає list-ітератор для списку для подальшого використання в циклі або за будь-якої іншої обробки. Інтерфейс ListIteratorрозширює інтерфейс Iteratorдля двостороннього обходу списку та видозміни його елементів. У перевантаженому варіанті можна передати індекс, з якого почнеться обхід. Індекс у разі означає перший елемент, з якого розпочне свою роботу метод next(), а за виклику методу previous()обхід почнеться з елемента під індексом «переданий індекс – 1».

public Spliterator <E> spliterator()

У Java 8 впроваджено новий тип ітератора late binding (пізнє зв'язування) та fail-fast, який називається ітератором-розділювачем. Ітератори-розділювачі дозволяють перебирати послідовність елементів, але застосовуються в інший спосіб. Найбільш важливою особливістю інтерфейсу Spliterator є його здатність підтримувати паралельну ітерацію окремих частин послідовності елементів, а отже, і паралельне програмування.