Java: эффективно внедряется в LinkedList

Question

Я оптимизирую реализацию отсортированного LinkedList.

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

Я хотел бы знать, есть ли другой способ, в который я могу вставить элемент одновременно с перемещением списка, чтобы уменьшить вставку из O (n + (n, ограниченное размером()/2)), чтобы На).

A ListIterator почти то, что Im после из-за его метода add(), но, к сожалению, в случае, когда в списке есть элементы, равные вставке, вставка должна быть размещена после них в списке. Для реализации этого ListIterator нужен peek(), которого у него нет.

редактировать: У меня есть ответ, но добавит это в любом случае, так как много людей нету правильно понял: Я ищу точку вставки и вставки, которые в сочетании выше, чем О (п)

Answer 1

Я бы благоприятствовать Петер Török предложение, но я все еще хотел бы добавить что-то для итератора подхода:

Обратите внимание, что ListIterator предоставляет метод previous() для итерации по списку в обратном направлении. Таким образом, сначала итерации, пока вы не найдете первый элемент, который больше, а затем перейдите к предыдущему элементу и вызовите add(...). Если вы нажмете на конец, то есть все элементы меньше, а затем просто вызовите add(...), не возвращаясь.

Answer 2

Вы можете рассмотреть skip list, который реализован с использованием нескольких связанных списков с различной степенью детализации. Например. связанный список на уровне 0 содержит все элементы, уровень 1 - только ссылки на каждый второй элемент в среднем, уровень 2 - только на каждый четвертый элемент в среднем и т. д. Поиск начинается с верхнего уровня и постепенно опускается до более низких уровней, пока он находит точное совпадение. Эта логика похожа на двоичный поиск. Таким образом, поиск и вставка представляют собой операцию O (log n).

Конкретный пример в библиотеке классов Java - ConcurrentSkipListSet (хотя он не может быть непосредственно использован для вас здесь).

Answer 3

У меня есть ответ, но добавит это в любом случае, так как много людей нету правильно поняли: я ищу точку вставки и вставки, которые в сочетании выше O(n).

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

• с единым или дважды связанный список предлагает O(N^2) общую стоимость вставки (независимо от того, сочетаете ли вы шаги поиска положения и выполнения вставки!) и стоимость итерации O(N).

• A TreeSet предлагает O(NlogN) общую стоимость ввода и O(N) стоимость итерации. Но имеет ограничение на отсутствие дубликатов.

• Мультимножество на основе дерева (например, TreeMultiset) имеет такую ​​же сложность, как и TreeSet, но допускает дубликаты.

• Структура данных пропущенных списков также имеет ту же сложность, что и предыдущие два.

Ясно, что меры сложности говорят о том, что структура данных, которая использует связанный список выполняет худший, как N становится большой. Для этой конкретной группы требований хорошо реализованный мультисети на основе дерева, вероятно, является лучшим, если предположить, что существует только один поток, доступ к коллекции. Если коллекция сильно используется многими потоками (и это набор), то, вероятно, лучше будет ConcurrentSkipListSet.

---

У вас также есть неправильное представление о том, как сочетаются меры «большого О». Если у меня есть один шаг алгоритма, который равен O(N), а вторым шагом является также O(N), то два шага объединены: STILL O(N) .... не «более O(N)». Вы можете получить это из определения «большой O». (Я не буду утомлять вас подробностями, но математика проста.)