C++ using a link list for this program

A new idea has come to light in which an attempt is promoted to make a program run a little faster. Since memory is way away from the CPU it behooves use to keep the active variables closer to the CPU (in a buffer) and try to cut down on the number of trips all the way to memory to get data the CPU is needing. This project has been assigned to you. Should you accept and should you succeed you will then receive appropriate compensation (a grade).

The problem is to keep active variables closer to the CPU where the variables will be kept in a buffer. When the CPU needs the data from a variable, the first place to look is in the buffer. If found that variables value is returned and that variable becomes the most recently used variable. If the variable is not found, then the variables value is fetched form memory then is added to the buffer, again becoming the most recently used variable. Now the buffer is only so big and will hold only so many variables at a time, so when the buffer is full and you add a new variable to the buffer, then an old variable needs to fall off (out of) the buffer. The variable that falls out represents a less recently used variable it leaves the buffer.

Your effort (your program) is to manage the buffer. You are to write a program that will input a stream of accessed variables simulating the variables accessed in a running program. The buffer will be implemented as a link list. Any variable accessed must first be determined if the variable is in the buffer. If so, move the variable to front of list to represent most recently used. The variables at the end of the list are the less recently used. Any variable not found in the list will be placed/added at the front of the list. At all times the buffer cannot exceed its limits.

You are to simulate different buffer sizes to see if the larger buffer size really saves much on the true memory access. So have your program test with buffer sizes of 4, 5, 6, 7, and 8, the max number of variables in the buffer. Run your program, reading through the data 5 times, one for each buffer size to test. Keep up with the number of times you have to access true memory (ie the number of times a variable is added to the buffer). Be sure not to exceed the buffer size with the number of variables in the list. Print out the buffer size and the number of memory accesses required to simulate this intermediate storage. On end-of-file for each buffer size tested, print out the current variables in the buffer at the time all variables have been read/input from the file.

The Data Structure we are implementing is called a self-organizing list in which we have a list and on each access to a node in the list, the list is reorganized as new variables are encountered.

INPUT: Your input file for the variable stream is LinkL Var Stream.txt.

OUTPUT: Each Buffer size, number of memory accesses and the last list of variables remaining in the buffer.

Input file:

tom sue joe finney tobee total joe joe tom total goo tobee tobee total sid mikey tom tobee blue blue blue sue goo blue blue miney tobee sumup moreso sid sid mikey mikey lesso maybso goo sidtom tom tom sue blue goo sumup tobee finney finney tobee joe joe tom total goo tobee tobee total sid mikey tom tobee blue blue blue sue mikey joe where blue tom finney blue goo joe mikey where finney joe mikey goo blue blue miney tobee cooly sumup moreso sid sid mikey mikey lesso maybso goo sid tom mikey lisso maybso goo goo total where about about tom blue sid finney jojo tobee joe joe tom total goo tobee tobee total sid mikey tom tobee blue blue blue sue goo blue blue miney tobee sumup lisso maybso goo goo sumup total moreso sid mikey mikey cooly lisso goo tobee tobee total sid mikey tom tobee blue blue blue sue so so so total tom lesso maybso goo ghost sid tom blue sid where joe sue joe sue tom sue where sid tom mikey lisso jo sumup jo jo maybso goo goo sumup total sumup lisso maybso goo goo sumup total cooly about tom blue sid finney tobee ghost ghost cooly joe joe tom total goo blue bmoreso sid sid mikeylue miney mikey tom tobee blue blue blue sue so so so total tom lesso goo tobee tom blue sid sid goo maybso goo sid tom blue sid where joe ghost sue joe sue tom sue mikey total conditions maybso goo goo sumup total blue tom finney goo sid blue blur blue joe sumup total miney total categories advanced estate finney goo sid blue blur box west team estate team estate box estate sales look windows photos english estate box estate box left conditions select windows photos sid blue blur blue joe sumup team estate box windows photos team estate photos conditions select windows photos windows photos team estate photos windows photos west left conditions west photos team estate west categories advanced estate box categories advanced west estate box select photos team select windows photos left conditions team estate left conditions west west west west select west windows select windows photos team west left conditions photos team estate box windows select left conditions windows left conditions photos team windows photos team estate box windows