​Списки, часть 1: строение и основные операции

1. Внутреннее устройство

В сердце ArrayList лежит массив:

Object[] elementData;

Размер массива задаётся в конструкторе: new ArrayList(50). Значение по умолчанию — пустой массив.

Структура LinkedList чуть сложнее. Каждый элемент оборачивается в класс:

private static class Node {
   E item;
   Node next;
   Node prev;
}

Т.е сам элемент списка + указатели на следующий и предыдущий элемент.

В объекте LinkedList хранится ссылка на первый и последний элемент списка:

Node first;
Node last;

2. Доступ по индексу: list.get(i) или list.set(i)

ArrayList просто обращается по индексу массива

LinkedList идёт долгим путём. Берёт элемент first идёт по ссылкам, пока не дойдёт до i-го элемента. Затем либо возвращает значение, либо обновляет.

Кажется, что второй подход гораздо дольше. И это правда🙂

Чтобы получить 5000-ый элемент в списке из 10к элементов ArrayList тратит 6 наносекунд, а LinkedList — 8750. Чем больше элементов, тем больше разница.

3. Вставка в середину списка

ArrayList

Допустим, для списка 🟧🟧🟧🟧 вызвали метод add(2, 🦄)

Создаётся новый массив размером +1:
⬜️⬜️⬜️⬜️⬜️

Все элементы старого списка копируются туда так, чтобы образовалось свободное место для нового элемента:
🟧🟧⬜️🟧🟧

Обновляем элемент:
🟧🟧🦄🟧🟧

LinkedList

Рассмотрим тот же метод add(2, 🦄):

▫️ Создаём элемент списка с двумя ссылками: ⬅️🦄➡️
▫️ Идём до текущего элемента 2 и получаем ссылки на элементы 1 и 3
▫️ У элемента 1 обновляем ссылку на next, у 3 — на prev

Само добавление простое, но перед ним нужно пройтись по списку. Это долго, поэтому LinkedList и здесь проигрывает по скорости.

4. Заполнение списка

(см код в вопросе перед постом)

ArrayList

▫️ Создаётся пустой массив
▫️ При первом add размер увеличивается до 10
▫️ При добавлении 11 элемента создаётся новый массив размером 15. Предыдущие элементы копируются, затем добавляется новый
▫️ И так далее: когда места не хватает, создаётся массив в 1.5 раза больше

LinkedList

У текущего tail элемента обновляется ссылка next. Новый объект записывается как tail.

Что работает быстрее?

Интуиция подсказывает, что LinkedList, так как для ArrayList нужно часто переносить элементы в новый массив. На самом деле операции копирования выполняются быстро, так как элементы лежат в памяти рядом, а у процессоров хорошая поддержка этой операции.

Бенчмарки показывают, что до 100к элементов разницы нет, а потом побеждает ArrayList. А при миллионе элементов ArrayList копируется реже и в итоге заполняется в два раза быстрее.

Внизу таблица JMH бенчмарков с моего компьютера. На других железках результаты могут отличаться.

Ответ на вопрос перед постом: для 50к элементов время почти одинаковое.