Testing MRU-list vs. standard list

Question

The task is to test the the benefits of a Move-To-Front Linked List vs. a standard Linked List. It was also meant to practice inheritance and pointers.

The standard functionality is in LinkedList, the derived MTFList replaces contains() to move the target to the front.

As I was late submitting my solution, I am not sure whether the poor grade is just for missing the deadline given in class, or reflects on my solution. Anyway, I don't know which errors I might have made.

I am hoping that some more experienced eyes can evaluate my use of pointers. Whether my constructors and destructors work appropriately or if I am allowing for memory links.

LinkedListStats.cpp

// Brandon Hoffman
// 10-21-2021
// Test program to evaluate linked list performance
// Written 10/4/19 by Michael Stiber
//

#include <iostream>
#include <string>
#include <random>
#include <vector>
#include <cassert>

// Replace the following include with alternative linked list class
//#include "LinkedList.h"
#include "MTFList.h"

using namespace std;

int main()
{
  // Alter the following declaration to change the linked list class
  // name.
  MTFList theList;

  const int numValues = 1000;
  const int numAccesses = 100000;

  // Create a linked list of the numbers 0..numValues-1
  for (int i = numValues-1; i >= 0; i--)
    theList.add(i);

  // Reset the traversal counter, just in case
  theList.resetTraverseCount();

  // Now, access the elements randomly many times
  int theNumber;
  default_random_engine generator;
  uniform_int_distribution<int> uniform(0, numValues-1);
  normal_distribution<double> normal(numValues/2.0, numValues/5.0);

  // As the statistic of comparison, we use a uniform
  // distribution. For sequential search, even a "smart" algorithm
  // shouldn't be able to improve performance.
  for (int i = 0; i < numAccesses; i++) {
    // Access a random item by value
    theNumber = uniform(generator);
    assert(theList.contains(theNumber));
  }

  cout << "Average number of nodes traversed per access (uniform): "
       << theList.getTraverseCount()/double(numAccesses)
       << endl;

  // Reset the traversal counter.
  theList.resetTraverseCount();

  // We use a normal distribution so that some values are accessed
  // much more frequently. It will be peaked around numValues/2 and fall off
  // rapidly above and below. Note that there is some chance of
  // generating a number outside the legal range, so we test and get a
  // new number if that happens (this is because a uniform
  // distribution goes to +/- infinity). A smart algorithm could in
  // principle take advantage of the higher frequency of access of
  // certain items to lower the average access time. On the other hand,
  // without any "smarts", the mean number of nodes traversed should still
  // be the mean of the distribution, the same as for the uniform distribution.
  for (int i = 0; i < numAccesses; i++) {
    theNumber = 0;
    do {
      theNumber = int(normal(generator));
    } while ((theNumber<0) || (theNumber>=numValues));

    assert(theList.contains(theNumber));
  }

  cout << "Average number of nodes traversed per access (normal): "
       << theList.getTraverseCount()/double(numAccesses)
       << endl;

}  // end LinkedListStats

MTFList.cpp

// LinkedList.cpp
// Brandon Hoffman
// 10-21-2021
// Contains all of the functionality from members of MTFList.h

#include "MTFList.h"

//Returns true if anEntry is found in the List, otherwise returns false. For every Node traversed in
//search of anEntry, increases traverseCount by 1. Overwites functionality from Linked List
//Now moves node with first occurrence of anEntry match to become new first node
bool MTFList::contains(int anEntry) {
   Node *p = first;
   Node *q = nullptr;

   while(p != nullptr) {
      this->incrementTraverseCount();

      if(anEntry == p -> data) {
         if (q != nullptr) {
            q -> next = p -> next;
            p -> next = first;
            first = p;
         }
         return true;
      }
      q = p;
      p = p -> next;
   }
   return false;
}

MTFList.h

// LinkedList.h
// Brandon Hoffman
// 10-21-2021
// Contains the declarations for the MTFList.h class inheriteing from LinkedList.h

#ifndef MTF_LIST_
#define MTF_LIST_

#include "LinkedList.h"

class MTFList : public LinkedList
{
   public:
      //Returns true if anEntry is found in the List, otherwise returns false. For every Node traversed in
      //search of anEntry, increases traverseCount by 1. Overwites functionality from Linked List
      //Now moves node with first occurrence of anEntry match to become new first node
      virtual bool contains(int anEntry);
};

#endif

LinkedList.cpp

// LinkedList.cpp
// Brandon Hoffman
// 10-21-2021
// Contains all of the functionality from members of LinkedList.h


