circular doubly linked list

linked_list.go

import (
	"fmt"

	"golang.org/x/exp/constraints"
)

type LinkedList[T constraints.Ordered] struct {
	head, tail *Node[T]
}

type Node[T constraints.Ordered] struct {
	next *Node[T]
	prev *Node[T]
	val  T
}

func (ll *LinkedList[T]) Insert(val T) {
	node := &Node[T]{val: val}

	if ll.head == nil {
		ll.head = node
		ll.tail = node
	}

	node.next = ll.head
	node.prev = ll.tail
	ll.tail.next = node
	ll.tail = node
}

func (ll *LinkedList[T]) Delete(val T) error {
	node, err := ll.Find(val)
	if err != nil {
		return err
	}
	if node == ll.head {
		if node == ll.tail {
			node = nil
			return nil
		}
		ll.tail.next = node.next
		ll.head = node.next
		node = nil
		return nil
	}
	node.next.prev = node.prev
	node.prev.next = node.next
	node = nil
	return nil
}

func (ll *LinkedList[T]) Find(val T) (*Node[T], error) {
	notFoundError := fmt.Errorf("node with value %v does not exist in the list", val)

	if ll.head == nil {
		return nil, notFoundError
	}

	for curr := ll.head; curr != ll.tail; curr = curr.next {
		if curr.val == val {
			return curr, nil
		}
	}

	if ll.tail.val == val {
		return ll.tail, nil
	}

	return nil, notFoundError
}

func (ll *LinkedList[T]) Update(val, newVal T) error {
	node, err := ll.Find(val)
	if err != nil {
		return err
	}

	node.val = newVal
	return nil
}

func (ll *LinkedList[T]) Sort() {
	ll.tail.next = nil
	ll.head = ll.head.sort()
	for tmp := ll.head; tmp.next != nil; tmp = tmp.next {
		tmp.next.prev = tmp
	}
	ll.tail.next = ll.head
}

func (node *Node[T]) sort() *Node[T] {
	if node == nil || node.next == nil {
		return node
	}

	tmp, slow, fast := node, node, node
	for fast != nil && fast.next != nil {
		tmp, slow, fast = slow, slow.next, fast.next.next
	}
	tmp.next = nil
	rest := slow

	node = node.sort()
	rest = rest.sort()

	return node.merge(rest)
}

func (node *Node[T]) merge(other *Node[T]) *Node[T] {
	head := &Node[T]{}
	curr := head

	for node != nil && other != nil {
		if node.val < other.val {
			curr.next = node
			node = node.next
		} else {
			curr.next = other
			other = other.next
		}
		curr = curr.next
	}

	if node != nil {
		curr.next = node
	} else {
		curr.next = other
	}

	return head.next
}