A simple golang implementation of a doubly-linked list that supports generics.

list.go

// A generic doubly-linked list

package list

// the zero value is ready to use.
type List[T any] struct {
	root Element[T]
	Len  int
}

type Element[T any] struct {
	prev  *Element[T]
	next  *Element[T]
	list  *List[T]
	Value T
}

func (e *Element[T]) Next() *Element[T] {
	n := e.next
	if e.list == nil || n == &e.list.root {
		return nil
	}
	return n
}

func (e *Element[T]) Prev() *Element[T] {
	p := e.prev
	if e.list == nil || p == &e.list.root {
		return nil
	}
	return p
}

func (l *List[T]) First() *Element[T] {
	if l.Len == 0 {
		return nil
	}
	return l.root.next
}

func (l *List[T]) Last() *Element[T] {
	if l.Len == 0 {
		return nil
	}
	return l.root.prev
}

func (l *List[T]) PushFront(v T) *Element[T] {
	if l.root.next == nil {
		l.init()
	}
	return l.insertValueAfter(v, &l.root)
}

func (l *List[T]) PushBack(v T) *Element[T] {
	if l.root.next == nil {
		l.init()
	}
	return l.insertValueAfter(v, l.root.prev)
}

func (l *List[T]) Remove(e *Element[T]) T {
	if e.list == l {
		l.remove(e)
	}
	return e.Value
}

// Constructs a new List[T] from the given slice, returns the List[T].
func FromSlice[T any](slice []T) List[T] {
	var list List[T]
	for _, e := range slice {
		list.PushFront(e)
	}
	return list
}

func (l *List[T]) init() {
	l.root = *new(Element[T])
	l.root.next = &l.root
	l.root.prev = &l.root
}

func (l *List[T]) insertAfter(e *Element[T], at *Element[T]) *Element[T] {
	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
	e.list = l
	l.Len++
	return e
}

func (l *List[T]) insertValueAfter(v T, at *Element[T]) *Element[T] {
	e := Element[T]{Value: v}
	return l.insertAfter(&e, at)
}

func (l *List[T]) remove(e *Element[T]) {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil
	e.prev = nil
	e.list = nil
	l.Len--
}

list_test.go

package list

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

func TestList(t *testing.T) {
	l := List[string]{}

	assert.Zero(t, l.root)
	assert.Zero(t, l.Len)
	assert.Zero(t, l.First())
	assert.Zero(t, l.Last())

	l.PushFront("foo")
	assert.Equal(t, 1, l.Len)
	assert.Equal(t, "foo", l.First().Value)

	l.PushFront("bar")
	assert.Equal(t, 2, l.Len)
	assert.Equal(t, "bar", l.First().Value)
	assert.Equal(t, "foo", l.Last().Value)

	l.PushFront("baz")
	assert.Equal(t, 3, l.Len)
	assert.Equal(t, "baz", l.First().Value)
	assert.Equal(t, "foo", l.Last().Value)

	// list is now (baz, bar, foo)
	assert.Equal(t, "bar", l.First().Next().Value)
	assert.Nil(t, l.First().Prev())
	assert.Equal(t, "foo", l.First().Next().Next().Value)
	assert.Equal(t, "baz", l.First().Next().Prev().Value)

	v := l.Remove(l.First())
	assert.Equal(t, 2, l.Len)
	assert.Equal(t, "baz", v)
	assert.Equal(t, "bar", l.First().Value)
	assert.Equal(t, "foo", l.Last().Value)

	v = l.Remove(l.First())
	assert.Equal(t, 1, l.Len)
	assert.Equal(t, "bar", v)
	assert.Equal(t, "foo", l.First().Value)
	assert.Equal(t, "foo", l.Last().Value)

	v = l.Remove(l.First())
	assert.Equal(t, 0, l.Len)
	assert.Equal(t, "foo", v)
	assert.Nil(t, l.First())
	assert.Nil(t, l.Last())
}