Interesting. Since the list is sorted, is the insertion still a linear search (O(N)) or now a binary search (O(log(N))? Or did I misunderstand something? Also, why is it not a hash table (almost O(1))?
Good point, I have the same doubt. Even if it is sorted, you still cannot do binary search on it unless using some skip list ideas. In fact, the code right now is doing linear search to find the ID given a name.
TBH, I don't fully understand how the ID linked list is utilized in Blender and why it needs to be sorted by names. It seems some other data structure could also work, unless I missed something.
TBH, I don't fully understand how the ID linked list is utilized in Blender and why it needs to be sorted by names. It seems some other data structure could also work, unless I missed something.