User Professor Hans Noodles
Professor Hans Noodles
41 уровень

Работа ArrayList в картинках

Статья из группы Java Developer
Привет! Сегодняшняя лекция про ArrayList будет с одной стороны проще, а с другой — сложнее, чем предыдущие. Работа ArrayList в картинках - 1Сложнее, потому что сегодня мы заглянем “под капот” ArrayList’a и будем изучать, что же с ним происходит во время операций. С другой стороны, в этой лекции почти не будет кода — в основном картинки и пояснения. Итак, поехали:) Как ты уже знаешь, внутри ArrayList’a находится обыкновенный массив, который и выступает хранилищем данных. В большинстве случаев мы не указываем точный размер списка. Но ведь внутренний массив должен иметь какой-то размер! Так и есть. Его размер по умолчанию — [10].

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}
Работа ArrayList в картинках - 2Для начала посмотрим, как выглядит добавление нового элемента. В первую очередь производится проверка — достаточно ли во внутреннем массиве места и влезет ли еще один элемент. Если место есть, новый элемент добавляется в конец списка. Когда мы говорим “в конец” — имеется в виду не последняя ячейка массива (это было бы странно). Имеется в виду ячейка, следующая за последним текущим элементом. Ее индекс будет равен cars.size(). Наш список сейчас пуст (cars.size() = 0). Соответственно, новый элемент будет добавлен в ячейку с индексом 0.

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);
Работа ArrayList в картинках - 3Тут все понятно. Что будет, если вставка будет осуществляться в середину, то есть между несколькими элементами?

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");
  
   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
  
   cars.add(1, ford);//добавляем ford в ячейку 1, которая уже занята
}
Опять же, сначала проверяется, достаточно ли места в массиве. Если места достаточно, происходит сдвиг элементов вправо начиная с той ячейки, куда мы вставляем новый элемент. Мы вставляем в ячейку с индексом 1. То есть элемент из ячейки 3 копируется в ячейку 4, элемент 2 — в ячейку 3, элемент 1 — в ячейку 2. Работа ArrayList в картинках - 4После этого наш новый элемент вставляется на свое место. Предыдущий элемент (bugatti) уже был скопирован оттуда на новое место. Работа ArrayList в картинках - 5Теперь давай разберемся, как бы происходил этот процесс, если бы места для вставки в массиве не было. Работа ArrayList в картинках - 6Вначале, конечно, осуществляется проверка — достаточно ли места. Если выясняется, что места не хватает, внутри ArrayList’a создается новый массив размером (размерСтарогоМассива * 1.5) + 1 В нашем случае новый массив будет иметь размер 16 ячеек. Туда сразу же будут скопированы все текущие элементы. Работа ArrayList в картинках - 7Старый массив будет удален сборщиком мусора, и останется только новый, расширенный. Теперь свободное место для нового элемента есть. Мы вставляем его в ячейку 3, которая занята. Теперь начинается уже знакомая тебе процедура. Все элементы, начиная с индекса 3, сдвигаются на одну ячейку вправо, и новый элемент спокойно добавляется. Работа ArrayList в картинках - 8И теперь вставка прошла успешно! Со вставкой разобрались. Теперь поговорим об удалении элементов. Как ты помнишь, при работе с массивами мы столкнулись с проблемой: при удалении в нем оставались “дыры”. Единственным выходом было сдвигать элементы влево каждый раз при удалении, причем писать код для сдвига приходилось самостоятельно. ArrayList работает по тому же принципу, но в нем этот механизм уже реализован автоматически. Работа ArrayList в картинках - 9Вот как это выглядит: Работа ArrayList в картинках - 10И в итоге мы получаем нужный результат: Работа ArrayList в картинках - 11Элемент lambo был успешно удален. Тут мы делали удаление из середины. Понятно, что удаление из конца списка будет быстрее, поскольку нужный элемент убирается без сдвига всех остальных. Давай еще раз пройдемся по размерам внутреннего массива и его хранению в памяти. Расширение массива — процесс, занимающий определенное количество ресурсов. Поэтому не стоит создавать ArrayList с размером по умолчанию, если ты точно знаешь, что в нем будет не меньше 100 элементов. Пока ты дойдешь до вставки 100-го элемента, внутренний массив расширится 6 раз, каждый раз с переносом всех элементов.
  • с 10 элементов до 16
  • с 16 элементов до 25
  • с 25 до 38
  • с 38 до 58
  • с 58 до 88
  • с 88 до 133 (по формуле (размерСтарогоМассива * 1.5)+1)
