Removing oldest inserted data from sorted list

Question

I have a List of objects that expands over time as more and more data gets added to it but will have a fixed maximum size at some point.

public class Calculation 
{
  public List<DataUnit> DataUnits { get; set; } = new();

  public void AddSorted(DataUnit unit)
  {
    int index = DataUnits.BinarySearch(unit);
    DataUnits.Insert((index>=0) x : ~x, unit);
  }

  public void AddData(DataUnit unit)
  {
    AddSorted(unit);
    if(DataUnits.Count > 30)
    {
      // i need some sort of solution here
      DataUnits.RemoveOldest();
    }
  }

  public void SomeCalculation()
  {
    // performs some calculation, that is O(1) with a sorted list and O(N) with a non sorted list
  }
    
}

The catches are restrictions to performance, RAM and time. The actual code (not the dummy one above), will have a lot of data coming in (something around 1000-2000 dataunits) within a 1 second time frame on a limited ressources machine. We have to perform calculations on this list, which is just way faster to do on a sorted list. And, since new data will be coming in each second, all the calculations have to be done within a second.

What would be the most optimal way of implementing this?

I thought about either sorting the list before each calculation separately, but I am afraid that O(sqrt(n)) will just not cut it. My second Idea would be a second list, that just preserves the time of insertion sorting, but with a lot of data, I think we might hit a resource limit when holding two list of those dataunits.

// EDIT

Additional Information about the DataUnit

public class DataUnit : IComparable
{
  public IComparable Data { get; set; }
  public int CompareTo(object? o)
  {
    if(o is DataUnit other)
    {
      return Data.CompareTo(other.Data);
    }
    return 0;
  }
}

Properties about the Calculation the SomeCalculation method performs an intensiv calculation over all the present data. This calculation only works with a sorted list by its Property Data (some index math magic, not important here).

So in the end, the List DataUnits must be sorted by Data. Since we have a lot more calls of SomeCalculation then AddData my implementation uses a list with sorted insertion rather than sorting the list every time we call SomeCalculation.

Problem: The DataUnits List reaches a fixed size (for example 30 elements), and will preserve its size after that. If one element gets added to the list, the oldest DataUnit object should be removed (and therefore not included in the calculation)

Answer 1

I'm not sure I understand you correctly, but according to MSDN List.Add appends element to the end of the list. Wouldn't be easiest to simply Add elements (which will always go to the end), count their numbers and once it reaches threshol remove first one? (aka the oldest one?) Of course this expects you do not change order of elements in the list. Something like cyclic buffer.

Something like this:

public void AddData(DataUnit unit)
{
   DataUnits.Add(unit);
   if (DataUnits.Count() > 30)
   {
      DataUnits.RemoveAt(0);
   }
}

Edit: Mathew Watson comment made me think a little bit. I believe this way you can have sorted array and remove last element:

  public class Calculation 
  {
    private DataUnit lastElement = null;

    public List<DataUnit> DataUnits { get; set; } = new();

    public void AddSorted(DataUnit unit)
    {
      int index = DataUnits.BinarySearch(unit);
      DataUnits.Insert((index>=0) x : ~x, unit);
    }

    public void AddData(DataUnit unit)
    {
      AddSorted(unit);

      // you don't need to use LINQ, you may test it against Count
      if (DataUnits.Any() == false)
      {
        this.lastElement = unit;
      }

      if(DataUnits.Count > 30)
      {
        if (this.lastElement != null)
        {
          DataUnits.Remove(this.lastElement);
          this.lastElement = unit;
        }
      }
    }

because all you need to know is that between some element and 30th element were 30 additions (and no removal). So all you need to do is to remember current element, count 30 additions and then remove that element and the one you're adding will be new candidate for removal.