Make sure you're familiar with the stdlib's containers/list library and its methods. You'll use that implementation of linked lists plus a map of pointers to the list elements to manage the cache contents.