Рекомендованная реализация заключается в использовании двусвязного списка для записи порядка доступа и хэш-карты, отображающей каждый ключ на узел в связанном списке, который содержит соответствующую запись.
Решение в элементахПрограммирование Интервью и Geeks для Geeks говорит, что при доступе к записи кэша его соответствующий узел должен быть перемещен на FRONT связанного списка.При такой настройке наименее использованный в последнее время будет последним узлом в связанном списке.Мне семантика FIFO кажется более интуитивной, так что мы добавляем узел в конец связанного списка каждый раз, когда есть доступ, а узел в начале связанного списка используется реже всего.Насколько я понимаю, если мы используем двусвязный список, который содержит ссылку как на его голову, так и на хвост, то подход, рекомендованный EPI, и подход, который является более интуитивным для меня, приведут к одинаковой производительности.Кто-нибудь знает, почему EPI и GFG рекомендуют LIFO вместо этого?