Вопрос: Предложите, как реализовать таблицу прямого адреса, в которой ключи хранимых элементов не должны быть различимыми, и элементы могут иметь спутниковые данные. Все три словарные операции (INSERT, DELETE и SEARCH) должны выполняться за O (1) раз. (Не забывайте, что DELETE принимает в качестве аргумента указатель на удаляемый объект, а не ключ.)
Ответ: Предполагая, что выборка элемента должна возвращать спутниковые данные всех сохраненных элементов, мы может иметь каждую карту ключей в двусвязном списке.
INSERT: добавляет элемент в список в постоянное время DELETE: удаляет элемент из связанного списка за постоянное время (элемент содержит указатели на предыдущий и следующий элемент) ПОИСК: возвращает первый элемент, который является узлом в связанном списке, за постоянное время
Я не понимаю, почему операция удаления принимает O (1)? Поскольку ключи не различимы. Некоторые слоты будут иметь двойные связанные списки. Разве не нужно l oop через двойной связанный список, чтобы удалить элемент? Почему это O (1). И почему двойной связанный список полезен здесь? Чем он отличается от односвязного списка в этом сценарии?