Колекція ArrayList
ArrayList - реалізує інтерфейс List. Як відомо, в Java масиви мають фіксовану довжину, і після того як масив створений, він не може зростати або зменшуватися. ArrayList може змінювати свій розмір під час виконання програми, при цьому не обов'язково вказувати розмірність при створенні об'єкта. Елементи ArrayList можуть бути абсолютно будь-яких типів в тому числі і null.Клас ArrayList розширює AbstractList і реалізує інтерфейс List. ArrayList - це загальний клас із наступним оголошенням:
class ArrayList<E>, E - тип об'єктів.
Конструктори ArrayList:
- ArrayList ()
- ArrayList (Collection <? extends E> c)
- ArrayList (int capacity)
Створення об'єкту
ArrayList<String> list = new ArrayList<String>();Щойно створений об'єкт list, містить властивості element Data і size.
Сховище значень elementData є ні що інше як масив певного типу (зазначеного в generic), в нашому випадку String[]. Якщо викликається конструктор без параметрів, то за замовчуванням буде створений масив з 10-ти елементів типу Object (з приведенням до типу, зрозуміло).
elementData = (E[]) new Object[10];
Додавання елементів
list.add("0");
Всередині методу add(value) відбувається наступне:
1) перевіряється, чи достатньо місця в масиві для вставки нового елемента;
ensureCapacity(size + 1);
2) додається елемент в кінець (відповідно до значення size) масиву.
elementData[size++] = element;
Весь метод ensureCapacity (min Capacity) розглядати не будемо, зупинимося тільки на парі цікавих місць. Якщо місця в масиві мало, нова ємність розраховується за формулою (oldCapacity * 3) / 2 + 1. Другий момент це копіювання елементів. Воно здійснюється за допомогою native методу System.arraycopy (), який написаний не на Java.
// newCapacity - нове значення ємностіelementData = (E[])new Object[newCapacity];
// newCapacity - нове значення ємностіelementData = (E[])new Object[newCapacity];
// oldData - тимчасове сховище поточного масиву з данимиSystem.arraycopy(oldData, 0, elementData, 0, size);
Приклад циклу, який по черзі додає 15 елементів:
list.add("1");
...list.add("9");
list.add("10");При додаванні 11-го елемента, перевірка показує що місця в масиві немає. Відповідно створюється новий масив і викликається System.arraycopy ().
Після цього додавання елементів продовжується
...list.add("14");
Додавання в «середину» списку
list.add(5, "100");Додавання елемента на позицію з певним індексом відбувається в три етапи:
1) перевіряється, чи достатньо місця в масиві для вставки нового елемента;
ensureCapacity(size+1);
2) готується місце для нового елемента за допомогою System.arraycopy ();
System.arraycopy(elementData, index, elementData, index + 1, size - index);
3) перезаписується значення елемента з вказаним індексом.
elementData[index] = element;size++;
Як можна здогадатися, у випадках, коли відбувається вставка елемента за індексом і при цьому у вашому масиві немає вільних місць, то виклик System.arraycopy () трапиться двічі: перший в ensureCapacity (), другий в самому методі add (index, value), що явно позначиться на швидкості всієї операції додавання.
У випадках, коли в початковий список необхідно додати іншу колекцію, та ще й в «середину», варто використовувати метод addAll (index, Collection). І хоча, даний метод швидше за все викличе System.arraycopy () три рази, в результаті це буде набагато швидше поелементного додавання.
Видалення елементів
Видаляти елементи можна двома способами:- За значенням remove (value)
- За індексом remove (index)
list.remove(5);
Спочатку визначається скільки елементів треба скопіювати
int numMoved = size - index - 1;
потім копіюємо елементи використовуючи System.arraycopy ()
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
зменшуємо розмір масиву і забуваємо про останній елемент
elementData[--size] = null; // Let gc do its work
При видаленні за значенням, в циклі проглядаються всі елементи списку, до тих пір поки не буде знайдено відповідність. Вилучений буде лише перший знайдений елемент.
!!! Як вірно помітив Mike Mirzayanov, при видаленні елементів поточна величина capacity не зменшується, що може призвести до своєрідних витоків пам'яті. Тому не варто нехтувати методом trimToSize ().
Підсумки
- Швидкий доступ до елементів за індексом за час O (1);- Доступ до елементів за значенням за лінійний час O (n);
- Повільний, коли вставляються і видаляються елементи з «середини» списку;
- Дозволяє зберігати будь-які значення в тому числі і null;
- Не синхронізований.
Клас ArrayList призначений для читання об'єктів по індексу. Тож не дарма у назві є слово Array (масив). Після створення колекції на основі ArrayList, прочитати дані можна кількома способами. Наступний приклад демонструє створення ArrayList, його наповнення об'єктами типу String та їх читання за допомогою методу get (int index) та за допомогою ітератора.
import java.util.ArrayList;import java.util.ListIterator;
public class TestArrayList {
private ArrayList<String> a1;
public static void main(String[] args) {
TestArrayList test = new TestArrayList();
test.create();
test.getData();
test.iterateData();
}
void create() {
//створюємо і наповнюємо ArrayList
a1 = new ArrayList<String>();
a1.add("Привіт");
a1.add("тобі");
a1.add("божевільний");
a1.add("світе!");
}
//читаємо дані по індексу
void getData() {
for (int i = 0; i < a1.size(); i++) {
System.out.print(a1.get(i) + " ");
}
}
//Читаємо вміст ArrayList з допомогою ітератора
void iterateData() {
ListIterator<String> it = a1.listIterator();
while (it.hasNext()) {
System.out.print(it.next() + " ");
}
}
}
Результат:
Привіт тобі божевільний світе!
Крім вищенаведених способів можна передати вміст ArrayList у звичайний масив за допомогою методу toArray(). Якщо ви хочете детально розібратися з ArrayList і його методами, то для цього також дивіться інформацію про інтерфейси Collection, List та Iterator.
ListIterator<String> it=a1.listIterator();
Таким чином створюється об’єкт ітератора, посилання на який передається об'єктній змінній it типу ListIterator. ListIterator – це інтерфейс, який розширює інтерфейс Iterator декількома новими методами.
Базовими ж методами інтерфейсу Iterator є ті, що використані у нас в програмі, а саме:
boolean hasNext() – повертає true, якщо ітерація має наступний елемент
E next() - повертає наступний елемент ітерації (буква E вказує, що це може бути елемент будь-якого типу, детальніше див. розділ Узагальнення)
void remove() – знищує останній елемент, що повертався ітератором
Тож у коді бачимо:
while(it.hasNext()){ System.out.print(it.next()+" ");
}
Цикл працює поки є елементи в ітераторі. Перевірка здійснюється за допомогою методу hasNext. А вивід елементів здійснюється за допомогою методу next. Перевірка за допомогою hasNext необхідна через те, що в разі відсутності наступного елементу при виклику методу next буде викинуто виняток NoSuchElementExeption.
Інтерфейсом ListIterator передбачено ще такі методи як add, hasPrevious, next, nextIndex, previous, previousIndex, set. Назви методів говорять самі за себе. Детальніше ви можете подивитися в документації по інтерфейсу ListIterator.
Клас Itr, який реалізовує інтерфейс ListIterator є внутрішнім класом класу AbstractList. ArrayList є нащадком класу AbstractList.
Для того, щоб ітератор міг працювати з певним об’єктом, клас даного об’єкту повинен реалізовувати інтерфейс Iterable:
public interface Iterable<E>
{
Iterator<E> iterator();
}
Інтерфейс Collection розширює даний інтерфейс.
Можна також перебрати елементи за допомогою перевантаженого з виходом java 5 циклу for (так званого “for each”):
for (String str : a1) {
System.out.print(str+" ");
}
При компіляції даний цикл перетворюється компілятором у цикл із ітератором.
Якщо ви погано розумієте вищенаведений приклад і як усе працює зверніться до розділів, що описують основні концепції об’єктно-орієнтованого програмування і, зокрема, розберіть детально теми інтерфейсів, абстрактних класів та поліморфізму.
