Diff for successive sorted slice
Unnecessary optimization

You can safely remove this block of code without changing the behavior of the program:


if sd.l.Len() == 0 {
    sd.Append(updated)
    additions = make([]string, len(updated))
    copy(additions, updated)
    return additions, make([]string, 0)
}



Possible optimization

When you append to additions and deletions,
reallocation might occur.
If you don't mind spending a little extra space,
you could ensure that these slices have enough capacity to avoid reallocation.
You know that the maximum number of additions is the size of the input,
and the maximum number of deletions is the size of the current content:

additions = make([]string, 0, len(updated))
deletions = make([]string, 0, sd.l.Len())


Shorter format declaration

Instead of this:


func (sd *SliceDiff) SortedDiff(updated []string) (additions []string, deletions []string) {



You can use this shorter form:

func (sd *SliceDiff) SortedDiff(updated []string) (additions, deletions []string) {


Naming

Short names are very popular and encouraged in Go.
But l is really the worst of all single-letter variable names.
In addition to the usual badness of these variables,
depending on the viewer program,
l might be indistinguishable from 1 or I or |.
I suggest to never use l as a symbol name.

Alternative implementation

It seems to me that the use of container/List doesn't really buy you much.
It would be simpler and clearer to implement without it.
Consider this alternative implementation using only slices:

// Package slicediff is a utility to determine the additions and deletions that happened to a sorted slice after each update.
//
// All the slices are assumed to be sorted!
package slicediff

// SliceDiff stores the current state of the sorted slice
type SliceDiff struct {
    content []string
}

// New creates a new SliceDiff
func New() *SliceDiff {
    return &amp;SliceDiff{}
}

// Append appends a slice at the end of the SliceDiff
//
// sa is assumed to be sorted
func (sd *SliceDiff) Append(sa []string) {
    sd.content = append(sd.content, sa...)
}

func diff(s1, s2 []string) (added, deleted []string) {
    len1, len2 := len(s1), len(s2)

    added = make([]string, 0, len2)
    deleted = make([]string, 0, len1)

    for i1, i2 := 0, 0; i1 &lt; len1 || i2 &lt; len2; {
        if i1 == len1 {
            added = append(added, s2[i2:]...)
            return
        } else if i2 == len2 {
            deleted = append(deleted, s1[i1:]...)
            return
        }

        if s1[i1] &lt; s2[i2] {
            deleted = append(deleted, s1[i1])
            i1++
        } else if s1[i1] &gt; s2[i2] {
            added = append(added, s2[i2])
            i2++
        } else {
            i1++
            i2++
        }
    }
    return
}

// SortedDiff compares the updated slice with l and returns the additions and deletions performed
//
// updated is assumed to be sorted
func (sd *SliceDiff) SortedDiff(updated []string) (additions, deletions []string) {
    additions, deletions = diff(sd.content, updated)
    sd.content = updated
    return
}