Efficient synchronization of two instances of an ordered list What data structure or algorithm can be used to efficiently synchronize two nearly identical ordered lists? Two offline systems start with the same ordered list and each edit, insert, delete and move items in the list. Occasionally they will be online to synchronize the list. The algorithm should minimize the amount of changed items or "diffs" that need to be communicated.

For an unordered list we would simply use a modification timestamp and UUID for each item to detect edits respectively inserts/deletions. But what data structure can we use for an ordered list? Using an integer rank would require renumbering all successors after an insert, and thus result in many "diffs" when comparing items in both lists. Using a floating-point rank (having the average of the predecessor and successor ranks) would have accuracy problems after inserting many new items.

Using a doubly linked list (i.e. referencing the UUID of the predecessor and successor item) would result in two changed items and one new item for each insert, thus 3 "diffs" when comparing items in both lists.

Any suggestions, pointers to literature or Google search terms about this subject?
For synchronizing from a master list to a slave list, it looks like a fellow named Michael Heyeck has a good, O(n) solution to this problem. Check out that blog post for an explanation and some code. Perhaps this is a good starting point to generalize to a two-way sync.

Essentially, the solution tracks both the master and slave lists in a single pass, tracking indices into each. Two data structures are then managed: a list of insertions to be replayed on the slave list, and a list of deletions.

It looks straightforward and also has the benefit of a proof of minimalism, which Heyeck followed up with in a subsequent post. The code snippet in this post is more compact, as well:

def sync_ordered_list(a, b):
x = 0; y = 0; i = []; d = []
while (x &lt; len(a)) or (y &lt; len(b)):
    if y &gt;= len(b): d.append(x); x += 1
    elif x &gt;= len(a): i.append((y, b[y])); y += 1
    elif a[x] &lt; b[y]: d.append(x); x += 1
    elif a[x] &gt; b[y]: i.append((y, b[y])); y += 1
    else: x += 1; y += 1
return (i,d)


Again, credit to Michael Heyeck.