Естественно, это в плане ресурсов довольно затратно. Работа ArrayList в картинках - 12Поэтому, если уж ты знаешь какое-то (хоть примерное) количество хранимых элементов, лучше сразу создать список с массивом определенного размера:

ArrayList<Car> cars = new ArrayList<>(100);
Теперь в памяти будет сразу выделен массив на 100 элементов, более эффективный, потому что не будут тратиться ресурсы на расширение. Есть и обратная сторона медали. При удалении объектов из ArrayList размер внутреннего массива не уменьшается автоматически. Например, у нас есть ArrayList с внутренним массивом в 88 элементов, который целиком заполнен: Работа ArrayList в картинках - 13В процессе работы программы мы удаляем из него 77 элементов, и в нем остается всего 11: Работа ArrayList в картинках - 14Уже догадался, в чем проблема? Конечно, в неэффективном использовании памяти! Мы используем всего 11 ячеек, при этом у нас выделена память на 88 элементов — это в 8 раз больше, чем нужно! Для проведения оптимизации в данном случае можно использовать специальный метод класса ArrayListtrimToSize(). Он “обрезает” длину внутреннего массива до количества хранящихся в нем на текущий момент элементов. Работа ArrayList в картинках - 15Теперь памяти выделяется столько, сколько нужно! :)
Комментарии (177)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
21 июля 2021
что если я сделаю

add(8, ford); 
? ячейки между

lambo
и

 ford
заполнятся

null
?
public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);

   cars.add(8, ford);//добавляем ford в ячейку 1, которая уже занята
}

ВашБосс Уровень 15, Сочи, Россия
8 июня 2021
"Как ты помнишь, при работе с массивами мы столкнулись с проблемой: при удалении в нем оставались “дыры”. Единственным выходом было сдвигать элементы влево каждый раз при удалении, причем писать код для сдвига приходилось самостоятельно." Напомните кому не сложно, как это реализовать?
OdashaNedasha Уровень 15, Киев, Украина
30 марта 2021
"То есть элемент из ячейки 3 копируется в ячейку 4, элемент 2 — в ячейку 3, элемент 1 — в ячейку 2." Здесь ошибка "элемент 1 — в ячейку 2"
Igorka Уровень 10
13 марта 2021
Спасибо * 1,5 знал +1 не знал
VladimirAhlan Уровень 19, Москва
4 марта 2021
Очень крутая статья, спасибо автору
Никита Уровень 14, Екатеринбург, Россия
25 февраля 2021
Если кому-нибудь известно (а может, просто я невнимателен): откуда взялось [ х * 1.5 + 1 ]?
Alexander Mul Уровень 25, Warsaw
2 февраля 2021
Когда мы задаём изначальную длину массива например 100 и и в процессе результата работы у нас в итоге останется например 25 мы применим метод trimToSize() для оптимизации и это логично но вот вопрос: А когда наш массив уже оптимизирован мы можем добавлять после элементы и также удалять их? Или элементы новые мы то добавить и удалить сможем и при добавлении я так понимаю память опять выделится, но когда мы после новых добавлений будем опять удалять из массива элементы то нужно опять применять этот метод trimToSize() для оптимизации?
hidden #2448783 Уровень 19
16 декабря 2020
Очень хорошая лекция. Быстро понятно .
Юлия Алпатова Уровень 10, Москва, Россия
6 декабря 2020
А где пример с trimToSize()?
ivasvi Уровень 28, Санкт-Петербург
29 ноября 2020
"Старый массив будет удален сборщиком мусора, и останется только новый, расширенный. Теперь свободное место для нового элемента есть. Мы вставляем его в ячейку 3, которая занята. Теперь начинается уже знакомая тебе процедура. Все элементы, начиная с индекса 3, сдвигаются на одну ячейку вправо, и новый элемент спокойно добавляется." А почему бы при переписывании значений из старого массива в новый не сделать это в два приема. Сначала переписать те элементы, которые не требуется двигать, а потом те элементы, которые нужно подвинуть на одну ячейку вправо, но писать их сразу со сдвигом. А после в образовавшуюся дырку и помещать вставляемый элемент? А то получается двойная работа какая-то. И с trimToSize() тоже остается вопрос. Почему бы не делать его не по количеству элементов, а в полтора раза больше? Ведь только нам потребуется вставить элемент, опять надо заниматься созданием нового массива, переписыванием и т.п.?