How would you implement an LRU cache in Java 6?

private class LruCache<A, B> extends LinkedHashMap<A, B> {
    private final int maxEntries;

    public LruCache(final int maxEntries) {
        super(maxEntries + 1, 1.0f, true);
        this.maxEntries = maxEntries;
    }

    /**
     * Returns <tt>true</tt> if this <code>LruCache</code> has more entries than the maximum specified when it was
     * created.
     *
     * <p>
     * This method <em>does not</em> modify the underlying <code>Map</code>; it relies on the implementation of
     * <code>LinkedHashMap</code> to do that, but that behavior is documented in the JavaDoc for
     * <code>LinkedHashMap</code>.
     * </p>
     *
     * @param eldest
     *            the <code>Entry</code> in question; this implementation doesn't care what it is, since the
     *            implementation is only dependent on the size of the cache
     * @return <tt>true</tt> if the oldest
     * @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry)
     */
    @Override
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
        return super.size() > maxEntries;
    }
}

Map<String, String> example = Collections.synchronizedMap(new LruCache<String, String>(CACHE_SIZE));

class CacheElement {
    private final Object obj;
    private int numberOfUsers = 0;

    CacheElement(Object obj) {
        this.obj = obj;
    }

    ... etc.
}

public class ConcurrentLRUCache<Key, Value> {

private final int maxSize;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

/**
 * @param key - may not be null!
 * @param value - may not be null!
 */
public void put(final Key key, final Value value) {
    if (map.containsKey(key)) {
        queue.remove(key); // remove the key from the FIFO queue
    }

    while (queue.size() >= maxSize) {
        Key oldestKey = queue.poll();
        if (null != oldestKey) {
            map.remove(oldestKey);
        }
    }
    queue.add(key);
    map.put(key, value);
}

/**
 * @param key - may not be null!
 * @return the value associated to the given key or null
 */
public Value get(final Key key) {
    return map.get(key);
}

import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V>
{
    int maxSize;
    int currentSize = 0;

    Map<K, ValueHolder<K, V>> map;
    LinkedList<K> queue;

    public LRUCache(int maxSize)
    {
    	this.maxSize = maxSize;
    	map = new HashMap<K, ValueHolder<K, V>>();
    	queue = new LinkedList<K>();
    }

    private void freeSpace()
    {
    	K k = queue.remove();
    	map.remove(k);
    	currentSize--;
    }

    public void put(K key, V val)
    {
    	while(currentSize >= maxSize)
    	{
    		freeSpace();
    	}
    	if(map.containsKey(key))
    	{//just heat up that item
    		get(key);
    		return;
    	}
    	ListNode<K> ln = queue.add(key);
    	ValueHolder<K, V> rv = new ValueHolder<K, V>(val, ln);
    	map.put(key, rv);
    	currentSize++;
    }

    public V get(K key)
    {
    	ValueHolder<K, V> rv = map.get(key);
    	if(rv == null) return null;
    	queue.remove(rv.queueLocation);
    	rv.queueLocation = queue.add(key);//this ensures that each item has only one copy of the key in the queue
    	return rv.value;
    }
}

class ListNode<K>
{
    ListNode<K> prev;
    ListNode<K> next;
    K value;
    public ListNode(K v)
    {
    	value = v;
    	prev = null;
    	next = null;
    }
}

class ValueHolder<K,V>
{
    V value;
    ListNode<K> queueLocation;
    public ValueHolder(V value, ListNode<K> ql)
    {
    	this.value = value;
    	this.queueLocation = ql;
    }
}

class LinkedList<K>
{
    ListNode<K> head = null;
    ListNode<K> tail = null;

    public ListNode<K> add(K v)
    {
    	if(head == null)
    	{
    		assert(tail == null);
    		head = tail = new ListNode<K>(v);
    	}
    	else
    	{
    		tail.next = new ListNode<K>(v);
    		tail.next.prev = tail;
    		tail = tail.next;
    		if(tail.prev == null)
    		{
    			tail.prev = head;
    			head.next = tail;
    		}
    	}
    	return tail;
    }

    public K remove()
    {
    	if(head == null)
    		return null;
    	K val = head.value;
    	if(head.next == null)
    	{
    		head = null;
    		tail = null;
    	}
    	else
    	{
    		head = head.next;
    		head.prev = null;
    	}
    	return val;
    }

    public void remove(ListNode<K> ln)
    {
    	ListNode<K> prev = ln.prev;
    	ListNode<K> next = ln.next;
    	if(prev == null)
    	{
    		head = next;
    	}
    	else
    	{
    		prev.next = next;
    	}
    	if(next == null)
    	{
    		tail = prev;
    	}
    	else
    	{
    		next.prev = prev;
    	}
    }
}

private void moveToFront(int index) {
        if (listHead != index) {
            int thisNext = nextElement[index];
            int thisPrev = prevElement[index];
            nextElement[thisPrev] = thisNext;
            if (thisNext >= 0) {
                prevElement[thisNext] = thisPrev;
            } else {
                listTail = thisPrev;
            }
            //old listHead and new listHead say new is 1 and old was 0 then prev[1]= 1 is the head now so no previ so -1
            // prev[0 old head] = new head right ; next[new head] = old head
            prevElement[index] = -1;
            nextElement[index] = listHead;
            prevElement[listHead] = index;
            listHead = index;
        }
    }

package util.collection;

private final int maxSize;
private int currentSize = 0;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

private synchronized void freeSpace() {
    Key key = queue.poll();
    if (null != key) {
        map.remove(key);
        currentSize = map.size();
    }
}

public void put(Key key, Value val) {
    if (map.containsKey(key)) {// just heat up that item
        put(key, val);
        return;
    }
    while (currentSize >= maxSize) {
        freeSpace();
    }
    synchronized(this) {
        queue.add(key);
        map.put(key, val);
        currentSize++;
    }
}

public Value get(Key key) {
    return map.get(key);
}