LRU implementation in C++ using a LinkedList












2












$begingroup$


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;

}









share|improve this question











$endgroup$

















    2












    $begingroup$


    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;

    }









    share|improve this question











    $endgroup$















      2












      2








      2





      $begingroup$


      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;

      }









      share|improve this question











      $endgroup$




      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;

      }






      c++ linked-list reinventing-the-wheel memory-management






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited 5 hours ago







      piepi

















      asked 5 hours ago









      piepipiepi

      423316




      423316






















          2 Answers
          2






          active

          oldest

          votes


















          1












          $begingroup$


          • 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.







          share|improve this answer









          $endgroup$













          • $begingroup$
            For the insert method and access method I found some common code between them so I ended up grouping it into a function. I guess I can change the access method to directly take the pointer and bring it to the end/front of the list. This way the access method need not call findPage. Also for optimizations I am gonna substitute the structures for hashtable + doubly linked list where the hash table will have the (key, memory_location) as an entry. this way we can look up and delte in O(1) time. I just wanted to implement a correctly behaving LRU first, irrespective of the time constraints.
            $endgroup$
            – piepi
            1 hour ago





















          1












          $begingroup$


          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.






          share









          $endgroup$













            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ifUsing("editor", function () {
            StackExchange.using("externalEditor", function () {
            StackExchange.using("snippets", function () {
            StackExchange.snippets.init();
            });
            });
            }, "code-snippets");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "196"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f213621%2flru-implementation-in-c-using-a-linkedlist%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            1












            $begingroup$


            • 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.







            share|improve this answer









            $endgroup$













            • $begingroup$
              For the insert method and access method I found some common code between them so I ended up grouping it into a function. I guess I can change the access method to directly take the pointer and bring it to the end/front of the list. This way the access method need not call findPage. Also for optimizations I am gonna substitute the structures for hashtable + doubly linked list where the hash table will have the (key, memory_location) as an entry. this way we can look up and delte in O(1) time. I just wanted to implement a correctly behaving LRU first, irrespective of the time constraints.
              $endgroup$
              – piepi
              1 hour ago


















            1












            $begingroup$


            • 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.







            share|improve this answer









            $endgroup$













            • $begingroup$
              For the insert method and access method I found some common code between them so I ended up grouping it into a function. I guess I can change the access method to directly take the pointer and bring it to the end/front of the list. This way the access method need not call findPage. Also for optimizations I am gonna substitute the structures for hashtable + doubly linked list where the hash table will have the (key, memory_location) as an entry. this way we can look up and delte in O(1) time. I just wanted to implement a correctly behaving LRU first, irrespective of the time constraints.
              $endgroup$
              – piepi
              1 hour ago
















            1












            1








            1





            $begingroup$


            • 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.







            share|improve this answer









            $endgroup$




            • 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.








            share|improve this answer












            share|improve this answer



            share|improve this answer










            answered 2 hours ago









            vnpvnp

            39.7k230101




            39.7k230101












            • $begingroup$
              For the insert method and access method I found some common code between them so I ended up grouping it into a function. I guess I can change the access method to directly take the pointer and bring it to the end/front of the list. This way the access method need not call findPage. Also for optimizations I am gonna substitute the structures for hashtable + doubly linked list where the hash table will have the (key, memory_location) as an entry. this way we can look up and delte in O(1) time. I just wanted to implement a correctly behaving LRU first, irrespective of the time constraints.
              $endgroup$
              – piepi
              1 hour ago




















            • $begingroup$
              For the insert method and access method I found some common code between them so I ended up grouping it into a function. I guess I can change the access method to directly take the pointer and bring it to the end/front of the list. This way the access method need not call findPage. Also for optimizations I am gonna substitute the structures for hashtable + doubly linked list where the hash table will have the (key, memory_location) as an entry. this way we can look up and delte in O(1) time. I just wanted to implement a correctly behaving LRU first, irrespective of the time constraints.
              $endgroup$
              – piepi
              1 hour ago


















            $begingroup$
            For the insert method and access method I found some common code between them so I ended up grouping it into a function. I guess I can change the access method to directly take the pointer and bring it to the end/front of the list. This way the access method need not call findPage. Also for optimizations I am gonna substitute the structures for hashtable + doubly linked list where the hash table will have the (key, memory_location) as an entry. this way we can look up and delte in O(1) time. I just wanted to implement a correctly behaving LRU first, irrespective of the time constraints.
            $endgroup$
            – piepi
            1 hour ago






            $begingroup$
            For the insert method and access method I found some common code between them so I ended up grouping it into a function. I guess I can change the access method to directly take the pointer and bring it to the end/front of the list. This way the access method need not call findPage. Also for optimizations I am gonna substitute the structures for hashtable + doubly linked list where the hash table will have the (key, memory_location) as an entry. this way we can look up and delte in O(1) time. I just wanted to implement a correctly behaving LRU first, irrespective of the time constraints.
            $endgroup$
            – piepi
            1 hour ago















            1












            $begingroup$


            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.






            share









            $endgroup$


















              1












              $begingroup$


              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.






              share









              $endgroup$
















                1












                1








                1





                $begingroup$


                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.






                share









                $endgroup$




                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.







                share











                share


                share










                answered 7 mins ago









                DeduplicatorDeduplicator

                11.3k1850




                11.3k1850






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Code Review Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f213621%2flru-implementation-in-c-using-a-linkedlist%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    How to label and detect the document text images

                    Vallis Paradisi

                    Tabula Rosettana