3

I have a list of items I am adding to, however this special list will delete anything past a given capacity. Note the order is maintained.

For the life of me, I can't think of the name of such a construct.

Consider

data = new SpecialListType(3); // set capacity to 3

data.Add("A");
data.Add("B");
data.Add("C");
data.Add("D");

data.Dump(); // returns {"B", "C", "D"}

What is this? Some form of a Set or Buffer? And is there a framework implementation of this in Java and .NET?

  • 1
    A data structure behaving like this is known as a cache. – Mike Nakis Apr 18 '15 at 8:58
  • 1
    Any data structure can be a "cache" if it's used for caching. @jay: does the structure necessarily preserve the order of the last three elements, or could they come back in any order? If the former, then manilo's answer is correct. – Ixrec Apr 18 '15 at 11:58
  • 1
    Clojure core.async has a channel with the same semantics that they call a "sliding buffer" which I think is a good name. There is also a "dropping buffer" channel which would have not put "D" into the list and kept "A" in. – WuHoUnited Apr 18 '15 at 13:43
  • @Ixrec: yes the order is important, I've updated my question to reflect that – jay Apr 19 '15 at 4:19
  • Regarding the drive-by close votes - please state your reasoning. I'll be happy to reword – jay Apr 19 '15 at 4:20
8

It's a bounded queue (a first-in-first-out queue with a fixed capacity).

This particular queue always allows addition of elements and silently remove head element for newly added element (when full).

In Java there is the CircularFifoQueue that works exactly that way (see also Size-limited queue that holds last N elements in Java).

For .NET you'd take a look at:

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.