На ваш заглавный вопрос: Да, они делают.
На ваш гипотетически отсортированный набор вопросов реализации: Нет, вы не можете.
Во-первых, вы ошиблись в реализации deque; это не простой связанный список «элемент на узел», это блок элементов на узел (64 в ссылочном интерпретаторе CPython, хотя это детали реализации). И, кроме головных и хвостовых блоков, внутренние блоки никогда не остаются пустыми, поэтому вставка на полпути через deque не особенно дешевая, она все равно должна перемещать кучу вещей вокруг. Это не O(n), как вставка в середине list, так как она использует некоторые преимущества при вращении для поворота, добавления в одну или другую сторону, а затем поворота назад, но это далеко от вставки в известной точке в связанный список, остающийся O(n) (хотя с большими постоянными делителями благодаря тому, что перетасовка целых блоков обходится дешевле, чем перемещение каждого из отдельных элементов).
Два, каждый поиск в deque равен O(n), не O(1), как list; у него постоянный делитель 64, как указано ранее, и он падает до O(1) около обоих концов deque, но в целом он все равно O(n), что плохо масштабируется для больших deque с. bisect поиск равен O(log n) при условии, что индексация последовательности равна O(1); для deque они будут O(n log n), поскольку они будут выполнять log n O(n) операций индексации. Это соответствует вашим результатам тестирования; bisect + deque значительно хуже.
Java TreeMap не реализовано в терминах бинарного поиска и связанного списка в любом случае; связанные списки не годятся для этого, поскольку в конечном итоге полный двоичный поиск должен проходить туда-сюда настолько, чтобы он выполнял O(n) всей работы, даже если он должен сравниваться только с O(log n) элементами. Древовидной карте нужна какая-то древовидная структура, вы не можете просто подделать ее с помощью связанного списка и хорошего алгоритма.
Встроенные альтернативы включают:
insort нормального list: Конечно, оно O(n) в целом, но дорогая часть (поиск места для вставки) составляет O(log n), и это всего лишь шаг "make room", который O(n), и это действительно дешево O(n) (в основном memcpy). Неприемлемо для действительно огромных list с, но вы будете удивлены, насколько большой list вам понадобится, чтобы накладные расходы были заметны на фоне замедления Python. - Отсроченная буферизованная сортировка: Если поиск нечастый, но вставки встречаются часто, отложите сортировку до тех пор, пока это не потребуется, чтобы минимизировать количество операций сортировки; просто добавьте новые элементы в конец без сортировки и установите флаг «нужна сортировка», и повторите поиск
sort перед поиском, когда флаг установлен. Алгоритм TimSort работает очень хорошо, когда входные данные уже в основном отсортированы (гораздо ближе к O(n), чем обычно может выполнить сортировка общего назначения без оптимизации для частично отсортированных), так что это может быть хорошо. - Если вам нужен только самый маленький элемент в любой момент времени, модуль
heapq может сделать это с истинными вставками и удалениями O(log n) и получает минимум с O(1) (это всегда индекс 0). - Использовать базу данных
sqlite3 (возможно через shelve), соответствующим образом проиндексированную; sqlite3 по умолчанию для индексов используется B-дерево, то есть запросы, упорядоченные с использованием ключей индекса, возвращают результаты в отсортированном порядке «бесплатно».
В противном случае вам придется установить сторонний модуль, который обеспечивает правильный отсортированный тип set.