Explanation : I am adding new elements in the list until the window runs out. Head will have the earliest element and tail will have the most recent element. Once the window is over, every addition requires deletion of the very first element or least used in the list which was temporally inserted a lot earlier than other elements. An access to an existing page in the list brings it to the end of the list signifying most recent use.

List end represents most recent element in the cache.
List head represents earliest of all the elements in the cache.

Link.h

#ifndef LINKLIST_LINK_H

#define LINKLIST_LINK_H



#include <iosfwd>



class Link{

private:

    int value;

    Link* next = nullptr;

public:

    Link();



    explicit Link(int key);



    int getValue() const;



    void setValue(int value);



    Link *getNext() const;



    void setNext(Link *next);



    friend void operator<<(std::ostream& os, const Link &link);

};



#endif //LINKLIST_LINK_H

Link.cpp

#include "Link.h"



#include <iostream>



Link::Link()  {

}



Link::Link(int key) {

    this->setValue(key);

}



int Link::getValue() const {

    return value;

}



void Link::setValue(int value) {

    Link::value = value;

}





Link *Link::getNext() const {

    return next;

}



void Link::setNext(Link *next) {

    Link::next = next;

}



void operator<<(std::ostream& os, const Link &link){

    os<<link.getValue()<<" ";

}

LinkList.h

#ifndef LINKLIST_LINKLIST_H

#define LINKLIST_LINKLIST_H



#include <vector>

#include "Link.h"



class LinkList{



protected:

    Link* head = nullptr;



    Link* tail = nullptr;



    std::vector<void* >linksAddresses;

public:



    virtual ~LinkList();



    void insert(int key);



    void push_back(int key);



    void push_front(int key);



    bool deleteKey(int key);



    bool findKey(int key);



    void insert_sorted(int key);



    friend void operator<<(std::ostream& os, const LinkList &linkList);



    void getLinksAddresses();



    void printReverse() const;



    void do_reverse();



    Link* delete_at_pos(int n);

};



#endif //LINKLIST_LINKLIST_H

LinkList.cpp

#include <iostream>

#include "LinkList.h"



void LinkList::insert(int key) {

    push_back(key);

}



void LinkList::push_front(int key) {



    Link *newNode = new Link(key);

    if (head == nullptr) {

        head = newNode;

        tail = newNode;

    } else {

        newNode->setNext(head);

        head = newNode;

    }

    //std::cout << "Inserted " << key <<" address :  "<<&newNode << " at frontn";



}



void LinkList::push_back(int key) {

    Link *newNode = new Link(key);

    if (tail == nullptr) {

        head = newNode;

        tail = newNode;

    } else {

        tail->setNext(newNode);

        tail = newNode;

    }

    //std::cout << "Inserted " << key << " at backn";



}



bool LinkList::deleteKey(int key) {

    Link *curr = head;

    Link *prev = head;



    if (head != nullptr && head->getValue() == key) {

        Link *temp = head;

        head = head->getNext();

        if(head == nullptr)

           tail = nullptr;

        delete temp;

        std::cout << "Deleted " << key << "n";

        return true;

    }



    while (curr != nullptr && curr->getValue() != key) {

        prev = curr;

        curr = curr->getNext();

    }



    if (curr == nullptr) {

        std::cout << "To delete Key " << key << " doesn't existn";

        return false;

    } else {

        prev->setNext(curr->getNext());

        delete curr;

        std::cout << "Deleted " << key << "n";

        return true;

    }

}



bool LinkList::findKey(int key) {

    Link *current = head;

    while (current != nullptr && current->getValue() != key)

        current = current->getNext();

    return current != nullptr;

}



LinkList::~LinkList() {

    Link *next;

    Link *curr = head;

    while (curr != nullptr) {

        next = curr->getNext();

        delete curr;

        curr = next;

    }

    //std::cout<<"Memory freedn";

}



void operator<<(std::ostream &os, const LinkList &linkList) {

    Link *curr = linkList.head;

    os << "List is : ";

    while (curr != nullptr) {

        os << *curr;

        curr = curr->getNext();

    }

    os << 'n';

}



