Лучший способ удалить средний элемент из списка или arraylist в Java?

Question

Мне нужно последовательно удалить средний элемент из отсортированных данных.Каков был бы лучший способ сделать это?Поскольку операция удаления LinkedList занимает n / 2 времени для удаления элемента, arraylist будет быстрее.Но с другой стороны, arraylist требует времени, чтобы сместить все элементы влево, что тоже неэффективно.Могут ли быть полезны другие структуры данных?

Answer 1

Удаление среднего элемента состоит из двух частей:

1. Поиск среднего элемента
2. Удаление этого элемента

ArrayList равно O(1) при произвольном доступе, поэтому 1-й шаг для массива быстрый.В то время как LinkedList равен O(1) при удалении (данный узел), * List 2-ой легко сделать.

То, что вы хотите, лучшее из обоих миров .

IMO этого легко достичь, если вы напишите пользовательский (или расширите существующий) LinkedList .Вам понадобится дополнительная справочная переменная middle, которая:

• переместится на next при вставке, если размер станет нечетным.
• переместится на prev при удаленииесли размер становится нечетным.

Вы также можете делать четные в обоих случаях, но они должны быть одинаковыми (четными или нечетными).

Answer 2

Может ли TreeSet соответствовать требованиям?Если предлагает удаление в O (log n) по ключу.