[bunderbunder]

Hash tables are a big example. You can implement pure associative arrays, and they have some nice benefits, but the best functional implementations still have much poorer asymptotic performance than a basic hash table.

Pure data structures also tend to include a lot of extra pointers. That can create a lot of overhead. A pure list of 32-bit integers will need either 4 or 8 bytes of overhead (depending on whether you're running 32 or 64 bit) for every item stored. A resizable array just needs whatever empty space it preallocates, plus the occasional memcpy when it needs to add capacity. Also locality of reference and all that fun stuff.