Cache Replacement Algorithm - FIFO

Cache Replacement FIFO Algorithm - (First In First Out)
Before, we understood how the cache replacement algorithm works using FIFO. We will just look for a while to understand the FIFO with the layman term. Suppose a company running a seminar and max capacity of the seminar hall is 100 employees. They have decided whoever comes first they will get the entry and once's seminar hall is full then wouldn't allow anyone. There is no priority to anyone or any designation. So, we will implement a cache replacement algorithm using the Queue abstract data type. We can implement a queue using ArrayList or LinkedList.
Let's do the code and understand the implementation of the algorithm.
Implement Cache Replacement FIFO policy using ArrayList

import java.util.Arrays;
import java.util.List;
import java.util.Optional;

/**
 * @author Chandra Shekhar Paatni on 26/04/20
 */
public class CacheReplacementFIFO<T> {
    T[] cacheReplacementFIFOS;
    int index = -1;
    public CacheReplacementFIFO(T[] cacheReplacementFIFOS) {
        this.cacheReplacementFIFOS = cacheReplacementFIFOS;
    }

    private void add(T value) {
//      check if the cache is full then remove first page
        if (index == cacheReplacementFIFOS.length - 1)
            remove();
//      Add data into the cache if not found
        cacheReplacementFIFOS[++index] = value;
        System.out.println("Page Miss with value "  +value);
    }

    private void remove() {
//      Check if cache is empty
         if(index > -1) {
            int i = 0;
            System.out.println("Page remove with value "+ cacheReplacementFIFOS[i]);
//          remove first element and move all the element one step ahead.
            while (i < index) {
                cacheReplacementFIFOS[i] = cacheReplacementFIFOS[++i];
            }
//          last index to -1
            index--;
        }
    }

    private T get(T value) {
//      Checking if the value is already exist in cache.
        Optional<T> optionalT = Arrays.stream(cacheReplacementFIFOS)
                .filter(e -> value.equals(e)).findFirst();
        if (optionalT.isPresent()) {
            System.out.println("Page Hit with value "+ value);
        } else
//          if the page miss in the cache then it will store
//          data to the cache for the future use.
            add(value);
        return value;
    }

    private void printCache() {
//      Final cache element in cache.
        Arrays.stream(cacheReplacementFIFOS)
                .map(e -> e+" ")
                .forEachOrdered(System.out::print);
    }

    public static void main(String[] args) {
        CacheReplacementFIFO<Integer> cacheReplacementFIFO
                = new CacheReplacementFIFO<>(new Integer[4]);
        List<Integer>  integers = Arrays.asList(0, 255, 1, 4, 18, 4, 1, 8);
        for (Integer integer : integers) {
            cacheReplacementFIFO.get(integer);
        }
        System.out.println("##############Final Value in cache#################");
        cacheReplacementFIFO.printCache();
    }
}

The time complexity of the above implementation of cache:-

• Removing Page is O(n).
• Inserting Page is O(1). 
• Searching Page is O(n).

Implement Cache Replacement FIFO policy using LinkedList

import java.util.Arrays;
import java.util.List;

/**
 * @author Chandra Shekhar Paatni on 26/04/20
 */
public class CacheReplacementFIFO<T> {
    Node<T> head, tail;
    int maxCapacity;
    int size = -1;
    public CacheReplacementFIFO(int maxCapacity) {
        this.maxCapacity = maxCapacity;
    }

    public void add(T value) {
        if (maxCapacity > 0) {
//          Adding a first page in cache            
            if (head == null && tail == null) {
                head = new Node<T>(value);
                tail = head;
            } else {
//              If the size is equal to maxCapacity then we have to
//                remove the first page.                
               if (size >= maxCapacity-1) {
                    remove();
                }
//              Adding a node in tail.                
                tail.next = new Node<T>(value);
                tail = tail.next;
            }
//          calculate existing size of page            
            size++;
            System.out.println("Page miss with value "+ value);
        }
    }

    private void remove() {
//      If we head and tail are pointing to the same node then setting tail to null.
        if (head == tail)
            tail = head.next;
        System.out.println("Page remove with value "+ head.value);
//      We increment the head to next to head.
        head = head.next;
    }

    private T get(T value) {
        Node temp = head;
        boolean isFound = false;
        while (temp != null) {
            if (temp.value.equals(value)) {
                isFound = true;
                break;
            }
            temp = temp.next;
        }
//      If the page is exist in the cache then return the page
        if (isFound) {
            System.out.println("Page hit with value "+ value);
            return (T) temp.value;
        }else
//          We have to add the page if it's not found.
            add(value);
        return value;
    }

    private void printCache() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.value + " ");
            temp = temp.next;
        }
    }

    public static void main(String[] args) {
        CacheReplacementFIFO<Integer> cacheReplacementFIFO
                = new CacheReplacementFIFO<>(4);
        List<Integer> integers = Arrays.asList(0, 255, 1, 4, 18, 4, 1, 8);
        for (Integer integer : integers) {
            cacheReplacementFIFO.get(integer);
        }
        System.out.println("##############Final Value in cache#################");
        cacheReplacementFIFO.printCache();
    }

    class Node<T> {
        T value;
        Node next;

        public Node() {
        }

        public Node(T value) {
            this.value = value;
        }
    }
}

The time complexity of the above implementation of cache:-

• Removing Page is O(1).
• Inserting Page is O(1). 
• Searching Page is O(n).