Ordered lists in django

Question

i have very simple problem. I need to create model, that represent element of
ordered list. This model can be implemented like this:

class Item(models.Model):
    data = models.TextField()
    order = models.IntegerField()

or like this:

class Item(models.Model):
    data = models.TextField()
    next = models.ForeignKey('self')

What way is preferred? What drawbacks have each solution?

Answer 1

Essentially, the second solution you propose is a linked list. Linked list
implemented at the database level are usually not a good idea. To retrieve a
list of n elements, you will need n database access (or use complicated
queries). Performance wise, retrieving a list in O(n) is awfully not
efficient.

In regular code, linked list are used to get better insert performance
compared to arrays (no need to move all elements around). In your database,
updating all elements is not that complicated in only 2 queries :

UPDATE item.order = item.order + 1 FROM item WHERE order > 3
INSERT INTO item (order, ...) VALUES (3, ...)

I remember seeing a reuseable app that implemented all that and a nice admin
interface, but I cant find it right now …

To summarize, definitly use solution #1 and stay away from solution #2 unless
you have a very very good reason not to !