Surprising, not surprisingly, choose any two, the go community doesn’t seem to have any intrusive linked list implementations. I’m currently working with data that has an html/dom like structure, i don’t want to expose all of the existing code to a new container structure, and it would be nice for elements to have direct access to their siblings – all in all, a classic use case for intrusive lists.

After searching around a bit, the few i could find were incomplete or experimental attempts. This example, by Lex Sheehan, is nice; but, it’s a tutorial, and it ends by introducing go’s standard library list implementation ( which is not intrusive. )

So, i decided to write one myself. Package inlist ( via GoDoc, and github ) is a port of the go standard library list package. It hews close enough to the original that i could use the same test code with some tweaks necessary to support the intrusive changes.

Here’s an example using inlist’s Hook to define an element ( user code can alternately implement the inlist.Intrusive interface for more control ):

func ExampleHook() {
  // Create a custom list element
  type MyElement struct {
    inlist.Hook     // anonymous support for the intrusive list
    MyData      int // some example data
  }

  // Create a new list
  l := inlist.New()
  l.PushBack(&MyElement{MyData: 17})
  l.PushFront(&MyElement{MyData: 20})

  // Traverse the list
  for e := l.Front(); e != nil; e = inlist.Next(e) {
    fmt.Println(e.(\*MyElement).MyData)
  }

  // Output:
    // 20
    // 17

Just to restate, inlist uses the same core algorithm as go’s list, substituting interfaces for direct pointer access. This means that, while each element still requires a pointer to its next and prev siblings: the element doesn’t have to store the list pointer if it’s available from some other source ( A singleton, a parent pointer in a tree of nodes, etc. )

Also, where each go list incurs a sentinel element consisting of 4 pointers, inlist’s is slightly smaller having only the 2 pointers ( next and prev ) it actually needs.

The one major algorithmic difference between the two implementations is inlist’s lack of PushFrontList() and PushBackList(). That’s because, unlike package list, package inlist cannot manufacture new elements whole cloth.

Instead, the best it can provide, are MoveFrontList() and MoveBackList() which fully transfer elements from one list to another. ( Truthfully, i think “move list” is safer than “push list”, but that’s a discussion for another time. )

Feedback? Let me know!