Почему кэш-память LRU использует список ссылок, а не один список ссылок?

Question

Я пытался понять, почему кэш-память LRU использует список ссылок с двойными ссылками, а не список ссылок с одинарными ссылками?

Если i go, то к сложностям по времени они одинаковы для вставки, обновления и удаления. Вот шпаргалка

Это потому, что два указателя в DLL используются для более удобного перемещения узлов назад или вперед ??

Answer 1

Чтобы удалить целевой узел из связанного списка, необходимо изменить другие узлы, которые указывают на него.

В двусвязном списке целевой узел имеет указатели на эти другие узлы, поэтому их легко найти.

В списке с одной ссылкой целевой узел не имеет указатель на другой узел, который указывает на него. Тем не менее, вам все еще нужно изменить этот узел, поэтому вам придется искать его.

Answer 2

Идея реализации LRU-кэша с использованием списка (DLL / SLL) состоит в том, чтобы переместить недавно использованную страницу (узел) в начало.

Это включает в себя большое смещение, скажем, узел находится в середине из списка (DLL / SLL), вам нужно будет удалить узел, переставить следующий указатель предыдущего узла.

Теперь в этом случае, если мы используем Singlely Linked List, нам нужно сохранить предыдущий узел самого последнего доступного узла.

Эта операция не требуется, если мы используем двусвязный список, поскольку он уже поддерживает предыдущий и следующий указатель.

Подвох здесь обращается к этому последнему узел, для которого мы используем хеш-таблицу, дающую нам доступ к этому узлу в O (1).