Improving Least Recently Used implementation in Java

Question

I wrote implementation of LRU in java and want to know if it can be improved further both in space and time complexity.

Input: Number of frames and reference string for pages.

Output: Number of page faults.

Also I am a little skeptical about its correctness because I got 6/10 in my practical lab.

Kindly ignore OOP's aspect of the program.

import java.util.*;
import java.io.*;
class Lru
{
 private static ArrayList<Integer> arl=new ArrayList<Integer>();
 private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 public static void main(String []args)throws IOException 
 {
 String [] arr;int n,f,pf=0;
 System.out.println("enter the number of frames");
 n=Integer.parseInt(br.readLine());
 System.out.println("enter the reference string");
 arr = br.readLine().split(" ");
 for(String s:arr)
 {
 f=Integer.parseInt(s);
 if(arl.size()<n)
 { ++pf;arl.add(f);}
 else if(arl.contains(f))
 {
 arl.remove(arl.indexOf(f));
 arl.add(f);
 }
 else { arl.remove(0); arl.add(f);++pf;}
 }
 System.out.println("the total no of page faults are "+pf);
 }
}

Answer 1

Bug

If the input consisted of the same page number over and over, your program would return multiple faults instead of 1, because you made this condition be first:

 if(arl.size()<n)
 { ++pf;arl.add(f);}

You should switch the first and second conditions:

 if(arl.contains(f)) {
 arl.remove(arl.indexOf(f));
 arl.add(f);
 } else if(arl.size()<n) {
 ++pf;
 arl.add(f);
 } else {
 arl.remove(0);
 arl.add(f);
 ++pf;
 }

Answer 2

Awful formatting and naming conventions, it is extremely difficult to follow the logic in your code.

• Use more descriptive names like - pageFaults instead of pf
• Declare variables each on separate line
• Wrap logic with curly brackets on separate lines
• Add comments to lines which are not clear what are you doing - to make it readable and maybe you even find the issues (if there are any) by yourself.