[gloomyBrain]

Я бы использовал связанный список + хэш. В хэше бы хранил пары "индекс - элемент", в связааном списке - сами элементы в текущей последовательности. При таком раскладе получаем быструю вставку до/после определенного элемента + доступ по индексам. Пример приводить не буду =)