void LinkList::insert_sorted(int key) {

    //TODO

}



void LinkList::getLinksAddresses() {

    while (head != nullptr){

        linksAddresses.push_back(&head);

        std::cout<<&head<<" "<<head->getValue()<<"n";

        head = head->getNext();

    }

}



void reverse(Link* head){

    if(head!= nullptr){

        reverse(head->getNext());

        std::cout<<head->getValue()<<" ";

    }

}



void LinkList::printReverse() const {

    reverse(head);

    std::cout<<"n";

}



void LinkList::do_reverse() {



    Link* prev = nullptr;

    Link* curr = head;

    Link* next = curr->getNext();

    while (curr){



    }



}



Link* LinkList::delete_at_pos(int n)

{

    if(n <=0)

        return head;

    int count  = 1;

    Link* curr = head, *prev = nullptr;;

    while(curr!=nullptr){

        if(count == n)

            break;

        prev = curr;

        curr = curr->getNext();

        count++;

    }

    if(curr!=nullptr){

        Link* temp = curr;

        if(curr == head){

            head = head->getNext();

        }else{

            prev->setNext(curr->getNext());

            }

        delete temp;

    }

    return head;

}

LRU.hpp

#ifndef LINKLIST_LRU_HPP

#define LINKLIST_LRU_HPP



#include <iostream>

#include "LinkList.h"

class LRU : public LinkList{

private:

    const int MAX = 4;

    int max_len  = 0;

    Link* findPage(int key){

        Link *current = LinkList::head;

        while (current != nullptr && current->getValue() != key)

            current = current->getNext();

        return current;

    }

public:

    void insert(int key) override{

        if(MAX > 0) {

            Link *page = findPage(key);

            if (page != nullptr) {

                access(page->getValue());

                return;

            }



            if (max_len >= MAX) {

                deleteKey(LinkList::head->getValue());

                max_len--;

            }

            push_back(key);

            max_len++;

        }

    }



    bool access(int key){

        Link *current = findPage(key);

        if(current == nullptr)

            return false;

        else{

            int val = current->getValue();

            deleteKey(val);

            max_len--;

            insert(val);

            return true;

        }

    }

};



#endif //LINKLIST_LRU_HPP

main.cpp

#include "LinkList.h"

#include "LRU.hpp"

#include <iostream>

void testingLinkedLRU();

int main() {

    testingLinkedLRU();

    return 0;

}

void testingLinkedLRU(){

LRU lru;

std::cout<<lru;



lru.insert(1);

std::cout<<lru;



lru.insert(2);

std::cout<<lru;



lru.insert(3);

std::cout<<lru;



lru.insert(4);

std::cout<<lru;



lru.insert(5);

std::cout<<lru;



lru.insert(6);

std::cout<<lru;



lru.access(3);

std::cout<<lru;



lru.insert(-5);

std::cout<<lru;



lru.insert(5);

std::cout<<lru;



lru.insert(50);

std::cout<<lru;



lru.access(5);

std::cout<<lru;



lru.access(1);

std::cout<<lru;



lru.access(-5);

std::cout<<lru;



}

• It is misleading that the same field in Link is sometimes referred as key and sometimes as value.



• 
  

  LRU::insert works too hard.

  
  
  
  
  
  • It calls findPage, followed by access, which in turn calls
    
    
    
    
    • 
      findPage with the same argument, and
    
    
    • 
      deleteKey, which also traverses the list looking for the same key.
    
    
    
    
  
  
  
  

  Three traversals with the same argument seems excessive. Consider finding the page which links to the victim.

  
  



• A standard implementation of the linked list may exhibits an undesirable behavior. Continuous deletion and creation of nodes will eventually scatter the nodes all over the heap, leading to the poor referential locality, hence plenty of cache misses during traversal. Since your list by definition has a fixed number of entries, try to keep your Links compactly, say in an array, and reuse them.



