Vrftsjtryk

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.