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?

Jay Wick
  • 375
  • 2
  • 10
  • 1
    A data structure behaving like this is known as a cache. – Mike Nakis Apr 18 '15 at 08: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 Wick Apr 19 '15 at 04:19
  • **Regarding the drive-by close votes - please state your reasoning.** I'll be happy to reword – Jay Wick Apr 19 '15 at 04:20

1 Answers1

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:

Community
  • 1
manlio
  • 4,166
  • 3
  • 23
  • 35