Как выбрать правильную реализацию списка?

Question

С this CodeReview answer,

Вы, кажется, использовать ArrayList для всех целей. В Java есть другие типы списков, которые лучше подходят для определенных ситуаций, чем ArrayList. Вы должны взглянуть на них и попытаться получить представление о том, когда использовать список. В этом конкретном случае i.E. LinkedList лучше.

Я также очень часто использую ArrayList и не вижу логики выбора другого типа списка.

List docs показать пять основных List подклассы: ArrayList, CopyOnWriteArrayList, LinkedList, Stack и Vector.

Из ArrayList Документов

Размера, IsEmpty, получить, установить, итератор и операции ListIterator работают в постоянное время. Операция add работает в режиме амортизированного постоянного времени, то есть для добавления n элементов требуется время O (n). Все остальные операции выполняются в линейном времени (грубо говоря). Постоянный коэффициент невысок по сравнению с константой для реализации LinkedList.

Это говорит о том, что ArrayList часто опережают LinkedList (утверждение поддерживается this heavily upvoted question), хотя LinkedList документы не дают хорошее представление о производительности:

Все операции выполнять, как может быть ожидаемый для двусвязного списка.

только кажется полезным для неизменных списков, поскольку полный снимок на каждой модификации кажется смехотворно дорогим для нормального использования.

Даже Stack документы не рекомендуют использовать его:

Более полный и последовательный набор операций стека LIFO обеспечивается интерфейсом Deque и его реализации, которые должны быть использованы в предпочтении к этому классу ,

С Vector синхронизируется и остальные List подклассов нет, мне кажется, что Vector будет лучшим выбором в поточно-среде.

Даже после прочтения документов я все еще не думаю, что понимаю, откуда пришел ответ TwoThe. CopyOnWriteArrayList и Vector Кажется, что у каждого есть один специализированный случай использования, Stack, похоже, не стоит использовать, и ArrayList кажется превосходящим LinkedList.

Что мне здесь не хватает, и при каких обстоятельствах реализация List будет выше, чем у ArrayList?

Answer 1

Я согласен с тем, что ArrayList является правильным выбором для многих целей. LinkedList использует 8 или 16 байт памяти для каждого элемента для указателей, а индексирование - O (длина), как вы сказали.

Что такое LinkedLists Преимущества?

• Исключение с remove() во время итерации - постоянное время. С ArrayList это O (длина).
• Для добавления нового узла списка требуется столько же времени. Когда ArrayList s заканчивается из космоса, выделяется больший блок памяти за кулисами, и все содержимое копируется. Хотя амортизированное время для этого по многим операциям является постоянным для каждого элемента, стоимость отдельного пользователя add() равна O (длина). Если такая периодическая задержка неприемлема, вы не можете использовать ArrayList.

Что касается остальных, то Vector восходит к самым ранним дням Java. Это потокобезопасный. Поскольку это увеличивает стоимость каждой операции, ее использование более или менее устарело в пользу ArrayList. Когда вам нужна безопасность резьбы, вы можете использовать обертку SynchronizedList вокруг ArrayList. Аналогичным образом Stack более или менее устарел в пользу более современных, а не потокобезопасных Deque.

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

Answer 2

Проще говоря, вы правы и TwoThe неверно в данном конкретном случае.Как вы указали, так как все, что вы здесь делаете, это add ing и looping, LinkedList только замедлят вас. Это вполне допустимый пример использования ArrayList, и нет ничего плохого в том, что вы делаете по умолчанию ArrayList, когда вы не совсем уверены, что использовать List.

Для более подробного объяснения, когда вы должны использовать LinkedList, ответы на this question могут быть полезными.