• 
  

  LinkList::push_front shall be streamlined. head = newNode is executed in both branches; take it out of if/else:

  
  
  

      newNode->setNext(head);
  
      if (head == nullptr) {
  
          tail = newNode;
  
      }
  
      head = newNode;
  
  

  
  
  

  Ditto for push_back.

  
  



• I do not endorse trivial getters and setters. There are no invariants to protect, so they just add noise. Making Link::key and Link::next public is just as good.

1. One class per file, and each with a dedicated header, is a pretty heavy-handed attempt at getting novices to modularize. As it is often the case, it is also counter-productive in this case.



2. 
   

   Link is an internal implementation-detail of LinkList and derived classes, aside from unfortunately and inadvertently being exposed by .delete_at_pos().

   
   
   

   Fix that one return, and make the class private.

   
   



3. As Link is an implementation-detail, there is no sense in trying and failing miserably to hide its details behind a dozen useless public members. Just expose them directly, the only one which might make sense to keep (though that is debatable) is the constructor.




4. Consider a more descriptive name for LinkList. Maybe ForwardList?




5. I wonder what linksAddresses is for, aside from taking up space.




6. There seems to be a lot of stubbed and half-done code left in LinkList. Other code is quite repetitive.




7. I suggest basing an LRU-cache on a std::vector<T> or if the items are heavy, a std::vector<std::unique_ptr<T>>. Also, just a single free function treating such a an LRU-cache might be good enough.




8. There is no reason to explicitly mention nullptr all the time for comparisons, this is C++ not Java or C#. Use ! for negation as needed.

This is a really useful thing to implement! Good choice of projects. Here are some thoughts on how you could improve it:

Naming

Generally when I think of a linked list I don't think of a list of links. I think of a list of nodes which are linked to each other (via next and/or previous pointers). For that reason, I wouldn't call your class Link, I'd call it Node. The link in your class is the next pointer.

The distinction between push_back() and insert() is unclear. In the base class there doesn't appear to be a difference as insert() simply calls push_back(). If I make an LRU object and call push_back() what are the consequences? (Or push_front() for that matter?) Perhaps LRU shouldn't make the methods of LinkList public. Also, renaming insert() to add_new_cache_item() would make clear which a caller should be using given a particular use case.

Related method names should follow the same pattern. You have insert() but then its opposite is called deleteKey(). Presumably that's because delete is a keyword so you couldn't call it that. I'd either rename insert() to insertKey() or rename deleteKey() to simply remove().

Do you need setValue?

Is there a reason why you need a setValue() method in Link? It's only called from the constructor. You could simply move the code for it into the constructor and get rid of the public function. (If you added a next parameter to the constructor you could make the class immutable which is helpful for multithreading, though it would involve changing some of the logic of updating the list.)

Encapsulation

I don't generally like friend functions. People will say that operator<<() is always a friend function. But here you're careful to keep the Link parameter const and it only calls the (also const) getValue() method. There's nothing here that requires it be a friend function, so I say get rid of the friend designation. Just make it a free function in the header.

Double-ended Queue

What you've created actually has a name other than "linked list". It's often called a double-ended queue or deque for short. They have several useful characteristics such as being O(1) for insertion and deletion at the ends, as you've no doubt discovered. There is a standard container called std::deque that implements this. (Though I realize you tagged this as "reinventing the wheel", which is always good for learning!)

Avoid raw pointers

I agree with others that you could implement this with a vector or array (or deque) if you wanted to. But whatever you do, you should avoid using raw pointers. They have so many potential pitfalls that they're really not worth it. I recommend using either std::unique_ptr or std::shared_ptr depending on the situation. They help avoid a large class of resource management errors.

Symmetry

You should strive to make the interface for your classes symmetrical to make them easier to use and understand. By that I mean that if you have an insert() method that does one thing, the remove() or delete() method should do the opposite. In LRU you've overridden insert() to do things like increment the max_len counter. But then in access() you have to manually decrement it after calling deleteKey(). You should also override deleteKey() to call the base class and decrement max_len so that someone updating access() doesn't have to know this fact in the future. They can simply call deleteKey() and not worry about it.