#include <iostream>
#include <string>

#include "LinkedList.h"

//constructor
//takes an array an int n to denote the length of the array
//this is for manual testing purposes only
LinkedList::LinkedList(int A[], int n)
{
   Node *t;
   int i = 0;

   first = new Node;
   first -> data = A[0];
   first -> next = nullptr;
   last = first;

   for(i = 1; i < n; i++) {
      t = new Node;
      t -> data = A[i];
      t -> next = nullptr;
      last -> next = t;
      last = t;
   }
};

//destructor
//The destructor deallocates all of the dynamic storage (each Node) and deletes the Node.
LinkedList::~LinkedList()
{
   this->clear();
}

//displays data in each Node for manual testing purposes
void LinkedList::display()
{
   Node *p = first;

   while(p) {
      std::cout << p -> data << " ";
      p = p -> next;
   }
   std::cout << std::endl;
}

// Returns currentSize, the current number of nodes in the linked List.
int LinkedList::getCurrentSize() const
{
   return currentSize;
}

//returns True if LinkedList is empty i.e. first is pointed nullptr
bool LinkedList::isEmpty() const
{

   if (first == nullptr) {
      return true;
   }
   else {
      return false;
   }
}

//Creates a new Node (dynamically allocated) with data = newEntry, adds it to the back of the
//List, and increases currentSize by 1.Returns true if the new Node with newEntry was added
//successfully, otherwise returns false.
bool LinkedList::add(int newEntry)
{
   Node *temporary;
   temporary = new Node;
   temporary -> data = newEntry;
   temporary -> next = nullptr;

   if (first==nullptr) {
      first = last = temporary;
   }
   else {
      last -> next = temporary;
      last = temporary;
   }

   this -> incrementCurrentSize();
   return true;
}


//Searches and removes the first occurrence of anEntry in the List and decreases numItems by 1.
//Deallocates memory for the removed Node. Returns true if anEntry was removed successfully,
//otherwise returns false (if anEntry was not found in the List or the List was empty).
//calls decrementCurrentSize method to reduce currentSize by 1
bool LinkedList::remove(int anEntry)
{
   Node *p = first;
   Node *q = nullptr;

   while (p != nullptr) {

      if(anEntry == p -> data){
         if (q == nullptr) {
            q = first;
            first = first -> next;
            delete q;
         }
         else {
            q -> next = p -> next;
            delete p;
         }
         this->decrementCurrentSize();
         return true;
         ;
      }
      q = p;
      p = p -> next;
   }
   return false;
}

//Removes all items from the List and resets currentSize to 0. Deallocates memory for each Node removed.
void LinkedList::clear()
{
   Node *p = first;
   while (first) {
      first = first -> next;
      delete p;
      p = first;
   }
   this->resetCurrentSize();
}

//Returns true if anEntry is found in the List, otherwise returns false. For every Node traversed in
//search of anEntry, increases traverseCount by 1.
bool LinkedList::contains(int anEntry)
{
   Node *p = first;
   while(p != nullptr) {
      this->incrementTraverseCount();
      if(anEntry == p -> data) {
         return true;
      }
      p = p -> next;
   }
   return false;
}

LinkedList.h

// LinkedList.h
// Brandon Hoffman
// 10-21-2021
// Contains the declarations for the LinkedList class
#ifndef LINKED_LIST_
#define LINKED_LIST_

#include "IList.h"

class LinkedList: public IList
{
   public:
      //constructor
      //The constructor initializes an empty LinkedList by setting both currentSize and traverseCount to
      //0 and setting first and lst to nullptr.
      //two constructors, first is standard for assignment, 2nd takes an array for testing purposes
      LinkedList(){first=nullptr; last=nullptr; traverseCount=0; currentSize=0;}
      LinkedList(int A[], int n);

      //destructor
      //The destructor deallocates all of the dynamic storage (each Node) and deletes the Node.
      virtual ~LinkedList();

      //accessors
      //displays data in each Node for manual testing purposes
      void display();

      // Returns currentSize, the current number of nodes in the linked List.
      virtual int getCurrentSize() const;

      //mutators
      //Sets traverseCount to 0.
      void resetTraverseCount() {traverseCount=0;}


      //Creates a new Node (dynamically allocated) with data = newEntry, adds it to the back of the
      //List, and increases currentSize by 1.Returns true if the new Node with newEntry was added
      //successfully, otherwise returns false.
      virtual bool add(int newEntry);


