最有效的结构，快速访问随机元素+最后一个元素的一个标准

你可以尝试的第一件事是消除OrderBy -所有你需要的是最小键，不需要排序得到它:

if (_pendingTimeSlot.Count > _capacity) {
    // No Enumerable.Min(DateTime), so doing it manually
    var oldestTimeStamp = DateTime.MaxValue;
    foreach (var key in _pendingTimeSlot.Keys)
        if (oldestTimeStamp > key) oldestTimestamp = key;
    _pendingTimeSlot.Remove(oldestTimeStamp);
    //Additional work here to log/handle this case
}

那么SortedDictionary呢，它肯定是一个选项，尽管它会消耗更多的内存。由于它是排序的，您可以简单地使用sortedDictionary.First()来获取具有最小键的键值对(因此在您的示例中是最老的元素)。

UPDATE:这是一种使用字典进行快速查找和使用有序双链表进行其他场景的混合方法。

class MyItem
{
    // ...
}
class TimeSlot
{
    public readonly DateTime TimeStamp;
    public TimeSlot(DateTime timeStamp)
    {
        TimeStamp = timeStamp;
        // ...
    }
    public bool IsComplete = false;
    public void HandleItemReceived(MyItem item)
    {
        // ...
    }
    // Dedicated members
    public TimeSlot PrevPending, NextPending;
}
class Synhronizer
{
    const int _capacity = 500;
    Dictionary<DateTime, TimeSlot> pendingSlotMap = new Dictionary<DateTime, TimeSlot>(_capacity + 1);
    TimeSlot firstPending, lastPending;
    //Let's assume that this method is not called concurrently, and only once per "MyItem"
    public void HandleItemReceived(DateTime timeStamp, MyItem item)
    {
        TimeSlot slot;
        if (!pendingSlotMap.TryGetValue(timeStamp, out slot))
        {
            slot = new TimeSlot(timeStamp);
            Add(slot);
            //Sometimes we don't receive all the items for one timestamps, which may leads to some ghost-incomplete TimeSlot
            if (pendingSlotMap.Count > _capacity)
            {
                // Remove the oldest, which in this case is the first
                var oldestSlot = firstPending;
                Remove(oldestSlot);
                //Additional work here to log/handle this case
            }
        }
        slot.HandleItemReceived(item);
        if (slot.IsComplete)
        {
            PushTimeSlotSyncronized(slot);
            Remove(slot);
        }
    }
    void Add(TimeSlot slot)
    {
        pendingSlotMap.Add(slot.TimeStamp, slot);
        // Starting from the end, search for a first slot having TimeStamp < slot.TimeStamp
        // If the TimeStamps almost come in order, this is O(1) op.
        var after = lastPending;
        while (after != null && after.TimeStamp > slot.TimeStamp)
            after = after.PrevPending;
        // Insert the new slot after the found one (if any).
        if (after != null)
        {
            slot.PrevPending = after;
            slot.NextPending = after.NextPending;
            after.NextPending = slot;
            if (slot.NextPending == null) lastPending = slot;
        }
        else
        {
            if (firstPending == null)
                firstPending = lastPending = slot;
            else
            {
                slot.NextPending = firstPending;
                firstPending.PrevPending = slot;
                firstPending = slot;
            }
        }
    }
    void Remove(TimeSlot slot)
    {
        pendingSlotMap.Remove(slot.TimeStamp);
        if (slot.NextPending != null)
            slot.NextPending.PrevPending = slot.PrevPending;
        else
            lastPending = slot.PrevPending;
        if (slot.PrevPending != null)
            slot.PrevPending.NextPending = slot.NextPending;
        else
            firstPending = slot;
        slot.PrevPending = slot.NextPending = null;
    }
    void PushTimeSlotSyncronized(TimeSlot slot)
    {
        // ...
    }
}

一些附加用法:

从旧的到最新的迭代:

for (var slot = firstPending; slot != null; slot = slot.NextPending)
{
    // do something
}

从最旧的到最新的迭代，并根据标准删除项:

for (TimeSlot slot = firstPending, nextSlot; slot != null; slot = nextSlot)
{
    nextSlot = slot.NextPending;
    if (ShouldRemove(slot))
        Remove(slot);
}

对于反向场景也是一样，但是使用lastPending和PrevPending成员代替。

下面是一个简单的示例。列表中的insert方法消除了元素交换。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Data> inputs = new List<Data>() {
                new Data() { date = DateTime.Parse("10/22/15 6:00AM"), data = "abc"},
                new Data() { date = DateTime.Parse("10/22/15 4:00AM"), data = "def"},
                new Data() { date = DateTime.Parse("10/22/15 6:30AM"), data = "ghi"},
                new Data() { date = DateTime.Parse("10/22/15 12:00AM"), data = "jkl"},
                new Data() { date = DateTime.Parse("10/22/15 3:00AM"), data = "mno"},
                new Data() { date = DateTime.Parse("10/22/15 2:00AM"), data = "pqr"},
            };
            Data data = new Data();
            foreach (Data input in inputs)
            {
                data.Add(input);
            }
        }
    }
    public class Data
    {
        public static List<Data> sortedData = new List<Data>();
        public DateTime date { get; set; }
        public string data { get; set;}

        public void Add(Data newData)
        {
            if(sortedData.Count == 0)
            {
                sortedData.Add(newData);
            }
            else
            {
               Boolean added = false;
               for(int index = sortedData.Count - 1; index >= 0; index--)
               {
                   if(newData.date > sortedData[index].date)
                   {
                       sortedData.Insert(index + 1, newData);
                       added = true;
                       break;
                   }
               }
               if (added == false)
               {
                   sortedData.Insert(0, newData);
               }
            }
        }
    }
}​