ArrayDeque реализован в виде массива, почему это не произвольный доступ?

Я знаю, что ArrayDeque быстр при добавлении и удалении простых списков. Я на самом деле проверил это, было быстрее добавлять и удалять, чем LinkedList. Потому что я знаю, что он реализован в виде массива, так почему бы не произвольный доступ?

Я прочитал файл ArrayDeque.java в Java src. Но я плохо понимаю свои знания английского. Я видел много статей от Google и Stack Overflow, но я не получил ответы, которые хотел.

В заключение я хочу получить ответ:

1. Почему ArrayDeque не произвольный доступ? (Мне очень любопытно) 2. В каких ситуациях используется ArrayDeque? 3. ArrayDeque не реализован как массив?(Знаю ли я неверные знания?)

Большое спасибо за Ваш ответ!

Источник

4 ответа

Решение

Как упомянуто здесь, ArrayDeque - реализация массива изменяемого размера интерфейса Deque. Подчеркивает структуру данных Array. Тем не менее, он не поддерживает произвольный доступ, поскольку предоставляет интерфейс двусторонней очереди. Если вы хотите получить доступ к случайному элементу Deque, вы можете вызвать toArray() а затем получить доступ к элементам по индексу.

Источник

Ответ в том, что нет веской причины. Было бы легко добавить постоянное время get(int) а также set(int,E) в ArrayDeque, Мне не раз приходилось реализовывать алгоритмы ArrayDeque в пределах ArrayList чтобы восполнить этот недостаток.

Источник
  1. Потому что вы не можете получить доступ к элементу в i-й позиции в постоянное время, в худшем случае.
  2. Всякий раз, когда вам нужно добавить и взять элементы с обоих концов.
  3. Да, это поддерживается массивом.
Источник

Я думаю, что краткий ответ на вопрос «почему нет произвольного доступа» заключается в том, что это не казалось необходимым при создании класса, а также не имело смысла: во-первых, это своего рода , что в основном позволяет доступ на обоих концах, и это все. Так что я как бы согласен, что функция произвольного доступа не должна быть в(хотя, по той же логике, его тоже быть не должно). Вы также можете реализовать, как указывали другие, но его сложно модифицировать и, возможно, есть другие проблемы. Лично я считаю, что интерфейсы коллекций в Java представляют собой большой беспорядок, но на этом я остановлюсь.

Теперь, если вы хотите решить недостатокне имея произвольного доступа, есть несколько вариантов:

  • Прежде всего, вам действительно нужен произвольный доступ? Возможноилидостаточно хороши.
  • Для действительно произвольного доступа это, вероятно, не очень быстро, но должно быть O(1):deque.stream().skip(index).findFirst().get()
Источник
Другие вопросы по тегам