I have spent some time attempting to implement the LFU Cache using the Java language. Perhaps I should put some additional time but given that Java does not support pointers perhaps it would be a convenient point to switch to C / C++ to get this done. After that I will probably returns to Java and attempt to implement this algorithm.
I have enhanced some and added other methods to the DoubleLinkList class.
Following is a screen capture of the console from the Eclipse IDE:
DoubleLinkList <<< constructor
main <<< iNode: val: 0 next: null prev: null
main <<< iNode: val: 1 next: null prev: john.linked.list.Node@15db9742
main <<< iNode: val: 2 next: null prev: john.linked.list.Node@6d06d69c
main <<< iNode: val: 3 next: null prev: john.linked.list.Node@7852e922
main <<< iNode: val: 4 next: null prev: john.linked.list.Node@4e25154f
main <<< iNode: val: 5 next: null prev: john.linked.list.Node@70dea4e
main <<< iNode: val: 6 next: null prev: john.linked.list.Node@5c647e05
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 <<< count: 5
main <<< list: 1 11 2 4 5
main <<< isFull: false
main <<< count: 6
main <<< list: 1 11 2 33 4 5
main <<< isFull: false
main <<< count: 7
main <<< list: 1 11 2 33 4 5 66
main <<< isFull: false
main <<< count: 8
main <<< list: 0 1 11 2 33 4 5 66
main <<< isFull: false
main <<< count: 9
main <<< list: 0 1 11 2 33 4 5 55 66
main <<< isFull: false
main <<< count: 10
main <<< list: 0 1 11 2 33 34 4 5 55 66
main <<< val: 0 next: john.linked.list.Node@6d06d69c prev: null
main <<< val: 1 next: john.linked.list.Node@33909752 prev: john.linked.list.Node@55f96302
main <<< val: 11 next: john.linked.list.Node@7852e922 prev: john.linked.list.Node@6d06d69c
main <<< val: 2 next: john.linked.list.Node@3d4eac69 prev: john.linked.list.Node@33909752
main <<< val: 33 next: john.linked.list.Node@42a57993 prev: john.linked.list.Node@7852e922
main <<< val: 34 next: john.linked.list.Node@70dea4e prev: john.linked.list.Node@3d4eac69
main <<< val: 4 next: john.linked.list.Node@5c647e05 prev: john.linked.list.Node@42a57993
main <<< val: 5 next: john.linked.list.Node@75b84c92 prev: john.linked.list.Node@70dea4e
main <<< val: 55 next: john.linked.list.Node@6bc7c054 prev: john.linked.list.Node@5c647e05
main <<< val: 66 next: null prev: john.linked.list.Node@75b84c92
main << val: 66 next: null prev: john.linked.list.Node@75b84c92
main << val: 55 next: john.linked.list.Node@6bc7c054 prev: john.linked.list.Node@5c647e05
main << val: 5 next: john.linked.list.Node@75b84c92 prev: john.linked.list.Node@70dea4e
main << val: 4 next: john.linked.list.Node@5c647e05 prev: john.linked.list.Node@42a57993
main << val: 34 next: john.linked.list.Node@70dea4e prev: john.linked.list.Node@3d4eac69
main << val: 33 next: john.linked.list.Node@42a57993 prev: john.linked.list.Node@7852e922
main << val: 2 next: john.linked.list.Node@3d4eac69 prev: john.linked.list.Node@33909752
main << val: 11 next: john.linked.list.Node@7852e922 prev: john.linked.list.Node@6d06d69c
main << val: 1 next: john.linked.list.Node@33909752 prev: john.linked.list.Node@55f96302
main << val: 0 next: john.linked.list.Node@6d06d69c prev: null
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: 1
main <<< list: 1
main <<< count: 2
main <<< list: 2 1
main <<< count: 3
main <<< list: 3 2 1
main <<< count: 4
main <<< list: 4 3 2 1
main <<< count: 5
main <<< list: 5 4 3 2 1
main <<< count: 6
main <<< list: 6 5 4 3 2 1
main <<< count: 7
main <<< list: 7 6 5 4 3 2 1
main <<< dequeue: 7
main <<< count: 6
main <<< list: 6 5 4 3 2 1
main <<< dequeue: 6
main <<< count: 5
main <<< list: 5 4 3 2 1
main <<< dequeue: 5
main <<< count: 4
main <<< list: 4 3 2 1
main <<< dequeue: 4
main <<< count: 3
main <<< list: 3 2 1
main <<< dequeue: 3
main <<< count: 2
main <<< list: 2 1
main <<< dequeue: 2
main <<< count: 1
main <<< list: 1
main <<< dequeue: 1
main <<< count: 0
main <<< list:
DoubleLinkList <<< constructor
main <<< w: name: 1 id: 1
main <<< w: name: 4 id: 2
main <<< w: name: 9 id: 3
main <<< widgets: name: 1 id: 1 name: 4 id: 2 name: 9 id: 3
main <<< w: name: widget_c id: -3
main <<< w: name: widget_b id: -2
main <<< w: name: widget_a id: -1
main <<< w: name: 1 id: 1
main <<< w: name: 4 id: 2
main <<< w: name: 9 id: 3
main <<< widgets: name: widget_c id: -3 name: widget_b id: -2 name: widget_a id: -1 name: 1 id: 1 name: 4 id: 2 name: 9 id: 3
Following is the test code that generated the output captured in the console:
package john.linked.list;
public class Solution {
/**
* Test code
*/
public static void main(String[] args) {
// **** constant(s) ****
final int MAX_COUNT = 7;
// **** instantiate a list of integers ****
// SingleLinkList<Integer> list = new SingleLinkList<Integer>(MAX_COUNT * 2);
DoubleLinkList<Integer> list = new DoubleLinkList<Integer>(MAX_COUNT * 2);
// **** insert into list ****
Node<Integer> iNode = null;
for (int i = 0; i < MAX_COUNT; i++) {
iNode = list.enqueue(i);
System.out.println(“main <<< iNode: ” + iNode.genString());
}
System.out.println();
// **** string with list contents ****
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
System.out.println();
// **** 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 <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
System.out.println(“main <<< isFull: ” + list.isFull());
list.insertAfter(2, 33);
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
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 ****
System.out.println(“main <<< isFull: ” + list.isFull());
list.insertBefore(1, 0);
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
System.out.println(“main <<< isFull: ” + list.isFull());
list.insertBefore(66, 55);
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
System.out.println(“main <<< isFull: ” + list.isFull());
list.insertBefore(4, 34);
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
System.out.println();
// **** manually traverse list using next ****
for (Node<Integer> n = list.head; n != null; n = n.next) {
System.out.println(“main <<< ” + n.genString());
}
System.out.println();
// **** manually traverse list using prev ****
for (Node<Integer> p = list.tail; p != null; p = p.prev) {
System.out.println(“main << ” + p.genString());
}
System.out.println();
// **** dequeue ****
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();
// **** push ****
for (int i = 1; i <= MAX_COUNT; i++) {
list.push(i);
System.out.println(“main <<< count: ” + list.getCount());
System.out.println(“main <<< list: ” + list.toString());
}
System.out.println();
// **** dequeue ****
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();
// **** list of widgets ****
// SingleLinkList<Widget> widgets = new SingleLinkList<Widget>(MAX_COUNT);
DoubleLinkList<Widget> widgets = new DoubleLinkList<Widget>(MAX_COUNT);
// **** add some widgets to the list ****
Node<Widget> wNode = null;
for (int i = 1; i <= 3; i++) {
Widget widget = new Widget(Integer.toString(i * i), i);
wNode = widgets.enqueue(widget);
}
// **** traverse list of widgets ****
for (Node<Widget> w = widgets.head; w != null; w = w.next) {
System.out.println(“main <<< w: ” + w.val.toString());
}
// **** display list of widgets ****
System.out.println(“main <<< widgets: ” + widgets.toString());
System.out.println();
// **** push new widgets before the head in the list ****
wNode = widgets.push(new Widget(“widget_a”, -1));
wNode = widgets.push(new Widget(“widget_b”, -2));
wNode = widgets.push(new Widget(“widget_c”, -3));
// **** traverse list of widgets ****
for (Node<Widget> w = widgets.head; w != null; w = w.next) {
System.out.println(“main <<< w: ” + w.val.toString());
}
// **** display list of widgets ****
System.out.println(“main <<< widgets: ” + widgets.toString());
}
}
Following is the code for the DoubleLinkList class:
package john.linked.list;
public class DoubleLinkList <T> {
// **** constants ****
final int MAX_NODES = 8;
// **** members ****
Node<T> head;
Node<T> tail;
int count;
int maxCount;
/**
* Default constructor.
*/
public DoubleLinkList() {
System.out.println(“DoubleLinkList <<< constructor”);
// **** set members ****
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);
}
// **** set members ****
this.head = null;
this.tail = null;
this.count = 0;
this.maxCount = maxCount;
}
/**
* ENQUEUE a new element after the TAIL of the queue.
*/
public Node<T> enqueue(T val) {
// **** check if list is full ****
if ((this.maxCount != 0) && (this.count >= this.maxCount)) {
throw new ArrayStoreException(“enqueue <<< unexpected count: ” + this.count + ” >= maxCount: ” + this.maxCount);
}
// **** create a new node ****
Node<T> node = new Node<T>(val);
// **** insert node into empty queue ****
if (this.head == null) {
this.head = node;
this.tail = node;
this.count++;
}
// **** append node at the tail of the queue ****
else {
// **** current node points to previous tail node ****
node.prev = this.tail;
// **** previous tail node points to new node ****
this.tail.next = node;
// **** update queue fields ****
this.tail = node;
this.count++;
}
// **** ****
return node;
}
/**
* 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<T> 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<T> 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 one.
*/
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 ****
if (after == this.tail.val) {
enqueue(val);
return;
}
// **** ****
for (Node<T> p = this.head; p != null; p = p.next) {
if (p.val == after) {
Node<T> node = new Node<T>(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<T> node = new Node<T>(val);
node.next = this.head;
node.prev = null;
this.head.prev = node;
this.head = node;
this.count++;
return;
}
// **** insert between ends ****
for (Node<T> p = this.head; p != null; p = p.next) {
if (p.val == before) {
Node<T> node = new Node<T>(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 a single element located at the HEAD of the 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);
}
}
/**
* PUSH element at HEAD of queue.
* Equivalent to push on a stack.
*/
public Node<T> push(T val) {
// **** check if list is full ****
if ((this.maxCount != 0) && (this.count >= this.maxCount)) {
throw new ArrayStoreException(“push <<< unexpected count: ” + this.count + ” >= maxCount: ” + this.maxCount);
}
// **** create a new node ****
Node<T> node = new Node<T>(val);
// **** insert node into empty queue ****
if (this.head == null) {
this.head = node;
this.tail = node;
this.count++;
}
// **** push node at head of queue ****
else {
// **** update node fields ****
node.next = this.head;
// **** update previous head field ****
this.head.prev = node;
// **** update queue fields ****
this.head = node;
this.count++;
}
// **** ****
return node;
}
}
On a following post I will develop the two equivalent classes for the linked lists. After they are tested I will then move to the implementation of the LFU Cache in C / C++.
If you have comments or questions regarding this or any other post 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