go自带的链表是没有排序功能的，而且也不支持泛型。不支持泛型还好说，使用 interface{} 就能解决。但是很多时候还是有对 list
排序的需求。
之前在公司内部，我写过一个 list 的排序，因为list内部的很多数据都是 private 的，所以没法使用归并排序，只能使用类插入排序。
在数据量不大的情况下，这种排序是可以接受的。但是如果数据量很大，这种排序就会很慢，所以这次我使用归并排序来实现排序，并且使用泛型来实现。
链表的归并排序，之前写过一次，这次就不再赘述了归并排序
关于 go 的泛型，之前也写过一篇文章go泛型
这次写的 支持 泛型 和 排序 的 GitHub 地址：listplus
这次简单讲解一下 go 自带的 list 的一些源码。
list源码
list 源码还是很简单的，就是一个双向链表，就挑几个函数学一下吧
element
1type Element struct {
2 next, prev *Element
3 list *List
4 Value any
5}
为什么要写 Element 这个结构体呢，是因为这里面存了 list 的指针。这个指针主要用来判断要操作的 element 是否属于这个
list。
一般自己在写链表的时候,很少这样写。多了这个指针，可以避免很多错误。比如把 A 链表中的元素插入到 B 链表中，这样就会出现问题。
剩下的 next 和 prev 就是链表的前后指针了，Value 就是存放数据的地方。 any 在 go 1.18 之后才有的，之前都是用
interface{} 来代替。
list
1type List struct {
2 root Element
3 len int
4}
这个结构就是链表的结构了，root 是一个 Element 结构体，这个 Element 结构体是一个哨兵，不存放数据，只是用来标记链表的头和尾。
root 的 next 指向链表的第一个元素，prev 指向链表的最后一个元素。
len 是链表的长度。
insert
1func (l *List) insert(e, at *Element) *Element {
2 e.prev = at
3 e.next = at.next
4 e.prev.next = e
5 e.next.prev = e
6 e.list = l
7 l.len++
8 return e
9}
PushBack 和 PushFront 都是调用这个函数来插入元素的。
这个函数也挺简单的，就是把 e 插入到 at 后面。逻辑也很简单，就是设置一下 e 和 at 的指针。然后把新插入的元素的 list 指针指向这个链表，最后链表的长度加一。
最后 return e，这个 e 就是新插入的元素。
在 PushBack 中，at 就是 root.prev，在 PushFront 中，at 就是 root。
remove
1func (l *List) remove(e *Element) {
2 e.prev.next = e.next
3 e.next.prev = e.prev
4 e.next = nil // avoid memory leaks
5 e.prev = nil // avoid memory leaks
6 e.list = nil
7 l.len--
8}
remove 函数就是调用这个函数来删除元素的。逻辑也很简单，就是把 e 从链表中删除。双向链表的删除，就是把 e 的前后指针指向对方，然后把 e 的 list 指针置空，最后链表的长度减一。
链表中删除一个元素，首先要找到这个元素，然后调用这个函数来删除。虽然链表删除的时间复杂度是 O(1)，但是找到这个元素的时间复杂度是 O(n)。
move
1func (l *List) move(e, at *Element) {
2 if e == at {
3 return
4 }
5 e.prev.next = e.next
6 e.next.prev = e.prev
7
8 e.prev = at
9 e.next = at.next
10 e.prev.next = e
11 e.next.prev = e
12}
move 函数就是调用这个函数来移动元素的。逻辑也很简单，就是把 e 移动到 at 后面。先把 e 从链表中 ‘删除’，然后把 e 插入到 at 后面。
所谓的删除就是 e 的前后指针指向对方。
go 的 list 中还有很多函数，这里就不一一列举了，但是对链表的核心操作就是这几个函数。
listplus
下面是我修改后的 list 的部分代码，整体逻辑没改，就是加了泛型支持，然后再加了排序功能。
就只列举一下 sort 函数吧
1func (l *List[T]) Sort(compare func(front, back T) bool) {
2 if l.len < 2 {//如果链表长度是0或者1，直接返回
3 return
4 }
5 head := l.Front()
6 tail := l.Back()
7 tail.next = nil
8 //取出链表的头和尾，然后调用归并排序
9 head, tail = l.mergeSort(head, compare)
10 //这里是把排序后的链表重新连接起来
11 l.root.next = head
12 l.root.prev = tail
13 head.prev = &l.root
14 tail.next = &l.root
15}
16
17func (l *List[T]) mergeSort(head *Element[T], compare func(front, back T) bool) (*Element[T], *Element[T]) {
18 if head == nil || head.next == nil {
19 return head, head
20 }
21 slow, fast := head, head
22 //使用快慢指针找到链表的中间节点
23 for fast.next != nil && fast.next.next != nil {
24 slow = slow.next
25 fast = fast.next.next
26 }
27 mid := slow.next
28 slow.next = nil//截断链表,因为下面的操作只会用 next指针,所以不用截断 prev指针
29
30 h1, t1 := l.mergeSort(head, compare)
31 h2, t2 := l.mergeSort(mid, compare)
32 return l.merge(h1, t1, h2, t2, compare)
33}
34
35func (l *List[T]) merge(h1, t1, h2, t2 *Element[T], compare func(front, back T) bool) (*Element[T], *Element[T]) {
36 //合并两个链表,然后返回合并后的头和尾
37 //和单向链表的合并不同的是,这里需要维护 prev指针
38 cur := &l.root
39 for h1 != nil && h2 != nil {
40 if compare(h1.Value, h2.Value) {
41 cur.next = h1
42 h1.prev = cur
43 h1 = h1.next
44 } else {
45 cur.next = h2
46 h2.prev = cur
47 h2 = h2.next
48 }
49 cur = cur.next
50 }
51 if h1 != nil {
52 cur.next = h1
53 h1.prev = cur
54 cur = t1
55 } else {
56 cur.next = h2
57 h2.prev = cur
58 cur = t2
59 }
60 return l.root.next, cur
61}
整体和以前写的链表排序差不多，不同的地方是这次是双向链表，所以需要维护 prev 指针。
一开始我是没有维护 prev 指针的，完全按照单向链表的思路来 merge，只是在 merge 完一个链表后，需要继续merge 另一个链表，重新组织链表的结构。
merge函数：
1func (l *List) merge(l1, l2 *Element, compare func(v1, v2 any) bool) *Element {
2 cur := &l.root
3 for l1 != nil && l2 != nil {
4 if compare(l1.Value, l2.Value) {
5 cur.next = l1
6 l1.prev = cur
7 l1 = l1.next
8 } else {
9 cur.next = l2
10 l2.prev = cur
11 l2 = l2.next
12 }
13 cur = cur.next
14 }
15 if l1 != nil {
16 cur.next = l1
17 l1.prev = cur
18 } else {
19 cur.next = l2
20 l2.prev = cur
21 }
22 for cur.next != nil {
23 cur.next.prev = cur
24 cur = cur.next
25 }
26 l.root.prev = cur
27 return l.root.next
28}
前半部分和这次的 merge 函数差不多，后面多了一个循环，是为了维护 prev 指针。
后来考虑到这部分是可以优化的，每次merge的时候，传递每个链表的 head 和 tail，这样就不用在merge完一个链表后，继续merge 另一个链表了。
这样就可以直接返回 head 和 tail，然后在 Sort 函数中重新连接链表。
整体还是比较简单的，就是不知的为什么 go 的 list 没有排序功能，这个功能还是很常用的。泛型都出了这么多年了，go 的 list 还是没有泛型。
性能
归并排序的时间复杂度是 O(nlogn)，比之前写的插入排序要快很多。但是 归并排序是基于递归的，需要额外的空间的，空间复杂度是 O(n)。
在数据量很大的时候，这个空间复杂度是很大的，所以在数据量很大的时候，还是要考虑一下。
原来想借鉴一下 go 的 sort 包，但是发现 go 的 sort 中的一些思想，比如 当数据量小于 12 的时候，使用插入排序，但是链表的长度统计不像切片那么方便，所以就没有实现。
还有就是在递归层数达到一定值的时候，使用别的排序算法，防止栈溢出。但是计算了一下
$ {log}_{2}1000000 = 19.931568569324174 $
链表的长度达到 1000000 的时候，递归层数也就 20 层，这个层数是可以接受的。
总结
这次实现了一个支持泛型和排序的链表，主要是为了学习 go 的泛型和链表的一些操作。链表的排序还是比较简单的，但是链表的排序还是比较少见的，一般都是使用切片来排序。 文中如果有错误的地方，还请指正。如果对 go 的泛型和链表有更好的想法，欢迎在 GitHub 上提出。