В чем разница между массивом и ArrayList в Java?

Question

[Alex Bezrukov]

Добрый день господа. Может кто подскажет мне в чем разница между обычным массивом данных, например int[] cats = new int[10] и ArrayList, например ArrayList list = new ArrayList()?

Answer 1

[Сергей Протько]

int[] cats = new int[10] в памяти выглядит как непрерывная область память заполненная значениями и равная sizeof(int) * 10. Преимущества - если вы часто обращаетесь и бегаете по коллекции элементов то массивы обеспечат вам максимальную производительность только за счет индексной адресации и меньшего количества кэш-мисов (гуглить свойство локальности данных). Минусы - фиксированный размер, заресайзить можно до не удобно и дорого в плане производительности.

ArrayList же это список, обычный такой вот список. То есть каждый элемент связан друг с другом через указатели. Плюсы - легко добавлять и удалять элементы. Минусы - элементы созданные в разное время могут оказаться в память черти где, что может привести к большому количеству кэш-мисов. Короче траверсинг по списку банально медленнее.

В зависимости от задачи имеет смысла выбирать то или иное решение.

Updated: справедливости ради поправлю себя же. ArrayList это реализация списка на массивах, так что все чуть сложнее. Описанный мной случай - LinkedList, но суть все та же - просто массивы - фиксированный размер, ArrayList - размер динамический.

Comments

[Alex Bezrukov]

Вот оно как. Спасибо.

[Power]

Сергей Протько: Насчёт ArrayList вы не правы. Внутри него как раз-таки находится обычный массив (название ArrayList неспроста). Ну а сам класс - удобная обёртка над массивом с возможностью автоматеческого выделения массива побольше, когда место заканчивается, ну и со всеми методами интерфейса List.
То, что вы описали, это LinkedList.

[Сергей Протько]

Power: ох, что-то да.... Не джавист я)

Answer 2

[halogen]

Что сходу так вспомнил, хотя могу ошибаться:

-	Массивы	List
Изменение размера	нет	да
Сложность доступа к элементу	всегда O(1)	зависит от реализации List
Поддержка семантики "только для чтения"	нет (вариант обхода в простых случаях: клонирование массива)	да (с использованием read-only-декоратора Collections.unmodifiableList(List))
"Ровная" интеграция в систему типов	нет (массивы являются своего рода особым случаем организации объектов; в отличии от .NET не имеет никакого array-типа в качестве базового типа)	да
Поддержка примитивных типов	да	нет ("тяжёлые" объекты для примитивов; слегка нивелируется наличием factory-методов типа Integer.valueOf(int); вариант обхода: FastUtils или Trove)
Проверка типа присваиваемых объектов	в момент присваивания элемента массива или его инициализации	в момент вытягивания элемента списка и интерпретации его на стороне, которая использует список
Взаимные преобразования	массив из списка: List.toArray() всегда возвращает новый массив объектов типа Object; List.toArray(T[]) позволяет указать приготовленный буфер для не-примитивов; преобразование в массив примитивов не поддерживается напрямую	список из массива: Arrays.asList(T...) без проблем, если массив является массивом объектов, а не примитивных типов; если массив является массивом примитивов, Arrays.asList() возвращает список с одного элемента, считая входной массив единственным объектом, хотя существуют варианты типа Ints.asList(int[]) из Guava
Возможность узнать общий тип всех элементов	да	нет (из-за стирания типов; можно узнать тип элемента только по-отдельности при доступе к каждому элементу)
.toString()-представление	нет (всегда имеет вид "[T@IDENTITY", где T - тип массива, IDENTITY - уникальный ID объекта; требуется использование Arrays.toString())	да (зависит от реализации, в общем случае "[n1, n2, n3...]")
Реализация for-обхода	через счётчик для доступа к каждому элементу	через итератор с помощью реализации Iterable

Answer 3

[Павел Гаев]

Примитивы (int, long, float и т.п.) нельзя хранить в ArrayList. Если будешь добавлять в Collection примитив, то произойдет автобоксинг