Мне нужно спроектировать структуру данных, которая обеспечивает доступ к массиву по индексу аналогично общему массиву. Но после ссылки на i-й элемент я должен переместить его в начало. Это легко сделать с помощью связанного списка и O (n) сложности доступа , но мне нужен способ для повышения производительности. Если вы sh, вы можете предположить, что вставка в такую структуру данных запрещена.
Например:
T=[5, 4, 9, 45] - Initial state
1. Access to 2-th element => T[2] returns 9, now T=[9,5,4,45](We move 2-th element to the beginning)
2. Access to 3-th element => T[3] returns 45, now T=[45,9,5,4](We move 3-th element to the beginning)
3. T[0] returns 45, T=[45,9,5,4]
4. T[2] returns 5, T=[5,45,9,4]
Надеюсь, проблема ясна. Пожалуйста, предложите любые связанные ссылки или фрагменты кода.
Отредактировано: я слышал о Декартовом дереве и веревках. Какой из них лучше применить здесь и почему?