For integer keys the speed of indexing is O(N), so it looks like it is a list. But apparently (wqw's comment in Unable to properly loop through keys AND values in a VB6 For Each loop) access time for string keys is O(log(N))... Maybe it is a tree built on top of single-linked list (indexing the list elements)?
I tried hard to get the documentation about this, but all I can find is how to use the Collection, never what is its data model.
I doubt you'll find much of anything regarding the implementation details of VBA.Collection. (Official usage reference at https://docs.microsoft.com/en-us/office/vba/language/reference/user-interface-help/collection-object)
The general advice is to consider using the VBScript Dictionary object instead; certainly use that instead if you need access to the keys. According to this, Dictionary is also faster up to a point: https://fastexcel.wordpress.com/2012/07/10/comparing-two-lists-vba-udf-shootout-between-linear-search-binary-search-collection-and-dictionary/
Another alternative I've done myself was to make use of the .NET Hashtable (making reference to mscorlib.dll). I've not done any performance tests of that versus VBScript Dictionary, so I don't if it's worth the effort (but it was fun to implement). An example is at Cannot iterate Hashtable in VBA (Excel).
