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:

CREATE TABLE ordered_items (
    item_id INT UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
    item_name VARCHAR(100) NOT NULL,
    previous_item_id INT UNSIGNED NULL,
    FOREIGN KEY (previous_item_id) REFERENCES ordered_items(item_id)
);

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.

<?php

function addItem($name, $previousId)
{
    $sql = "INSERT INTO ordered_items (item_name, previous_item_id)
            VALUES (?, ?)";

    // The query function is assumed to prepare and execute a SQL statement with
    // an array of bound parameters, and return the insert ID or selected row.
    $itemId = query($sql, [$name, $previousId]);
    setInsertedItemReference($itemId, $previousId);
}

/**
 * If another item in the list has the same previous ID as the
 * inserted item, change it to reference the inserted item.
 */
function setInsertedItemReference($itemId, $itemPreviousId)
{
    $params = [$itemId, $itemId];

    if ($itemPreviousId === null) {
        $condition = 'IS NULL';
    } else {
        $condition = '= ?';
        $params[] = $itemPreviousId;
    }

    $sql = "UPDATE ordered_items
            SET previous_item_id = ?
            WHERE item_id <> ?
            AND previous_item_id {$condition}";

    query($sql, $params);
}

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.

<?php

function deleteItem($itemId)
{
    $previousId = selectItem($itemId)['previous_item_id'];
    closeMovedItemGap($itemId, $previousId);
    query("DELETE FROM ordered_items WHERE item_id = ?", [$itemId]);
}

function selectItem($itemId)
{
    $sql = "SELECT * FROM ordered_items WHERE item_id = ?";
    return query($sql, [$itemId]);
}

/**
 * If any other item has a previous ID referencing the moved item,
 * change it to point to the moved item's original previous ID.
 */
function closeMovedItemGap($itemId, $itemPreviousId)
{
    $sql = "UPDATE ordered_items
            SET previous_item_id = ?
            WHERE previous_item_id = ?";

    query($sql, [$itemPreviousId, $itemId]);
}

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

<?php

function updateItem($id, $name, $previousId)
{
    if ($id === $previousId) {
        throw new Exception('Items cannot reference themselves');
    }

    $originalItem = selectItem($id);

    if ($previousId !== $originalItem['previous_item_id']) {
        // the item was reordered
        closeMovedItemGap($id, $originalItem['previous_item_id']);
        setInsertedItemReference($id, $previousId);
    }

    $sql = "UPDATE ordered_items
            SET item_name = ?,
            previous_item_id = ?
            WHERE item_id = ?";

    query($sql, [$name, $previousId, $id]);
}

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.