The motivation for this post was a LeetCode challenge titled: LFU Cache for which I would like to develop a set of put() and get() methods that operate in O(1) running time. If you wish to take a look at the challenge you may find it at the following URL: https://leetcode.com/problems/lfu-cache/
The actual challenge does not require O(1) methods but I read the following statement:
Follow up:
Could you do both operations in O(1) time complexity?
Challenge as a Least Frequently Used (LFU) link. It takes you to: https://en.wikipedia.org/wiki/Least_frequently_used which is a Wikipedia page. Go to the bottom part of the page and you will find a link An O(1) algorithm for implementing the LFU cache eviction scheme which takes you to a PDF of the same name written by Professor Ketan Shah, et.al. I downloaded and read the paper a few times. It is quite interesting because of the possible uses when caching objects on the Internet.
It seemed to me that Java was not going to be the best language to 
implement the code in (another challenge). That said, I went ahead and attempted it. As you can see in the PDF, there are references to links in the doubly linked list used. The LinkedList class in Java does not appear to be a good fit. I decided to go ahead and implement a single (just for kicks and giggles) and a doubly linked list classes. They should help with the follow up challenge.
I will start with my own implementation of a single linked list. I will be using it for future challenges and to test other code as needed. After the single link list class I will implement in my next post a doubly inked list with the same functionality as the single link list. That calls will be used to work on the LFU Cache implementation. I am also considering an implementation in C / C++. Not so sure at this time.
Following is a screen capture of the Eclipse IDE console after the test:
main <<< list: 0 1 2 3 4 5 6 <== display list after inserting 7 elements
main <<< peek: 0 <== peek at the list
main <<< find(0): true <== found 0 in list
main <<< delete(0): 0
main <<< find(6): true <== found 6 in list
main <<< delete(6): 6
main <<< find(3): true <== found 3 in list
main <<< delete(3): 3
main <<< find(9999): false <== did NOT find 9999 in list
main <<< count: 4 <== after deleting 3 node
main <<< list: 1 2 33 4 5 66 <== insert after before 2 elements
main <<< count: 6 <== current count
main <<< list: 0 1 2 33 34 4 5 55 66 <== insert before 3 elements
main <<< count: 9
main <<< dequeue: 0
main <<< dequeue: 1
main <<< dequeue: 2
main <<< dequeue: 33
main <<< dequeue: 34
main <<< dequeue: 4
main <<< dequeue: 5
main <<< dequeue: 55
main <<< dequeue: 66
main <<< count: 0 <== after deleting all elements one by one
The Java test code follows:
package john.linked.list;
public class Solution {
/**
* Test code
*/
public static void main(String[] args) {
// **** ****
final int MAX_COUNT = 7;
// **** instantiate a new list of integers ****
SingleLinkList<Integer> list = new SingleLinkList<Integer>();
// **** insert to list ****
for (int i = 0; i < MAX_COUNT; i++) {
list.insert(i);
}
System.out.println(“main <<< list: ” + list.toString());
// **** peek into the queue ****
System.out.println(“main <<< peek: ” + list.peek());
// **** delete element(s) ****
boolean found = list.find(0);
System.out.println(“main <<< find(0): ” + found);
System.out.println(“main <<< delete(0): ” + list.delete(0));
found = list.find(6);
System.out.println(“main <<< find(6): ” + found);
System.out.println(“main <<< delete(6): ” + list.delete(6));
found = list.find(3);
System.out.println(“main <<< find(3): ” + found);
System.out.println(“main <<< delete(3): ” + list.delete(3));
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());
// **** insert after ****
list.insertAfter(2, 33);
list.insertAfter(5, 66);
System.out.println(“main <<< list: ” + list.toString());
System.out.println(“main <<< count: ” + list.getCount());
// **** insert before ****
list.insertBefore(1, 0);
list.insertBefore(66, 55);
list.insertBefore(4, 34);
System.out.println(“main <<< list: ” + list.toString());
System.out.println(“main <<< count: ” + list.getCount());
// **** dequeue from list ****
while (!list.isEmpty()) {
System.out.println(“main <<< dequeue: ” + list.dequeue());
}
// **** get element count ****
System.out.println(“main <<< count: ” + list.getCount());
}
}
As usual, the test code for each method was included before implementing the associated method. I cannot emphasize enough how important it is to develop software in a continuous cycle from architecture, design, implementation and testing.
The code for the Node class follows:
package john.linked.list;
public class Node <T> {
// **** ****
public T val;
public Node next;
public Node prev;
/**
* Constructor
*/
public Node(T val) {
this.val = val;
this.next = null;
this.prev = null;
}
}
Finally the Java code for the SingleLinkList class follows:
package john.linked.list;
public class SingleLinkList <T> {
// **** members ****
Node<T> head;
Node<T> tail;
int count;
int maxCount;
/**
* Default constructor.
*/
public SingleLinkList() {
}
/**
* Constructor.
*/
public SingleLinkList(int maxCount) {
// **** verify argument ****
if (maxCount < 0) {
throw new IllegalArgumentException(“SingleLinkList <<< unexpected maxCount: ” + maxCount);
}
// **** ****
this.maxCount = maxCount;
this.head = null;
this.tail = null;
this.count = 0;
}
/**
* @return the count
*/
public int getCount() {
return this.count;
}
/**
* @return the maxCount
*/
public int getMaxCount() {
return maxCount;
}
/**
* @param maxCount the maxCount to set
*/
public void setMaxCount(int maxCount) {
this.maxCount = maxCount;
}
/**
* Insert value before specified one.
*/
public void insertBefore(T before, T val) {
// **** insert before head ****
if (head.val == before) {
Node node = new Node(val);
node.next = this.head;
this.head = node;
this.count++;
return;
}
// **** insert between ends ****
Node q = null;
for (Node p = this.head; p != null; p = p.next) {
// **** insert before this node ****
if (p.val == before) {
Node node = new Node(val);
q.next = node;
node.next = p;
this.count++;
return;
}
// **** q follows p ****
q = p;
}
}
/**
* Insert value after specified value.
*/
public void insertAfter(T after, T val) {
// **** 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;
p.next = node;
this.count++;
return;
}
}
}
/**
* Delete value from list.
*/
public T delete(T val) {
// **** traverse list looking for the node to delete ****
Node<T> q = null;
for (Node p = this.head; p != null; p = p.next) {
// **** check if we need to delete this node ****
if (p.val == val) {
// **** remove head node ****
if (p == this.head) {
this.head = this.head.next;
}
// **** remove tail node ****
else if (p == this.tail) {
this.tail = q;
}
// **** remove node between ends ****
else {
q.next = p.next;
}
// **** ****
this.count–;
// **** ****
return val;
}
// **** increment q ****
q = p;
}
// **** ****
throw new IllegalArgumentException(“SingleLinkList <<< val: ” + val + ” not in list”);
}
/**
* Insert an element at the tail of the queue.
*/
public void insert(T v) {
// **** create a new node ****
Node<T> node = new Node<T>(v);
// **** append the node to an empty list ****
if (this.head == null) {
this.head = node;
this.tail = node;
this.count++;
return;
}
// **** append node after the tail of the list ****
this.tail.next = node;
// **** update node fields ****
this.tail = node;
this.count++;
}
/**
* Remove the node at the head of the queue.
*/
public T dequeue() {
// **** check if the queue is empty ****
if (this.head == null) {
return null;
}
// **** ****
Node<T> n = this.head;
T val = (T)n.val;
// **** update fields in the queue ****
this.count–;
if (this.count == 0) {
this.head = null;
this.tail = null;
} else {
this.head = n.next;
}
// **** return the value removed from the queue ****
return 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;
}
}
// **** ****
return false;
}
/**
* Determine if the queue is empty.
*/
public boolean isEmpty() {
return (this.count <= 0);
}
/**
* Peek at the element at the head of the queue.
*/
public T peek() {
// **** check if queue is empty ****
if (count == 0) {
throw new IllegalArgumentException(“peek <<< unexpected maxCount: ” + maxCount);
}
// **** return value at head of queue ****
return (T)this.head.val;
}
/**
* Build a string with the elements in the list.
*/
public String toString() {
StringBuilder str = new StringBuilder();
// **** ****
for (Node<T> p = this.head; p != null; p = p.next) {
str.append(p.val.toString() + ” “);
}
// **** ****
return str.toString();
}
}
Like I said, will move to replicate the SingleLinkList class using double links. The implementation should be ready later this evening or tomorrow early morning.
If you have comments or questions regarding this post or any other 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