Django: Ordering by Linked List for Model Objects

Linked list is a data structure where each object has points to next. In django, linked list can provide an interesting solution when it comes to custom ordering/grouping issues.

Lets think of an example like this= you are making a blog site, and you have made a Post Model like this:

class Post(models.Model):
    title=models.CharField(max_length=255)
    body=models.TextField()
    author=models.ForeignKey(User, on_delete=models.DO_NOTHING)

Now you want to make a group of posts as series. How can you do that? Here are possible solutions:

Without linked list

One way of approaching this problem is to make a new model named Series and have ForeignKey relation from Post to Series. Also there should be a ordering field in Tutorials as well, so that it does not create a series with multiple posts with same order. For example like this:

class Series(models.Model):
    title=models.CharField(max_length=255)

class Post(models.Model):
    series=models.ForeignKey(Series, null=True, default=None)
    order = models.IntegerField()

    class Meta:
        unique_togather=('series', 'order',)

Pros and cons without linked list

There are few pros and cons of this approach. Pros are: the model structure is very flexible and easy to make a query:

series = Series.objects.first()
posts = series.post_set.all().order_by('order')

But, a major cons is that, you need to create at-least 1 extra table and 1 extra field to maintain it.

With linked list

So, when we are going to use linked list, we need to put a reference to next object in model:

class Post(models.Model):
    # rest of the fields
    previous=models.OneToOneField('self', null=True, blank=True, related_name="next")

Funny thing is that, as linked list we were suppose to mark the next, instead we are creating an entry named previous in the model. But don’t worry, it will serve as reference to next object via related objects. Here are some explanations:

When you are giving a related_name to a OneToOne(or ForeignKey Field), it will give the related object, for example in the model the previous post, a reference to current post. So when we type previous_post.next, it will return current post.

>> p1 = Post.objects.create(...)
>> p2 = Post.objects.create(...)
>> p2.previous=p1
>> p2.save()
>> print(p1.next)
   <Post: Post object (2)>

Now, if we want to create a new series, all we have to do is link a post to its previous one, thats it.

But in this approach, querying is bit complicated. You can get all the posts in a series like this:

posts = Post.objects.filter(previous__isnull=True)
# root posts will not have any previous post
series = list()
for post in posts:
    print(post)
    series_posts=list()
    series_posts.append(post)
    while(post.next):
        print(post.next)
        post=post.next
        series_posts.append(post)
    series.append(series_posts)

print(series)

Now, in template you can access previous and next posts of a given post like this:

{{ post.title }} {{ post.body }} {% if post.previous %}
<a href="{% url 'post-detail' post.previous.pk %}">{{ post.previous.title }}</a>
{% endif %} {% if post.next %}
<a href="{% url 'post-detail' post.next.pk %}">{{ post.next.title }}</a>
{% endif %}

Pros and cons with linked list

The pros of this approach is that, you don’t have to create extra table for this. But a major downside is that, whenever you want to add a new post in middle of the series, you need to write a lot of lines. For example, you might need to change like this:

p1=Post.objects.first()
p2 = p1.next

p3=Post.objects.create(...)
p2.previous=p3
p2.save()
p3.previous=p1
p3.save()

But hopefully the order in Objects won’t change too frequently. So its not a major problem.

Conclusion

Fundamental data structure like linked list is really helpful in maintaining order in objects. I hope this post has been able to put some light on this topic. Thanks for reading.

Last updated: Apr 05, 2024