LRU with arrays - R&D

Question

Why LRU uses linked list ? Can't we use array to store items, so item with most frequently used will be stored at front of array & least at last of array.

The only reason i can think of not to use array - is that when removing/updating array, it has less performance as compared to linked list.

Is there any more reason ?

Note:- This question is for academic purpose or for research purpose, to have better idea about LRU.

Answer 1

Some context: A LRU Cache is a custom data structure that saves least recently used results for fast access (this makes sense since take a messaging app for example — you don't want to wait 30 seconds to open up a chat, you want the last 10 messages to appear instantly and if you want to get stuff even farther back then you can get that from the database and wait).

Now that you have this important context reminded to you we can get to why we want to use a linkedlist:

It generally gives constant insertion/deletion time given that you know what to insert/delete (which you usually get in constant time as well with a HashMap). If you had to insert/delete to an array constantly, the array resizes (which are O(N)) would be very detrimental to performance (remember we don't want chat messages taking forever to load) whereas deleting from a linkedlist is as easy as:

public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

You can use an array, it just won't be as efficient — there is more reason for using linkedlists however: we want to keep a structure where (in constant time) we can add the most recently used requests listnodes to the front of our linkedlist (after the head/sentinel dummy node). This allows you to have a constant time get() method.