Быстрый поиск в двусвязном списке

Question

В настоящее время у меня есть простая программа базы данных, которая считывает ключи из текстового файла и сохраняет их в двусвязном списке (значения читаются позже, если они необходимы). В настоящее время я делаю последовательный поиск в списке, но это явно довольно медленно. Я надеялся, что есть другой способ сделать. Я читал о бинарных деревьях (в частности, о красных черных деревьях), но я мало что знаю о них, и надеялся, что смогу что-то подсветить из hivemind stackoverflow :) Полагаю, мой вопрос, какой самый быстрый путь выполнить поиск в двусвязном списке?

РЕДАКТИРОВАТЬ: Забыл сказать, что список отсортирован. Не знаю, меняет ли это что-нибудь. Кроме того, причина, по которой я читаю только ключи, состоит в том, что максимальная длина значения составляет 1024 * 32 байта, что я считаю слишком большим. Обратите внимание, что это для назначения, поэтому «типичные сценарии использования» не применяются. Скорее всего, профессора будут подвергаться стресс-тестированию этой штуки, и я не хочу, чтобы такие большие блокировались.

Answer 1

Существует такая вещь, как " Пропустить список ", которую вы можете использовать.

Это набор упорядоченных списков.Каждый список пропускает больше элементов списка.Это позволяет вам выполнять форму двоичного поиска.Однако поддерживать списки сложнее.

Answer 2

Самый быстрый способ выполнить поиск в несортированном двусвязном списке - это один элемент за раз.

Если вы пытаетесь ускорить поиск, не используйте связанный список. Например, ваша идея использовать бинарное дерево, безусловно, будет быстрее, но, как сказал в комментариях Мэтью Флашен, эта реализация полностью отличается от того, что вы используете сейчас.

Answer 3

Учитывая, что ваш двусвязный список отсортирован, и у вас есть список элементов для поиска, я предлагаю рассмотреть проблему построения самобалансирующегося бинарного дерева поиска.Построение дерева может занять некоторое время, но оно будет амортизировано, если у вас есть длинный список элементов для поиска.