What C# Data Structure Supports The Following?

Question

I need a C# data structure that works in the following way:

1. Define it with a static size
2. Adding new data to end of list
3. Oldest data falls off.
4. Random access of data elements

Example: If I define a structure of 5 elements and added the following

1,2,3,4,5,6,7,8

The data structure would look like the following:

4,5,6,7,8

I'm not sure which structure will work in this way. Vector? List? Stack? The data structure supports a static size like an array and push data that pushes off old data.

Stack/queue doesn't provide random access. List doesn't have a "push" operation.

Perhaps a LinkedList and add custom operation for "push" that removes the first element? LinkList random access is o(n) operation though.

Answer 1

For maximum efficiency, that would probably be a custom class implementing a circular buffer.

Just have a fixed size array created at instantiation time to hold the data. In addition have a start index, a size member and a capacity so you know how much data is in the buffer and where it starts.

So, to start with, your list contains no data, the start position is 0 and the size is 0.

When you add an item, it goes into element (start + size) % capacity and size is incremented if it's not yet at capacity. If it was at capacity, you increment start as well, wrapping around if need be: start = (start + 1) % capacity.

To get an element at index n from the list, you actually adjust it with start:

return element[(start + n) % capacity];

I haven't covered removing the start of the list since that's not in your specs. However, it's a simple check to ensure size is not 0, then extracting the item at element[start], then incrementing start with the same wraparound shown above.

In pseudo-code (untested but should be close):

def listNew (capacity):
    me = new object
    me.capacity = capacity
    me.data = new array[capacity]
    me.start = 0
    me.size = 0
    return me

def listAdd (me, item):
    if me.size = me.capacity:
        me.data[me.start] = item
        me.start = (me.start + 1) % me.capacity
    else:
        me.data[(me.start + me.size) % me.capacity] = item
        me.size = me.size + 1

def listGet (me, index):
    if index > size:
        return 0 # or raise error of some sort
    return me.data[(me.start + index) % me.capacity]

def listRemove (me):
    if size == 0:
        return 0 # or raise error of some sort
    item = me.data[(me.start + index) % me.capacity]
    me.start = (me.start + 1) % me.capacity
    me.size = me.size - 1
    return item

All of these operations are O(1) time complexity, as requested.

For your particular example of adding the numbers 1 through 8 to a five-element list, you would end up with:

  0   1   2   3   4 <--- index
+---+---+---+---+---+
| 6 | 7 | 8 | 4 | 5 |
+---+---+---+---+---+
              ^
              +--------- start    = 3
                         size     = 5
                         capacity = 5

That way, extracting virtual index 3 (the fourth number) from the buffer would give you an actual index of:

  (start + 3) % capacity
= (  3   + 3) %    5
=       6     %    5
=             1