ArrayList, LinkedList, Vestor эти три класса реализуют интерфейс java.util.List, но у них есть свои различные характеристики, в основном следующие:

Во-первых, синхронизация

ArrayList, LinkedList не синхронизируются, а Vestor синхронизируется. Поэтому, если вам не требуется потокобезопасность, вы можете использовать ArrayList или LinkedList, вы можете сэкономить накладные расходы на синхронизацию. Но в случае многопоточности иногда приходится использовать Vector. Конечно, есть способы обернуть ArrayList, LinkedList, чтобы они тоже добились синхронизации, но эффективность может снизиться.

Во-вторых, данные о росте

из внутреннего механизма реализации с точки зрения ArrayList и Vector используют массив Objec для хранения. Когда вы добавляете элементы в оба типа, все они должны увеличивать длину внутреннего массива, если количество элементов превышает текущую длину внутреннего массива. По умолчанию Vector автоматически увеличивается в два раза по сравнению с исходным ArrayList. Из 50%, поэтому в итоге вы получите эту коллекцию, всегда занимающую больше места, чем вам действительно нужно. Поэтому, если вы хотите сохранить большие объемы данных в коллекции, использование Vector имеет некоторые преимущества, поскольку вы можете избежать ненужных накладных расходов на ресурсы, установив начальный размер коллекции.

В-третьих, оперативность поиска, вставки, удаления объектов

ArrayList и Vector, из указанного места (индекса) для извлечения объекта или вставки в конец коллекции, удаления объекта в одно и то же время, могут быть выражены как O (1) . Однако, если вы добавляете или удаляете элемент в другом месте коллекции, время, необходимое для этого, увеличивается линейно на: O (ni), где n — количество элементов в коллекции, а i — позиция индекса, в которой элементы добавляются или удаляются. Почему это так? Предполагается, что все элементы, следующие за i-м и i-м элементами в наборе, должны выполнить (ni) операций перемещения над объектами при выполнении вышеуказанной операции.
В LinkedList вставка и удаление элементов в любом месте коллекции занимает одинаковое количество времени, -O (1), но медленнее для индексации элемента, O (i), где i — позиция индекса .

Как правило, мы все знаем, что ArrayList и LinkedList примерно различаются:

1.ArrayList основан на динамическом массиве структур данных, структура данных LinkedList основана на списке.
Для получения и установки случайного доступа ArrayList лучше, чем LinkedList, потому что LinkedList перемещает указатель.
Для операций добавления и удаления LinedList более удобен, поскольку ArrayList хочет перемещать данные.

ArrayList и LinkedList — это два класса коллекций для хранения последовательности ссылок на объекты. Например, мы можем использовать ArrayList для хранения последовательности строк или целых чисел. Итак, ArrayList и LinkedList по производительности. В чем разница? Когда ArrayList должен использовать LinkedList?
один. Временная сложность
Первый момент является критическим, внутренняя реализация ArrayList основана на основе массива объектов, поэтому он использует метод get для доступа к любому элементу списка (произвольный доступ), его скорость быстрее, чем LinkedList. Метод get в LinkedList начинается с конца списка по порядку, проверяя до другого конца. Для LinkedList нет более быстрого способа доступа к определенному элементу в списке.
Предположим, у нас есть очень большой список, элементы внутри него отсортированы, список может быть типа ArrayList, также может быть типа LinkedList, и теперь мы перечисляем бинарный поиск (binary search), сравниваем список ArrayList и Скорость запроса LinkedList смотрите в следующей программе:

код Java
пакет com.mangocity.test;
импортировать java.util.LinkedList;
импортировать java.util.List;
импортировать java.util.Random;
импортировать java.util.ArrayList;
импортировать java.util.Arrays;
импорт java.util.Collections;
public class TestList … {
public static final int N = 50000;

общедоступные статические значения списка;

static … {
Integer vals [] = new Integer [N];

For r

(int i = 0, currval = 0; i ‹N; i ++) … {
vals = new Integer (currval);
currval+=r.nextInt(100)+1;
}

values ​​= Arrays.asList(vals);
}

static long timeList (List lst) … {
long start = System.currentTimeMillis
for (int i = 0; i ‹N; i ++ ) … {
int index = Collections.binarySearch(lst, values.get(i));
if (index!=i)
System.out.println("***ошибка***");
}
return System.currentTimeMillis() — Старт;
}
public static void main (String args []) {…
System.out.println («прошедшее время ArrayList: «+ timeList (новый ArrayList (значения))));
System.out.println(«LinkedList занимает много времени:» + timeList (новый LinkedList (значения)));
}

