The data structure for the "order" property of an object in a list

Question

I have a list of ordered objects stored in the database and accessed through an ORM (specifically, Django's ORM). The list is sorted arbitrarily by the user and I need some way to keep track of it. To that end, each object has an "order" property that specifies its order in relation to the other objects.

Any data structure I use to sort on this order field will have to be recreated upon the request, so creation has to be cheap. I will often use comparisons between multiple objects. And insertions can't require me to update every single row in the database.

What data structure should I use?

Answer 1

Linked list (doubly)?

Answer 2

Heap

As implemented by std::set (c++) with comparison on the value (depends on the value stored), e.g. integers by value, strings by string ordering and so on. Good for ordering and access but not sure when you need to do reordering, is that during insertion, constantly and so on.

You're not specifying what other constraints do you have. If number of elements is know and it is reasonable or possible to keep fixed array in memory then each position would be specified by index. Assumes fixed number of elements.

You did not specify if you want operations you want to perform often. If you load up values once then access them without modification you can use one algorithm for creation then either build index or transform storage to be able to use fast access ...

Answer 3

I don't think you cannot get constant time for insertions (but maybe amortized constant time?).

I would use a binary tree, then the bit sequence describing the path can be used as your "order property".