Similarly, Solidity Arrays are fixed to the size you initialize them with.
Solidity arrays are not fixed size. Here's an example snippet from a contract I use to test gas optimization:
contract Gas {
// this structure must fit into a 256 bit (32 byte) native word of the EVM
struct IdStruct {
uint128 id; // zero means invalid.
uint32 value;
uint32 field2;
uint64 padding;
}
uint128 [] itemIds;
mapping (uint128 => IdStruct) items
As you can see I can have infinite array of items. I can look up any one of them up in O(1) time. I can iterate over all the items. Deletion and insertion are O(1) or O(n) depending if you care about holes in your array or not, and how you track them. There are more complex data structures out there that have O(1) insertions and deletions as well, here. Also google for Ethereum Alarm Clock.
So I am wondering, say I need a smart contract which has a data structure which has no fixed limits? Is this even possible?
It depends what you want to do. If you want to reduce the struct (say take the sum of all the elements value fields), you will be limited by the amount of gas this takes. (I've gotten this down to about 3k gas per element).
If you just need to look up an element, you can potentially have an infinite number of elements. Someone has to pay the gas cost of insertion.
How you structure a lookup system for a large set depends on who pays gas cost for which operation, whether you need to do reduction, filtering, and so on. Like any application, the data structure(s) you need depends on what you are doing. The nuance here is you measure the cost in gas, not in CPU cycles, cache misses, or storage like you would on a modern CPU system. You are currently limited to 4.7M gas per block, and you probably shouldn't use all of that.
It's probably possible, as you hint at above, to spread out a large data set operation over multiple blocks. Haven't tried it yet.
