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
👍1
Сравнение производительности
Время выполнения операций принято описывать в нотации "Big O", которая показывает, как время работы растет с увеличением объема данных (n).
1. Доступ к элементу по индексу (get(index))
ArrayList: O(1) — константное время.
Это его сильнейшая сторона. Поскольку внутри обычный массив, чтобы получить элемент по индексу 5, система просто делает одну операцию: берет начальный адрес массива и смещается на 5 ячеек в памяти. Это происходит мгновенно, независимо от размера списка.
LinkedList: O(n) — линейное время.
Это его главный недостаток для данной операции. У списка нет индексов в памяти. Чтобы найти элемент с индексом 5, ему приходится начинать с начала (или с конца, если индекс ближе к нему) и последовательно переходить по ссылкам next (или prev).
Для доступа к первому или последнему элементу (get(0) или get(last)) скорость будет высокой O(1), так как есть прямые ссылки first и last. Но для элемента в середине — очень низкой.
2. Вставка элемента (add(element)) и удаление с конца
ArrayList: В среднем O(1), но в худшем случае O(n).
Добавление в конец (add(element)) обычно очень быстрое (O(1)), так как это запись в свободную ячейку. Однако, если массив полон, требуется дорогостоящая операция копирования всего массива (O(n)).
LinkedList: O(1) — константное время.
Добавление в конец всегда выполняется за константное время. Для этого нужно просто создать новый узел, сделать его prev ссылку на старый последний узел, и обновить ссылку last. Это несколько операций, но их количество не зависит от размера списка.
3. Вставка/удаление в произвольной позиции (add(index, element), remove(index))
ArrayList: O(n) — линейное время.
Это его слабое место. Представьте, что вы вставляете элемент в начало списка (индекс 0). ArrayList вынужден сдвинуть все существующие элементы на одну позицию вправо, чтобы освободить место для нового.
Эта операция arraycopy требует времени, пропорционального количеству сдвигаемых элементов (n). Удаление из начала/середины имеет ту же проблему, так как требует сдвига всех последующих элементов влево.
LinkedList: В среднем O(n), но само изменение ссылок — O(1).
Время операции здесь определяется не самим добавлением/удалением, а поиском нужной позиции. Как мы помним, поиск по индексу в LinkedList занимает O(n). Однако, как только узел найден, вставка или удаление выполняются очень быстро: нужно всего лишь поменять несколько ссылок у соседних узлов. Не нужно перемещать половину списка!
Поэтому, если у вас уже есть ссылка на узел (например, вы находитесь в середине итерации), вставка и удаление рядом с этим узлом будут исключительно быстрыми (O(1)).
Когда использовать ArrayList (в 95% случаев):
Когда преобладают операции чтения и получения элементов по индексу.
Когда вы в основном добавляете элементы в конец.
Когда память несколько критична, и вы хотите минимизировать overhead.
Когда использовать LinkedList:
Когда преобладают операции вставки и удаления в начале или середине списка, и при этом у вас нет частой необходимости в быстром доступе по индексу.
Когда вы активно используете структуры типа "стек" (LIFO) или "очередь" (FIFO) (хогда для этого есть более специализированные классы, как ArrayDeque).
#Java #для_новичков #beginner #List #ArrayList #LinkedList
Время выполнения операций принято описывать в нотации "Big O", которая показывает, как время работы растет с увеличением объема данных (n).
1. Доступ к элементу по индексу (get(index))
ArrayList: O(1) — константное время.
Это его сильнейшая сторона. Поскольку внутри обычный массив, чтобы получить элемент по индексу 5, система просто делает одну операцию: берет начальный адрес массива и смещается на 5 ячеек в памяти. Это происходит мгновенно, независимо от размера списка.
// Внутренняя логика ArrayList.get(index)
public E get(int index) {
// ... проверка индекса ...
return (E) elementData[index]; // Прямое обращение по индексу массива
}
LinkedList: O(n) — линейное время.
Это его главный недостаток для данной операции. У списка нет индексов в памяти. Чтобы найти элемент с индексом 5, ему приходится начинать с начала (или с конца, если индекс ближе к нему) и последовательно переходить по ссылкам next (или prev).
// Примерная логика (упрощенно). Чтобы найти узел с индексом 5:
Node<E> x = first;
for (int i = 0; i < 5; i++) { // Нужно сделать 5 итераций
x = x.next;
}
return x.item;
Для доступа к первому или последнему элементу (get(0) или get(last)) скорость будет высокой O(1), так как есть прямые ссылки first и last. Но для элемента в середине — очень низкой.
2. Вставка элемента (add(element)) и удаление с конца
ArrayList: В среднем O(1), но в худшем случае O(n).
Добавление в конец (add(element)) обычно очень быстрое (O(1)), так как это запись в свободную ячейку. Однако, если массив полон, требуется дорогостоящая операция копирования всего массива (O(n)).
LinkedList: O(1) — константное время.
Добавление в конец всегда выполняется за константное время. Для этого нужно просто создать новый узел, сделать его prev ссылку на старый последний узел, и обновить ссылку last. Это несколько операций, но их количество не зависит от размера списка.
3. Вставка/удаление в произвольной позиции (add(index, element), remove(index))
ArrayList: O(n) — линейное время.
Это его слабое место. Представьте, что вы вставляете элемент в начало списка (индекс 0). ArrayList вынужден сдвинуть все существующие элементы на одну позицию вправо, чтобы освободить место для нового.
// При вставке в середину/начало в ArrayList
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = newElement;
size++;
Эта операция arraycopy требует времени, пропорционального количеству сдвигаемых элементов (n). Удаление из начала/середины имеет ту же проблему, так как требует сдвига всех последующих элементов влево.
LinkedList: В среднем O(n), но само изменение ссылок — O(1).
Время операции здесь определяется не самим добавлением/удалением, а поиском нужной позиции. Как мы помним, поиск по индексу в LinkedList занимает O(n). Однако, как только узел найден, вставка или удаление выполняются очень быстро: нужно всего лишь поменять несколько ссылок у соседних узлов. Не нужно перемещать половину списка!
// Вставка `newNode` между `prevNode` и `currentNode`
newNode.prev = prevNode;
newNode.next = currentNode;
prevNode.next = newNode;
currentNode.prev = newNode;
Поэтому, если у вас уже есть ссылка на узел (например, вы находитесь в середине итерации), вставка и удаление рядом с этим узлом будут исключительно быстрыми (O(1)).
Когда использовать ArrayList (в 95% случаев):
Когда преобладают операции чтения и получения элементов по индексу.
Когда вы в основном добавляете элементы в конец.
Когда память несколько критична, и вы хотите минимизировать overhead.
Когда использовать LinkedList:
Когда преобладают операции вставки и удаления в начале или середине списка, и при этом у вас нет частой необходимости в быстром доступе по индексу.
Когда вы активно используете структуры типа "стек" (LIFO) или "очередь" (FIFO) (хогда для этого есть более специализированные классы, как ArrayDeque).
#Java #для_новичков #beginner #List #ArrayList #LinkedList
👍1