List в java – это интерфейс, который предоставляет возможность поддерживать упорядоченную коллекцию. Он содержит основанные на индексах методы для вставки, обновления, удаления и поиска элементов. Он также может иметь повторяющиеся элементы. Но, в отличие от массива, List динамический — в нем можно изменять количество элементов.
Две наиболее частые реализации интерфейса List - это ArrayList и LinkedList.
Класс ArrayList построен на базе массива. Это означает, что доступ по индексу (порядковому номеру элемента) происходит очень быстро. А добавление элементов в середину списка в общем случае довольно затратно, т.к. нужно будет подвинуть вправо каждый элемент, который идёт после добавляемого. С удалением такая же штука. Кроме того, массив, лежащий в основе этой структуры данных, имеет конечное количество свободных ячеек и если их перестанет хватать, придётся создать новый массив большего размера, перенеся в него все элементы из исходного. Но всё это скрыто внутри реализации ArrayList.
Класс LinkedList представляет собой цепочку элементов, в которой каждый элемент имеет ссылку на предыдущий элемент и на следующий. Также имеется ссылка на начало и на конец списка, что позволяет быстро получать доступ к первому и к последнему элементу. При этом для доступа по индексу требуется пройтись последовательно по всей цепочке, поэтому время доступа по индексу прямо пропорционально размеру списка. Однако сам процесс добавления и удаления элементов весьма прост: нужно всего лишь изменить пару ссылок.
Есть еще две реализации, о которых говорят реже. Это Vector и его потомок Stack. Vector похож на ArrayList, но сейчас им не рекомендуют пользоваться — он синхронизированный, за счет этого более потокобезопасный, но менее производительный. Исключение — редкие ситуации с высокими требованиями к потоковой безопасности.
Stack — это стек, работающий по принципу LIFO (last in, first out). Доступ начинается с того элемента, который добавлен в структуру последним, как взятие верхней карты из колоды. Его же быстрее всего можно удалить. Для просмотра последнего элемента есть метод peek(), для просмотра с удалением — pop(), а для добавления элемента в конец — push().
Более подробно об ArrayList и LinkedList поговорим в следующей статье.