Результат, который я получаю: ArrayList Затрачиваемое время: 15
LinkedList Затрачиваемое время: 2596
Этот результат не является фиксированным, но в основном время ArrayList значительно меньше, чем время LinkedList. Поэтому в этом случае не следует использовать LinkedList. Метод бинарного поиска использует стратегию произвольного доступа, тогда как LinkedList не поддерживает быстрый произвольный доступ. Время, необходимое для рандомизации LinkedList, пропорционально размеру списка. И соответственно время нахождения в случайном доступе в ArrayList фиксируется.
Означает ли это, что ArrayList всегда работает лучше, чем LinkedList? Это не обязательно так, в некоторых случаях LinkedList работает лучше, чем ArrayList, а некоторые алгоритмы более эффективны при реализации в LinkedList. Например, при использовании метода Collections.reverse для реверсирования списка производительность будет выше.
Посмотрите на такой пример, присоединяйтесь к нам, чтобы иметь список, с его большим количеством операций вставки и удаления, в этом случае LinkedList является лучшим выбором. Рассмотрим следующий крайний случай, когда мы повторяем вставку элемента в начало списка:

Код Java
пакет com.mangocity.test;

импортировать java.util. *;
Public class ListDemo {
static final int N = 50000;
static long timeList (список списка) {
long start = System.currentTimeMillis ();
Объект о = новый объект ();
for (int i = 0; i ‹N; i ++)
list.add (0 , O);
return System.currentTimeMillis() — Старт;
}
public static void main (String [] args) {
System.out.println ("The ArrayList Processed:" + timelist (ArrayList new new ()));
System.out .println («Время LinkedList:» + timeList (новый LinkedList ()));
}
}
На данный момент мой вывод: ArrayList Time: 2463

LinkedList Time: 15
Это отличается от результата предыдущего примера, когда при добавлении элемента в самое начало ArrayList все существующие элементы сдвигаются назад, что означает накладные расходы на перемещение и копирование данных. И наоборот, добавление элемента в начало LinkedList — это просто вопрос назначения записи этому элементу и последующей настройки двух соединений. Накладные расходы на добавление элемента в начало LinkedList фиксированы, а стоимость добавления элемента в начало ArrayList пропорциональна размеру ArrayList.

два. Пространственная сложность
имеет LinkedList в частном внутреннем классе, определенном следующим образом:

код Java
Private Entry {статический класс
элемент объекта;
Запись Следующая;
Запись Предыдущая;
}

элемент списка ссылок для каждого объекта в Entry, а также в LinkedList Это предыдущий элемент и следующий элемент. Объект LinkedList из 1000 элементов будет иметь 1000 связанных объектов Entry, каждый из которых соответствует элементу в списке. В этом случае в структуре LinkedList возникают большие накладные расходы, поскольку в ней хранится информация о 1000 объектах Entity.
ArrayList использует для хранения элементов встроенный массив, начальная емкость этого массива равна 10. Когда массиву нужно вырасти, новая емкость получается следующим образом: новая емкость = (старая емкость * 3) / 2 +1, т.е. Каждая емкость наверняка увеличится на 50%. Это означает, что если у вас есть объект ArrayList, содержащий большое количество элементов, в конечном итоге у вас будет много места, которое будет потрачено впустую, что вызвано тем, как работает ArrayList. Если для хранения нового элемента недостаточно места, массив необходимо будет перераспределить, чтобы иметь возможность добавлять новые элементы. Перераспределение массива приведет к резкому снижению производительности. Если мы знаем, сколько элементов будет в ArrayList, мы можем указать емкость с помощью конструктора. Мы также можем удалить неиспользуемое пространство после выделения ArrayList с помощью метода trimToSize.

три. Резюме
ArrayList и LinkedList имеют свои преимущества и недостатки в производительности, имеют свое место, в целом можно описать так:
1. Для ArrayList и LinkedList стоимость добавления элемента в конец списка фиксируется. Для ArrayList это в основном добавление элемента во внутренний массив, который указывает на добавленный элемент, что иногда приводит к перераспределению массива. Для LinkedList эти накладные расходы одинаковы, и выделяется внутренний объект Entry.

2. Вставка или удаление элемента в середине ArrayList означает, что все оставшиеся элементы в списке будут перемещены; накладные расходы на вставку или удаление элемента в середине LinkedList фиксированы.

3. LinkedList не поддерживает эффективный произвольный доступ к элементам.

4. Пустая трата пространства ArrayList в основном отражается в конце списка, чтобы зарезервировать определенное количество места, а стоимость пространства LinkedList отражается в том, что каждый из его элементов должен занимать значительное пространство.

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

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