Я придумал структуру данных, которая сочетает в себе некоторые преимущества связанных списков с некоторыми преимуществами массивов фиксированного размера. Мне кажется очень очевидным, и поэтому я ожидаю, что кто-то подумает об этом и назвал его уже. Кто-нибудь знает, что это называется:
Возьмите небольшой массив фиксированного размера. Если количество элементов, которые вы хотите разместить в вашем массиве, больше, чем размер массива, добавьте новый массив и любые указатели, которые вам нравятся между старым и новым.
Таким образом, у вас есть:
Static array
—————————————————————————
|1|2|3|4|5|6|7|8|9|a|b|c|
—————————————————————————
Linked list
———— ———— ———— ———— ————
|1|*->|2|*->|3|*->|4|*->|5|*->NULL
———— ———— ———— ———— ————
My thing:
———————————— ————————————
|1|2|3|4|5|*->|6|7|8|9|a|*->NULL
———————————— ————————————
Изменить. Для справки этот алгоритм обеспечивает довольно плохую работу по снижению/удалению в худшем случае и не намного лучше среднего. Большим преимуществом для моего сценария является улучшенная производительность кеша для операций чтения.
Изменить re bounty: ответ Antal S-Z был настолько полным и хорошо исследованным, что я хотел предоставить им награду за это. Очевидно, Qaru не позволяет мне принять ответ, как только я предложил щедрость, так что мне придется подождать (по общему признанию, я злоупотребляю системой начисления завещания несколько, хотя она во имя вознаграждения кого-то за отличную ответ). Конечно, если кому-то удастся предоставить лучший ответ, больше власти для них, и они могут, безусловно, иметь щедрость!
Изменить имена имен. Меня не интересует то, что вы бы назвали, если вы не назовете это, потому что то, что власти по этому вопросу назовут. Если это имя вы только что придумали, мне это неинтересно. Я хочу это имя, которое я могу найти в учебниках и в Google. (Кроме того, здесь совет: Antal ответ - это то, что я искал. Если ваш ответ не "разворачивается связанный список" без серьезной причины, это просто неправильно.)
