Это, кстати, в тему о том, что на не сильно большом количестве элементов лучше забыть о всяких больших O() и что вставка в начало/середину массива это O(N), ужас-ужас, нужно на связный список переделывать.

Пока не побенчмаркаешь — вообще непонятно, с очень большой вероятностью memmove будет сильно быстрее, чем затем случайные обращения к памяти узлов этого списка, разбросанные то там, то тут.