Почему типичные реализации Array List не являются двусторонними?

Question

Почему ArrayList s, как правило, не являются двусторонними, что обеспечивает быструю амортизацию вставки спереди и сзади?

Есть ли какой-либо недостаток при использовании последнего поверхпервый?

(я не говорю только о Java - я не видел, чтобы двусторонние списки массивов были по умолчанию ни на одном другом языке, но Java был просто хорошим примером здесь.)

---

* Редактировать: я первоначально назвал их "запросами массивов", но это было недоразумением с моей стороны;Я говорил не об очередях, а о двойных списках массивов.

Answer 1

ArrayList прост; записи начинаются с 0, и вы можете добавлять вещи в конце (что может удлинить массив), но запись #X в списке всегда backing_array[X].

ArrayDeque будет более сложным; помимо необходимости отслеживать начало последовательности (поскольку больше не гарантируется, что она будет начинаться с 0, если только вы не хотите O (N) сдвигов / несмещений), вам также придется беспокоиться о другом конце » пустой». Эта дополнительная сложность обходится дорого; в более распространенном случае (списки) RTL все равно должен будет выполнять все проверки и математические вычисления индекса, необходимые в deque, замедляя приложение без реальной причины. Запись #X становится backing_array[start+X], и проверки границ также имеют дополнительную математику.

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

Answer 2

Deque используется только тогда, когда вы хотите получить доступ к данным способом FIFO или LIFO, их общий интерфейс также не обеспечивает способ получения n-го элемента, вы должны сделать это вручную, и на самом деле, если вы посмотрите на Java Deque здесь , вы понимаете, что n-й метод не предусмотрен. Этого должно быть достаточно, чтобы избежать его использования при необходимости индексировать любую группу данных.

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

ИМХО, это также вопрос взаимодействия между массивами в настоящее время и тем, как они были реализованы / управляемы, когда вы писали код ближе к машине.

Answer 3

Обычная реализация ArrayList - это обычный тип коллекции для кода, которому нужно просто что-то, к чему он может многократно добавлять элементы, а затем считывать их. Тип предлагает больше возможностей, чем это, и пропуск некоторых из них может улучшить функциональность типа в основном случае использования, но общее количество дополнительного процессорного времени, которое пришлось бы тратить по всей юниверсе, если бы ArrayList операций было хотя бы 1 % медленнее будет значительным.

Кроме того, неясно, как именно должны вести себя индексированные обращения к двустороннему списку массивов, поскольку существуют две разумные модели поведения: он может указывать, что добавление или удаление элементов с конца с низким номером должно изменить нумерацию все существующие элементы, или он может указывать, что индекс элемента, вставленного до элемента 0, будет равен -1 (все существующие индексы останутся на месте). Добавление более 2 ^ 32 элементов перед элементом 0 (при удалении достаточного количества элементов с другого конца во избежание нехватки памяти) добавит элемент MIN_INT, затем элемент MAX_INT, затем MAX_INT-1 и т. Д. Такой интерфейс может быть неудобным в некоторые способы, но могут быть очень хорошими в других (например, реализация может позволить одновременный индексированный доступ потоком записи и потоком чтения, которые работают на противоположных концах, так как разработчику, который хочет манипулировать элементом 547, не придется беспокоиться об этом когда это произойдет, элемент интереса переместится в слот № 548).

Конечно, существуют различные типы двусторонних коллекций, но это не означает, что добавление двусторонних функций добавит какое-либо значение для общих случаев использования.

Answer 4

В Java ArrayDeque не реализует List.Я не уверен, почему это не так.