      //Searches and removes the first occurrence of anEntry in the List and decreases numItems by 1.
      //Deallocates memory for the removed Node. Returns true if anEntry was removed successfully,
      //otherwise returns false (if anEntry was not found in the List or the List was empty).
      //calls decrementCurrentSize method to reduce currentSize by 1
      virtual bool remove(int anEntry);

      //Removes all items from the List and resets currentSize to 0. Deallocates memory for each Node removed.
      virtual void clear();

      //Returns true if anEntry is found in the List, otherwise returns false. For every Node traversed in
      //search of anEntry, increases traverseCount by 1.
      virtual bool contains(int anEntry);

      //returns True if LinkedList is empty i.e. first is pointed nullptr
      virtual bool isEmpty() const;

 protected:
   //standard Node structure
   struct Node
   {
      int data;
      struct Node *next;
   };

   struct Node *first, *last;
   int currentSize = 0;

   //mutators
   void incrementCurrentSize() {currentSize++;}

   void decrementCurrentSize() {currentSize--;}

   void resetCurrentSize() {currentSize=0;}

   void incrementTraverseCount() {traverseCount++;}

   bool isValidEntry();



};

#endif

IList.h

//  Modified from code created by Frank M. Carrano and Timothy M. Henry.
//  Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.

#ifndef I_LIST_
#define I_LIST_

class IList
{
public:
   /** Constructor */
   IList () : traverseCount(0) { }

   /** Destroys object and frees memory allocated by object.
    (See C++ Interlude 2) */
   virtual ~IList () { }

   /** Gets the current number of entries in this list.
    @return The integer number of entries currently in the list. */
   virtual int getCurrentSize() const = 0;

   /** Sees whether this list is empty.
    @return True if the list is empty, or false if not. */
   virtual bool isEmpty() const = 0;

   /** Adds a new entry to this list.
    @post  If successful, newEntry is stored in the list and
       the count of items in the list has increased by 1.
    @param newEntry  The object to be added as a new entry.
    @return  True if addition was successful, or false if not. */
   virtual bool add(int newEntry) = 0;

   /** Removes one occurrence of a given entry from this list,
       if possible.
    @post  If successful, anEntry has been removed from the list
       and the count of items in the list has decreased by 1.
    @param anEntry  The entry to be removed.
    @return  True if removal was successful, or false if not. */
   virtual bool remove(int anEntry) = 0;

   /** Removes all entries from this list.
    @post  List contains no items, and the count of items is 0. */
   virtual void clear() = 0;

   /** Tests whether this list contains a given entry.
    @param anEntry  The entry to locate.
    @return  True if list contains anEntry, or false otherwise. */
   virtual bool contains(int anEntry) = 0;

   /** Get the count of number of nodes traversed.
    @return  The integer number of nodes traversed since last time the count was reset. */
    virtual int getTraverseCount() const { return traverseCount; }

   /** Reset the count of nodes traversed to zero. */
    virtual void resetTraverseCount() { traverseCount = 0; }

protected:
    int traverseCount;
}; // end IList

#endif

Answer 1

• The

   if (first == nullptr) {
       return true;
   } 
   else {
       return false;
   }
  

  is a very long way to say

    return first == nullptr;
  

• When you add a new entry to the list, it becomes last no matter what. Be explicit:

    if (first==nullptr) {
        first = temporary;
    } else { 
        last -> next = temporary;
    }
    last = temporary;
  

• Ditto for remove. The p/q deletion logic looks convoluted. We only want to delete the node we found, that is p, right? Consider instead

     if (p == first) {
        first = first -> next;
     } else {
        q -> next = p -> next;
     }
     delete p;
  

• The lines

    temporary -> data = newEntry;
    temporary -> next = nullptr;
  

  scream to be in the Node constructor.

• An introductory comment to add is misleading. It claims that the method returns false on a failure to add. I don't see it returning false. I also don't see the possibility of a failure, unless new Node throws a bad_alloc, but then all bets are off anyway.

• remove and contains (especially MTFList::contains) share a lot of functionality. You be in a better shape having a helper method, say Node * detach. Consider

    LinkedList::remove(int entry)
    {
        Node * r = detach(entry);
        if (r) {
            delete r;
        }
        return r != nullptr;
    }
  
    MTFList::contains(int entry)
    {
        Node * r = detach(entry);
        if (r) {
            r->next = first;
            first = r;
            incrementCurrentSize();
        }
        return r != nullptr;
    }
  

  Of course, incrementCurrentSize looks out of place here. It is a strong indication that a prepend method wants to be implemented.

  Another very helpful helper method would be findPredecessor. It will let you consolidate remove and LinkedList::contains.

