This is the second post related to the LFU Cache. I have completed most (if not all) operations that I expect to require for the LFU Cache algorithm running O(1) implemented. Of course, as I have stated time and again, you start with an architecture, then mode to a design, implementation and testing and cycle as many times as needed modifying the steps until you and the customer (in this case the same) are satisfied with the end product.
I would like to start with a screen capture of the console on the Eclipse IDE:
DoubleLinkList <<< constructor
main <<< count: 7
main <<< list: 0 1 2 3 4 5 6
main <<< peekHead: 0
main <<< peekTail: 6
main <<< find(0): true
main <<< delete(0): 0
main <<< count: 6
main <<< list: 1 2 3 4 5 6
main <<< find(6): true
main <<< delete(6): 6
main <<< count: 5
main <<< list: 1 2 3 4 5
main <<< find(3): true
main <<< delete(3): 3
main <<< count: 4
main <<< list: 1 2 4 5
main <<< find(9999): false
main <<< count: 4
main <<< list: 1 2 4 5
main <<< isFull: false
main <<< isFull: false
main <<< isFull: false
main <<< count: 7
main <<< list: 1 11 2 33 4 5 66
main <<< count: 8
main <<< list: 0 1 11 2 33 4 5 66
main <<< count: 9
main <<< list: 0 1 11 2 33 4 5 55 66
main <<< count: 10
main <<< list: 0 1 11 2 33 34 4 5 55 66
main <<< dequeue: 0
main <<< count: 9
main <<< list: 1 11 2 33 34 4 5 55 66
main <<< dequeue: 1
main <<< count: 8
main <<< list: 11 2 33 34 4 5 55 66
main <<< dequeue: 11
main <<< count: 7
main <<< list: 2 33 34 4 5 55 66
main <<< dequeue: 2
main <<< count: 6
main <<< list: 33 34 4 5 55 66
main <<< dequeue: 33
main <<< count: 5
main <<< list: 34 4 5 55 66
main <<< dequeue: 34
main <<< count: 4
main <<< list: 4 5 55 66
main <<< dequeue: 4
main <<< count: 3
main <<< list: 5 55 66
main <<< dequeue: 5
main <<< count: 2
main <<< list: 55 66
main <<< dequeue: 55
main <<< count: 1
main <<< list: 66
main <<< dequeue: 66
main <<< count: 0
main <<< list:
main <<< count: 0
The output has been enhanced when compared to the previous post in this sequence. Some of the enhanced output has been marked in bold.
The peek() method has been replaced with peekHead() and peekTail() methods. We now have an isFull() new method that at this point does not make much sense. I will cover this feature later in this post. A couple issues that I found in the single list code were corrected when I was implementing and testing the double link list class.
After modifying one line in the test code we have the following console screen capture:
DoubleLinkList <<< constructor
main <<< count: 7
main <<< list: 0 1 2 3 4 5 6
main <<< peekHead: 0
main <<< peekTail: 6
main <<< find(0): true
main <<< delete(0): 0
main <<< count: 6
main <<< list: 1 2 3 4 5 6
main <<< find(6): true
main <<< delete(6): 6
main <<< count: 5
main <<< list: 1 2 3 4 5
main <<< find(3): true
main <<< delete(3): 3
main <<< count: 4
main <<< list: 1 2 4 5
main <<< find(9999): false
main <<< count: 4
main <<< list: 1 2 4 5
main <<< isFull: false
main <<< isFull: false
main <<< isFull: false
main <<< count: 7
main <<< list: 1 11 2 33 4 5 66
main <<< count: 8
main <<< list: 0 1 11 2 33 4 5 66
Exception in thread “main” java.lang.ArrayStoreException: insertBefore <<< unexpected count: 8 >= maxCount: 8
at john.linked.list.DoubleLinkList.insertBefore(DoubleLinkList.java:247)
at john.linked.list.Solution.main(Solution.java:84)
The test code was inserting elements and it ran into the issue that the queue was full and it attempted to insert a new element. Let me show the updated test code:
package john.linked.list;
public class Solution {
/**
* Test code
*/
public static void main(String[] args) {
// **** constant(s) ****
final int MAX_COUNT = 7;
// **** instantiate a new list of integers ****
// SingleLinkList<Integer> list = new SingleLinkList<Integer>(8);
DoubleLinkList<Integer> list = new DoubleLinkList<Integer>(8);
// **** insert into list ****
for (int i = 0; i < MAX_COUNT; i++) {
list.insert(i);
}
// **** string with list contents ****
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
// **** peek into the queue ****
System.out.println(“main <<< peekHead: ” + list.peekHead());
System.out.println(“main <<< peekTail: ” + list.peekTail());
System.out.println();
// **** DELETE element(s) ****
boolean found = list.find(0);
System.out.println(“main <<< find(0): ” + found);
System.out.println(“main <<< delete(0): ” + list.delete(0));
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
found = list.find(6);
System.out.println(“main <<< find(6): ” + found);
System.out.println(“main <<< delete(6): ” + list.delete(6));
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
found = list.find(3);
System.out.println(“main <<< find(3): ” + found);
System.out.println(“main <<< delete(3): ” + list.delete(3));
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
found = list.find(9999);
System.out.println(“main <<< find(9999): ” + found);
if (found)
System.out.println(“main <<< delete(9999): ” + list.delete(9999));
// **** get element count ****
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
System.out.println();
// **** insert AFTER ****
System.out.println(“main <<< isFull: ” + list.isFull());
list.insertAfter(1, 11);
System.out.println(“main <<< isFull: ” + list.isFull());
list.insertAfter(2, 33);
System.out.println(“main <<< isFull: ” + list.isFull());
list.insertAfter(5, 66);
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
System.out.println();
// **** insert BEFORE ****
list.insertBefore(1, 0);
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
list.insertBefore(66, 55);
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
list.insertBefore(4, 34);
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
System.out.println();
// **** dequeue from list ****
while (!list.isEmpty()) {
System.out.println(“main <<< dequeue: ” + list.dequeue());
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
}
System.out.println();
// **** get element count ****
System.out.println(“main <<< count: ” + list.getCount());
}
}
Of interest is the instantiation of the doubly linked list with an argument of 
8. This parameter causes the class to check for the number of elements before an insertion is made. By having this feature and the isFull() method client applications may limit the size of the queue. There are some other methods that allow the developer to build a stack or a circular buffer of any size using the single list (simpler but slower) 
that its double link counterpart.
The java code for the DoubleLinkList class follows:
package john.linked.list;
public class DoubleLinkList <T> {
// **** members ****
Node<T> head;
Node<T> tail;
int count;
int maxCount;
/**
* Default constructor.
*/
public DoubleLinkList() {
System.out.println(“DoubleLinkList <<< constructor”);
this.head = null;
this.tail = null;
this.count = 0;
this.maxCount = 0;
}
/**
* Constructor.
*/
public DoubleLinkList(int maxCount) {
System.out.println(“DoubleLinkList <<< constructor”);
// **** verify argument ****
if (maxCount < 0) {
throw new IllegalArgumentException(“DoubleLinkList <<< unexpected maxCount: ” + this.maxCount);
}
// **** ****
this.head = null;
this.tail = null;
this.count = 0;
this.maxCount = maxCount;
}
/**
* INSERT at tail of the queue.
*/
public void insert(T v) {
// **** check if list is full ****
if ((this.maxCount != 0) && (this.count >= this.maxCount)) {
throw new ArrayStoreException(“insert <<< unexpected count: ” + this.count + ” >= maxCount: ” + this.maxCount);
}
// **** create a new node ****
Node<T> node = new Node<T>(v);
// **** insert node into empty list ****
if (this.head == null) {
this.head = node;
this.tail = node;
this.count++;
}
// **** insert node at tail of list ****
else {
// **** update node fields ****
node.next = null;
node.prev = this.tail;
// **** update queue fields ****
this.tail.next = node;
this.tail = node;
this.count++;
}
}
/**
* Build string with elements in the list.
*/
public String toString() {
StringBuilder str = new StringBuilder();
// **** traverse list ****
for (Node<T> p = this.head; p != null; p = p.next) {
str.append(p.val.toString() + ” “);
}
// **** return string ****
return str.toString();
}
/**
* Peek HEAD of queue.
*/
public T peekHead() {
// **** check if queue is empty ****
if (count == 0) {
throw new IllegalArgumentException(“peekHead <<< unexpected count: ” + count);
}
// **** return value at head of queue ****
return (T)this.head.val;
}
/**
* Peek TAIL of queue.
*/
public T peekTail() {
// **** check if queue is empty ****
if (count == 0) {
throw new IllegalArgumentException(“peekTail <<< unexpected count: ” + count);
}
// **** return value at tail of queue ****
return (T)this.tail.val;
}
/**
* FIND element in queue.
*/
public boolean find(T val) {
// **** traverse queue ****
for (Node p = this.head; p != null; p = p.next) {
if (p.val == val) {
return true;
}
}
// **** value not found ****
return false;
}
/**
* DELETE value from the queue.
*/
public T delete(T val) {
for (Node p = this.head; p != null; p = p.next) {
// **** check if we need to delete this node ****
if (p.val == val) {
// **** delete head ****
if (this.head == p) {
this.head = p.next;
p.next.prev = null;
}
// **** delete tail ****
else if(this.tail == p) {
this.tail = p.prev;
p.prev.next = null;
}
// **** delete in between ****
else {
p.next.prev = p.prev;
p.prev.next = p.next;
}
// **** decrement count ****
this.count–;
// **** return value being deleted ****
return (T)p.val;
}
}
// **** ****
throw new IllegalArgumentException(“delete <<< val: ” + val + ” NOT in list”);
}
/**
* @return the count
*/
public int getCount() {
return this.count;
}
/**
* Insert value AFTER specified value.
*/
public void insertAfter(T after, T val) {
// **** check if list is full ****
if ((this.maxCount != 0) && (this.count >= this.maxCount)) {
throw new ArrayStoreException(“insertAfter <<< unexpected count: ” + this.count + ” >= maxCount: ” + this.maxCount);
}
// **** inserting after tail (normal enqueue) ****
if (after == this.tail.val) {
insert(val);
return;
}
// **** ****
for (Node p = this.head; p != null; p = p.next) {
if (p.val == after) {
Node node = new Node(val);
node.next = p.next;
node.prev = p;
p.next.prev = node;
p.next = node;
this.count++;
return;
}
}
}
/**
* Insert value BEFORE specified one.
*/
public void insertBefore(T before, T val) {
// **** check if list is full ****
if ((this.maxCount != 0) && (this.count >= this.maxCount)) {
throw new ArrayStoreException(“insertBefore <<< unexpected count: ” + this.count + ” >= maxCount: ” + this.maxCount);
}
// **** insert before head ****
if (head.val == before) {
Node node = new Node(val);
node.next = this.head;
node.prev = null;
this.head.prev = node;
this.head = node;
this.count++;
return;
}
// **** insert between ends ****
for (Node p = this.head; p != null; p = p.next) {
if (p.val == before) {
Node node = new Node(val);
node.next = p;
node.prev = p.prev;
p.prev.next = node;
p.prev = node;
this.count++;
return;
}
}
}
/**
* Determine if the queue is EMPTY.
*/
public boolean isEmpty() {
return (this.count <= 0);
}
/**
* DEQUEUE at head of queue.
*/
public T dequeue() {
// **** check if the queue is empty ****
if (this.head == null) {
return null;
}
// **** get value from head node ****
T val = this.head.val;
// **** decrement the queue count ****
this.count–;
// **** update fields in the queue ****
if (this.count == 0) {
this.head = null;
this.tail = null;
} else {
this.head.next.prev = null;
this.head = this.head.next;
}
// **** return the value removed from the queue ****
return val;
}
/**
* Determine if list is full.
*/
public boolean isFull() {
if (this.maxCount == 0) {
return false;
} else {
return (this.count >= this.maxCount);
}
}
}
The code seems to work. Of course it needs a lot more testing and use to feel comfortable with it.
Also note in the test code, that by instantiating the constructors for single or double linked lists with or without arguments (complete set of tests) one is able run the same tests. That tends to simplify the test cycle. Also note, that one should always add to the test cases. That is a simple way to make sure that changes in the code do not affect existing methods or features. The 
thing that I have omitted in the test code is testing for results after each method invocation. The code just displays what is going in. In actual testing it is always better to assert results.
As I have mentioned before, I have implemented several libraries (including queues and stacks) with associated APIs in different programming languages. Most of them are still in use today in commercial off the shelf (COTS) products.
I believe I am ready to get back to tackle the LFU Cache in O(1). Not sure if additional classes or methods will be required.
At this time I need to get back to do actual work. If you have comments or questions regarding this or any other entry in this blog please do not hesitate and send me a message. I will not use your name unless you explicitly allow me to do so.
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa