Removing older values from a List

Question

I have a list that I want to be able to store 20 values. What would be a good approach to deleting older values. A better example would be, imagine a change history and I wan't to be able to store 20 latest changes, while older ones go away.

Is there a special thing in C# that will let me do that or do I have to either make my own or use the Remove function.

EDIT1: Alright, how about storing 4000 - 10000 values, suddenly a linked-list looks attractive.

EDIT2: Circular list is good BUT, I don't want to be able to loop my older values.

EDIT3: For my problem, random access isn't too important, but sequential access is.

Answer 1

use a Queue. each time you enqueue into the queue check if size == 20. If so, dequeue/pop one element

Answer 2

There is no built in collection that handles that, but you could easily make one:

public class LimitedList<T> : List<T> {

  public new void Add(T item) {
    if (Count == 20) {
      RemoveAt(0);
    }
    base.Add(item);
  }

}

Note though that this currently only handles the limit when items are added using the Add method, and not other methods like AddRange and Insert. Also, as SLask pointed out, the List<T> class isn't specifically intended to be inherited (although it's not marked as final), so a more robust implementation would encapsulate the list instead of inheriting from it.

Note also that it's inefficient to remove the first item in a large list, but with as few items as 20, there is no problem. A LinkedList would handle that better if you need a much larger collection.

Answer 3

Sounds like you're describing a ring buffer. http://stackoverflow.com/questions/590069/how-would-you-code-an-efficient-circular-buffer-in-java-or-c might be helpful.

Answer 4

You can make your own list class:

public class BoundedList<T> : Collection<T> {
    public int MaxSize { get; private set; }
    public BoundedList(int MaxSize) : base(new List<T>(maxSize)) {
        MaxSize = maxSize;
    }
    protected override void InsertItem(T item, int index) {
        base.InsertItem(item, index)
        if (Count > MaxSize)
            Remove(0);
    }
}

Answer 5

I think you need priority Q and you can define priority randomly. before adding each item, increase remained items priority.

Answer 6

Alright I finally got a chance to think about this problem myself and found a good compromise without going through too much effort. Why not just use a linked list.

1. For a history type of implementation, just keep track of the pointer.
2. It will still be linear time for sequencing operations.
3. Removing the last value can be done in constant time.

I guess I failed to mention that random access wasn't too important...