Answer 2

Don’t write using namespace std;.

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc. (See SF.7.)

---

const int numValues = 1000;

Remember "constexpr is the new static const." This should be constexpr. And what type should you be using?

---

for (int i = numValues-1; i >= 0; i--)
That brutal just to loop n times. Do you know about iota? See this article for counting, and note that std::ranges::iota_view is supplied with the standard library as of C++20.

In general, you should not write explicit loops; you should use algorithms.

---

while(p != nullptr) {
Don't write explicit tests against nullptr. You'll work with smart pointers of various kinds, not just raw pointers (hopefully, usually not raw pointers) and these have an efficient explicit operator bool. It is highly idiomatic to use the truth value of a pointer directly in C++, even though it is no longer as inefficient (since C++11) to write an explicit comparison.

this->incrementTraverseCount();
Don't explicitly use this->. In member functions, the other members are in scope.

---

#ifndef MTF_LIST_
#define MTF_LIST_

These names are too short and to-the-point so they may collide in a real project that uses multiple libraries by different authors. Just use #pragma once, and if you must use the #define mechanism, generate a UUID. You'll probably have stopped using #include before you ever see a compiler that doesn't accept #pragma once. Modules don't have the same issues as classic #include files.

---

⧺SL.io.50 Don't use endl.

---

IList () : traverseCount(0) { }

This is better written to give an inline initializer to the traverseCount member, and then don't implement the default constructor yourself at all. That is,

       ⋮
    int traverseCount { 0 };
       ⋮
    IList() = default;

---

LinkedList::LinkedList(int A[], int n)

• ⧺I.13 Do not pass an array as a single pointer (includes pointer and count parameters in the discussion)

• ⧺R.14 Avoid [] parameters, prefer span

• ⧺F.24 Use a span<T> or a span_p<T> to designate a half-open sequence

In real code, you don't want to be limited to an array of values, but should be able to feed it any kind of range. Look at how standard library functions take their arguments. I admit generic programming might be beyond what you've covered so far, but you should not get in the habit of doing things in weird or bad ways. Here, you should be using std::span.

---

Put simple function implementations directly in the header file. For example, your destructor should be defined inside the class:

       ⋮
    virtual ~LinkedList()  { clear(); }
       ⋮
    int getCurrentSize() const {  return currentSize;  }
    bool isEmpty() const  {  return !first;  }
    

Why is the size an int instead of size_t? For that matter, nothing is named according to convention! Look at the standard library: size, empty. Name things what people expect so others will know how to use it without having to learn your own special vocabulary.

I see more examples of "fat interface". Why is display a member function? It should be a non-member that uses the general purpose ability to traverse the list and do whatever code needs to do with each value in the collection.

---

I'm not sure why you made things virtual and added a function in a derived class. I don't know how well that would work if you really were using polymorphism for the nodes.

The assignment was meant to practice inheritance and pointers.

It doesn't seem to be a good example for having anything to do with inheritance.

So the standard functionality is in the LinkedList class and then a MTFList class inherits that functionality and changes the contains method to move a node to the front when a particular integer value is searched and found.

The search features does not need to be a member of the list. It can be a non-member that operates on a list using only public functionality. You can have an ordinary find, and another function that does find-and-move-to-front.

If you look at the standard library, you'll see that the linked list (which is almost never used, BTW) does not have any kind of find member function.

Searching a container — any container — is done with the find algorithm.

editorial

I don't know exactly what your course is all about and what the outline is or what level of proficiency the student needs to have already. But I have some general thoughts on the subject of teaching C++ in 2021.

One of the "normal" rules is ⧺C.149 — no naked new or delete. Similarly, you should use standard containers for normal coding, don't use raw pointers, use the standard algorithms, etc. Implementing a container is an advanced topic.

Understanding how linked lists, trees, hash tables, and whatnot work and how they can be written is a different class than learning a programming language. A Data Structures and Algorithms class will indeed have you write primitive implementations of basic container-like data collections, and implement code to do bread & butter stuff like sorting and finding an element in a collection. The student in this class should be able to concentrate on these details without also having to learn a language or gather basic coding proficiency.

Likewise, in a class on the C++ language and/or learning to write code in general, you should not be asked to write code that is atypical, bizzare, or flagrantly opposing Best Practices. It should not require you to make naive use of what should be advanced topics. It should prepare you for writing real-world code.