Имя структуры данных: массив комбинаций / связанный список
Я придумал структуру данных, которая сочетает в себе некоторые преимущества связанных списков с некоторыми преимуществами массивов фиксированного размера. Это кажется мне очень очевидным, и поэтому я ожидаю, что кто-то подумал об этом и уже назвал его. Кто-нибудь знает, как это называется:
Возьмите небольшой массив фиксированного размера. Если количество элементов, которые вы хотите поместить в ваш массив, больше, чем размер массива, добавьте новый массив и любые другие указатели между старым и новым.
Таким образом, у вас есть:
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
———————————— ————————————
редактироватьДля справки: этот алгоритм обеспечивает довольно плохую производительность при добавлении / удалении в худшем случае и не намного лучше среднего. Большим преимуществом для моего сценария является улучшенная производительность кэша для операций чтения.
Изменить повторную наградуОтвет Antal S-Z был настолько полным и хорошо изученным, что я хотел предоставить им вознаграждение за это. Очевидно, переполнение стека не позволяет мне принять ответ, как только я предложу вознаграждение, так что мне придется подождать (правда, я несколько злоупотребляю системой намерений, но это во имя вознаграждения кого-то за отличное вознаграждение). ответ). Конечно, если кто-тоделает удастся дать им лучший ответ, больше власти, и они, скорее всего, получат за это награду!
Изменить имена: Мне не интересно, чтовы бы Назовите это, если только вы не назовете это так, потому что это то, что назвали бы авторитеты по этому вопросу. Если это имя, которое вы только что придумали, мне это не интересно. То, что я хочу, это имя, которое я могу найти в учебниках и с Google. (Также вот совет: ответ Антала - это то, что я искал. Если ваш ответ не является «развернутым связанным списком» безочень хорошая причина, это просто неправильно.)