Impl LinkedHashMap - использует двойной связанный список, а не один связанный список; Зачем
Как я упоминал в документации LinkedHashMap, в ней говорится, что двойной связанный список (DLL) поддерживается внутренне
Я пытался понять, почему DLL была выбрана вместо S(ingle)LL. Самое большое преимущество, которое я получаю с DLL, - это обратный ход, но я не вижу ни одного варианта использования LinkedHashMap (), использующего это преимущество, так как предыдущего нет () вроде операции вроде next () в интерфейсе Iterable.
Кто-нибудь может объяснить, почему была DLL, а не SLL?
1 ответ
Это связано с тем, что с помощью дополнительной карты хешей вы можете реализовать удаление в O(1). Если вы используете односвязный список, удаление будет принимать O(n).
Рассмотрим хеш-карту для хранения пары ключ-значение и другую внутреннюю хеш-карту с ключами, указывающими на узлы в связанном списке. При удалении, если это двусвязный список, я легко могу перейти к предыдущему элементу и указать ему следующий элемент. Это невозможно с односвязным списком.