/ PHP

Implementing a linked list in SQL

Recently I was challenged with enabling users to drag and drop items in a list to sort them in any order, and persisting that order in a SQL database. One way to handle this would be to add an index column to the table, which could be updated when an item is reordered. The downside of this approach is that whenever an item is added or moved, the index of every item beneath it must be updated. This could become a performance bottleneck in very large lists.

A more efficient approach is to use a linked list, where each item contains a reference to the previous item in the list, and the first item has a null reference (you could alternatively reference the next item, with the last item containing a null reference, but this requires the list to be sorted back-to-front, which I find less intuitive).

Let's start by creating a minimal table for items:

Next, we'll write two functions for adding items to the list: one to insert the item and the other to update any item referencing the same previous ID as the new item.

To remove an item from the list, we will again need two functions: one to delete the item row and another to update any item referencing the removed item.

Finally, we can add a function to update items (including their sort order):

As can be seen, whether an item is added, removed, or reordered, at most three rows will need to be updated. This keeps the performance nearly constant, regardless of the size of the list. With the basic database implementation complete, in my next post I'll share an approach to efficiently sort the linked list in client-side code.

Theodore Brown

Theodore Brown

Full-stack PHP and JavaScript developer interested in browsers, astronomy, and the future of programming.

Read More