Best way to have an list of indices which changes order

• 09-28-2008
laertius
Best way to have an list of indices which changes order

I need a list of indices which specify the order in which the elements of an array will be accessed for a specific purpose (the order of the accessed array must stay constant, it's only for this special case that its elements must be accessed in a variable order). This order will change in the following way: When one index is 'selected' it should move from its current position in the list to the first position.

The number of elements is relatively small, i.e. probably < 15 in most cases.

What's the best way to do this? As a linked list, or as an array of ints that gets rebuilt every time, or some other way?

Thanks.
• 09-28-2008
tabstop
A linked list will always require you to pop a link and set a link to remove an item, and the same to add an item at the front, while an array will require you to move on average n/2 items each time.

If n<15, I doubt that any efficiency here would be noticed by anyone, anywhere. In fact, you'd probably have to work pretty hard to come up with an algorithm that didn't finish more-or-less instantaneously. So it probably comes down to what ties in with the rest of your code the best (if this is the only linked list, it may not be worth the hassle, etc.)
• 09-28-2008
nonoob
Why not just exchange the value in the indecies array with its first one? Or did you mean that when an element is selected, all other elements must necessarily FOLLOW it in their same contiguous sequence, such as if your selection is part of a sort algorithm or some "most recently used" descending order list?
• 09-28-2008
laertius
Yes exactly. "Most recently used" is what I'm after.
• 09-28-2008
nonoob
In that case, if there are only 15, then an array of ints is adequate. Move the elements down one to fill the gap left by the 'selected' one. The 'selected' one then goes to the top.
• 09-29-2008
```for(i = 0; i < 15; i++)   index[i] = i;```
```for(i = 0; i < 15; i++)   printf("&#37;s", stringarray[index[i]]);```