How to shift items in an array?

Question

I have an array of items that are time sensitive. After an amount of time, the last item needs to fall off and a new item is put at the beginning.

What is the best way to do this?

Answer 1

Use a Queue instead.

Answer 2

By using a Queue, preferably one implemented using a linked-list.

Answer 3

I would suggest using a queue, just a special instance of an array or list. When your timed event occurs, pop the last item from the queue, and then push your new item on.

Answer 4

Have a look at using a Queue rather than a simple array.

Answer 5

A queue would work if there a fixed number of items.

Given that the 'amount of time' is known, how about a SortedDictionary with a DateTime key and override the Add method to remove all items with keys that are too old.

Answer 6

LinkedList<T> has AddFirst and RemoveLast members that should work perfectly.

EDIT: Looking at the Queue docs, it seems they use an internal array. As long as the implementation uses a circular-array type algorithm performance should be fine.

Answer 7

In csharp 3 you can do:

original = new[] { newItem }.Concat(
    original.Take(original.Count() - 1)).ToArray()

But you are probably better off using a specialised datastructure

Answer 8

Queue is great for FIFO arrays. For generic array handling, use List(T)'s Insert(0, x) and RemoveAt(0) methods to put or remove items in front of the list, for example.

Answer 9

Probably the easiest way to do this with an array is to use a circular index. Rather than always looking at array[n], you would reference array[cIndex] (where cIndex referrs to the item in the array being indexed (cIndex is incremented based on the arraySize (cIndex % arraySize)).

When you choose to drop the oldest item in the array, you would simply reference the element located at ((cIndex + (arraySize - 1)) % arraySize).

Alternatively, you could use a linkedList approach.

Answer 10

Technically you need a deque. A queue has items pushed and popped off one end only. A deque is open at both ends.

Most languages will allow array manipulation, just remove the first element and put another one on the end.

Alternatively you can shift every element, by looping. Just replace each element (starting from the oldest) with its neighbour. Then place the new item in the last element.

If you know that your deque won't go above a certain size, then you can make it circular. You'll need two pointers to tell you where the two ends are though. Adding and removing items, will increase/decrease your pointers accordingly. You'll have to detect a buffer overflow condition (i.e. your pointers 'cross'). And you'll have to use modular arithmetic so your pointers go in a circle around the array.

Or you could time stamp each element in the array and remove them when they become too 'old'. You can either do this by keeping a separate array indexed in the same way, or by having an array of two element arrays, with the time stamp stored in one of the sub-elements.

Answer 11

If you're looking for the fastest way of doing this, it's going to be a circular array: you keep track of your current position in the array (ndx), and the end of the array (end), so when you insert an item, you implicitly eliminate the oldest item.

A circular array is the fastest implementation of a fixed-size queue that I know of.

For example, in C/C++ it would look like this for ints (quitting when you get a 0):

int queue[SIZE];
int ndx=0;      // start at the beginning of the array
int end=SIZE-1;
int newitem;
while(1){
  cin >> newitem;
  if(!newitem)  // quit if it's a 0
    break;
  if(ndx>end)   // need to loop around the end of the array
    ndx=0;
  queue[ndx] = newitem;
  ndx++
}

Lots of optimization could be done, but if you want to built it yourself, this is the fastest route.

If you don't care about performance, use a shipped Queue object because it should be generalized.

It may or may not be optimized, and it may not support a fixed size list, so be sure to check the documentation on it before using.