CareerCup

"SPLAY TREES"--these could be the best DS that provide similar behaviour as the cache.

They are designed to provide a faster access to the same piece of data for the second time. They achieve this by there self-balancing nature.

i think linked list is best option to act as a "cache" .. because we need to traverse for a particular object in cache may be in forward or in backward direction with respect to current position ... this cant be used effectively in the stack or queue (even in a circular queue)... maintaining linked list is also very easier thing ... that's why i think a "double circular" might be a best option ...

What about hashed doubly link list?

A scenario for using replicated local cache is when the cache server is remote/ distributed/ shared. In that case, if we fetch same data item many times in a program, we could think about caching it in local memory/ heap.

In java, a data structure for replicated cache would be Map.

import java.util.Date;
import java.util.Map;

// distributed, remote cache 
class RealCache<K,V> {
  V v;
  public V get(K k) {
    return v;
  }
  
  public void add(K k,V v) {
    // ... real cache implementation ...
  }
}

// local in-vm cache
class CacheValue<V> {
  V v;
  Date localCache = new Date();
}

class LCache<K,V> {
  RealCache<K,V> rc;
  Map<K,CacheValue<V>> map;
  static Long msecToCacheFor;

  public V get(K k) {
    Date now = new Date();
    CacheValue<V> vc = map.get(k);
    if ( vc != null && vc.localCache.getTime()-now.getTime() < msecToCacheFor ) {
      return vc.v;
    }
    else {
      if ( vc != null ) map.remove(k);
      V v = rc.get(k);
      if ( v != null ) {
        // add it to local cache
        map.put(k, new CacheValue<V>());
      }
      return v;
    }
  }
  
  public void add(K k, V v) {
    rc.add(k, v);
  }

}

A "Perfect Hash table" would do the lookup in O(1) time!...
which is similar to fast lookup in cache memory!...

doubly linked list

cant we use optimal binary search trees?

What do you mean by "replicated as cache"?