ArrayList: особенности и внутреннее устройство
ArrayList — это динамический массив, который является одной из наиболее часто используемых реализаций интерфейса List в Java. Он предоставляет упорядоченную коллекцию элементов и позволяет доступ к ним по индексу. В этом посте мы рассмотрим особенности и внутреннее устройство ArrayList.
Основные особенности ArrayList
Динамический размер:
В отличие от обычного массива, размер ArrayList может динамически изменяться. При добавлении элементов его емкость увеличивается автоматически.
Доступ по индексу:
ArrayList обеспечивает быстрый доступ к элементам по индексу. Операция получения элемента по индексу выполняется за постоянное время O(1).
Упорядоченность:
Элементы в ArrayList хранятся в том порядке, в котором они были добавлены.
Не синхронизированность:
ArrayList не является потокобезопасной коллекцией. Если необходимо использовать его в многопоточной среде, требуется внешняя синхронизация.
Внутреннее устройство ArrayList
ArrayList реализован как обертка над массивом, который динамически изменяет свой размер по мере добавления или удаления элементов. Рассмотрим основные аспекты внутреннего устройства ArrayList.
Массив для хранения элементов:
Внутри ArrayList используется массив Object[], называемый elementData, для хранения элементов.
Размер и емкость:
ArrayList имеет два важных параметра: size и capacity. size — это количество элементов, фактически находящихся в списке, а capacity — это размер внутреннего массива elementData.
Инициализация:
При создании ArrayList можно задать начальную емкость. Если она не указана, используется значение по умолчанию (обычно 10).
Если начальная емкость не указана:
Добавление элементов:
Метод add добавляет элемент в конец списка. При добавлении элемента проверяется, хватает ли текущей емкости массива. Если нет, создается новый массив с увеличенной емкостью, и элементы копируются в него.
Получение элементов:
Метод get возвращает элемент по указанному индексу. Операция выполняется за постоянное время O(1).
Удаление элементов:
Метод remove удаляет элемент по индексу или по значению. После удаления элемента все последующие элементы сдвигаются влево, чтобы заполнить пробел.
#Java #Training #Medium #ArrayList
ArrayList — это динамический массив, который является одной из наиболее часто используемых реализаций интерфейса List в Java. Он предоставляет упорядоченную коллекцию элементов и позволяет доступ к ним по индексу. В этом посте мы рассмотрим особенности и внутреннее устройство ArrayList.
Основные особенности ArrayList
Динамический размер:
В отличие от обычного массива, размер ArrayList может динамически изменяться. При добавлении элементов его емкость увеличивается автоматически.
Доступ по индексу:
ArrayList обеспечивает быстрый доступ к элементам по индексу. Операция получения элемента по индексу выполняется за постоянное время O(1).
Упорядоченность:
Элементы в ArrayList хранятся в том порядке, в котором они были добавлены.
Не синхронизированность:
ArrayList не является потокобезопасной коллекцией. Если необходимо использовать его в многопоточной среде, требуется внешняя синхронизация.
Внутреннее устройство ArrayList
ArrayList реализован как обертка над массивом, который динамически изменяет свой размер по мере добавления или удаления элементов. Рассмотрим основные аспекты внутреннего устройства ArrayList.
Массив для хранения элементов:
Внутри ArrayList используется массив Object[], называемый elementData, для хранения элементов.
private transient Object[] elementData;
Размер и емкость:
ArrayList имеет два важных параметра: size и capacity. size — это количество элементов, фактически находящихся в списке, а capacity — это размер внутреннего массива elementData.
Инициализация:
При создании ArrayList можно задать начальную емкость. Если она не указана, используется значение по умолчанию (обычно 10).
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = {};
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}Если начальная емкость не указана:
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}Добавление элементов:
Метод add добавляет элемент в конец списка. При добавлении элемента проверяется, хватает ли текущей емкости массива. Если нет, создается новый массив с увеличенной емкостью, и элементы копируются в него.
public boolean add(E e) {
ensureCapacityInternal(size + 1); // проверка емкости
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // увеличивается на 50%
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}Получение элементов:
Метод get возвращает элемент по указанному индексу. Операция выполняется за постоянное время O(1).
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}Удаление элементов:
Метод remove удаляет элемент по индексу или по значению. После удаления элемента все последующие элементы сдвигаются влево, чтобы заполнить пробел.
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}#Java #Training #Medium #ArrayList
Основные компоненты ArrayList
Массив для хранения элементов:
Внутри ArrayList используется массив Object[] для хранения элементов. Этот массив называется elementData.
Размер и емкость:
ArrayList имеет два важных параметра: size и capacity. size — это текущее количество элементов в списке, а capacity — это размер внутреннего массива elementData.
Инициализация:
ArrayList можно создать с заданной начальной емкостью или без неё. Если емкость не указана, используется значение по умолчанию (обычно 10).
Пример использования ArrayList
#Java #Training #Medium #ArrayList
Массив для хранения элементов:
Внутри ArrayList используется массив Object[] для хранения элементов. Этот массив называется elementData.
private transient Object[] elementData;
Размер и емкость:
ArrayList имеет два важных параметра: size и capacity. size — это текущее количество элементов в списке, а capacity — это размер внутреннего массива elementData.
private int size;
Инициализация:
ArrayList можно создать с заданной начальной емкостью или без неё. Если емкость не указана, используется значение по умолчанию (обычно 10).
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = {};
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}Пример использования ArrayList
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
// Добавление элементов
list.add("Apple");
list.add("Banana");
list.add("Cherry");
// Получение элементов
System.out.println("First element: " + list.get(0)); // Apple
// Удаление элемента
list.remove("Banana");
System.out.println("List after removal: " + list); // [Apple, Cherry]
// Размер списка
System.out.println("Size of list: " + list.size()); // 2
}
}
#Java #Training #Medium #ArrayList
Глава 2. List — списки в Java
Реализации: ArrayList и LinkedList. Сравнение производительности
ArrayList: динамический массив под капотом
Самая популярная и часто используемая реализация List. Её название раскрывает всю суть: ArrayList — это список, реализованный на основе массива.
Внутреннее устройство:
Массив как основа. Когда вы создаете ArrayList, внутри него создается обычный массив типа Object[] (или E[] после дженериков). Изначально этот массив имеет некоторый начальный размер (емкость, capacity), часто по умолчанию это 10 элементов.
Динамическое расширение.
Когда вы добавляете новый элемент с помощью add(), ArrayList проверяет, осталось ли место во внутреннем массиве.
Если место есть, элемент просто помещается в первую свободную ячейку elementData[size], и значение size увеличивается на 1. Это очень быстрая операция, comparable с работой с массивом.
Если массив полон, происходит следующее:
Создается новый массив большего размера. Стандартная логика увеличения — (старый_размер * 1.5) + 1.
Все элементы из старого массива копируются в новый.
Старый массив удаляется сборщиком мусора, а ссылка elementData начинает указывать на новый массив.
Только после этого новый элемент добавляется в конец.
Этот процесс пересоздания и копирования массива является относительно медленным, поэтому, если вы заранее знаете примерное количество элементов, лучше создать ArrayList с нужной начальной емкостью через конструктор new ArrayList<>(1000). Это позволит избежать или минимизировать количество операций расширения.
LinkedList: цепочка связанных элементов
LinkedList подходит к задаче иначе. Его название также прямо говорит о структуре: LinkedList — это связный список.
Внутреннее устройство:
Узлы (Node). LinkedList не использует массив. Вместо этого он построен на основе узлов.
Каждый узел — это самостоятельный объект, который хранит три вещи:
Сам элемент (например, строку или число).
Ссылку на следующий узел (next).
Ссылку на предыдущий узел (prev).
Двусвязность. LinkedList в Java является двусвязным списком. Это означает, что он хранит ссылки как на следующий, так и на предыдущий элемент. Благодаря этому можно легко перемещаться по списку как от начала к концу, так и от конца к началу.
Отсутствие массива. Элементы не хранятся в непрерывной области памяти. Они разбросаны по куче (Heap), а связаны между собой лишь этими ссылками-«ниточками». Голова списка — это поле first, а хвост — last.
#Java #для_новичков #beginner #List #ArrayList #LinkedList
Реализации: ArrayList и LinkedList. Сравнение производительности
ArrayList: динамический массив под капотом
Самая популярная и часто используемая реализация List. Её название раскрывает всю суть: ArrayList — это список, реализованный на основе массива.
Внутреннее устройство:
Массив как основа. Когда вы создаете ArrayList, внутри него создается обычный массив типа Object[] (или E[] после дженериков). Изначально этот массив имеет некоторый начальный размер (емкость, capacity), часто по умолчанию это 10 элементов.
// Примерно так выглядит внутри ArrayList
public class ArrayList<E> {
private Object[] elementData; // Внутренний массив
private int size; // Текущее количество реальных элементов
// ...
}
Динамическое расширение.
Когда вы добавляете новый элемент с помощью add(), ArrayList проверяет, осталось ли место во внутреннем массиве.
Если место есть, элемент просто помещается в первую свободную ячейку elementData[size], и значение size увеличивается на 1. Это очень быстрая операция, comparable с работой с массивом.
Если массив полон, происходит следующее:
Создается новый массив большего размера. Стандартная логика увеличения — (старый_размер * 1.5) + 1.
Все элементы из старого массива копируются в новый.
Старый массив удаляется сборщиком мусора, а ссылка elementData начинает указывать на новый массив.
Только после этого новый элемент добавляется в конец.
Этот процесс пересоздания и копирования массива является относительно медленным, поэтому, если вы заранее знаете примерное количество элементов, лучше создать ArrayList с нужной начальной емкостью через конструктор new ArrayList<>(1000). Это позволит избежать или минимизировать количество операций расширения.
LinkedList: цепочка связанных элементов
LinkedList подходит к задаче иначе. Его название также прямо говорит о структуре: LinkedList — это связный список.
Внутреннее устройство:
Узлы (Node). LinkedList не использует массив. Вместо этого он построен на основе узлов.
Каждый узел — это самостоятельный объект, который хранит три вещи:
Сам элемент (например, строку или число).
Ссылку на следующий узел (next).
Ссылку на предыдущий узел (prev).
// Примерная структура узла
private static class Node<E> {
E item; // Данные
Node<E> next; // Ссылка на следующий узел
Node<E> prev; // Ссылка на предыдущий узел
// ...
}
Двусвязность. LinkedList в Java является двусвязным списком. Это означает, что он хранит ссылки как на следующий, так и на предыдущий элемент. Благодаря этому можно легко перемещаться по списку как от начала к концу, так и от конца к началу.
Отсутствие массива. Элементы не хранятся в непрерывной области памяти. Они разбросаны по куче (Heap), а связаны между собой лишь этими ссылками-«ниточками». Голова списка — это поле first, а хвост — last.
#Java #для_новичков #beginner #List #ArrayList #LinkedList
👍3