在 golang 中实现通用链表，它不允许同一链表中的不同类型

Question

我想制作一个链表，它可以保存任何类型的值，但链表必须只保存任何一种类型的值。一般来说，当我使用接口来实现这一点时——任何实现节点接口的类型都可以添加到链表中。我为此编写了一个实现，每当将新键添加到链表时，都会根据头部键的类型检查键的类型。我想了解这是实现它的正确方法还是有更好的方法。该代码运行良好 - 但我想了解是否有更好或不同的方法来执行此操作。另外 - 当前使用反射包检查类型的性能影响是什么。有没有不同的方法来实现同样的事情。*main.Student 类型不受支持的类型Unsupported type for the type *main.Student################################################################################Printing the linked list *main.ComplexNode &{9 90}  9 + i90 *main.ComplexNode &{8 80}  8 + i80 *main.ComplexNode &{7 70}  7 + i70 *main.ComplexNode &{6 60}  6 + i60 *main.ComplexNode &{5 50}  5 + i50 *main.ComplexNode &{4 40}  4 + i40 *main.ComplexNode &{3 30}  3 + i30 *main.ComplexNode &{2 20}  2 + i20 *main.ComplexNode &{1 10}  1 + i10################################################################################

Answer 1

好消息，从 Go 1.18 开始，Go 现在支持泛型。

按照问题中的示例，这里是一个使用泛型的简化 LinkedList。您可以在此处的操场上修改它。

package main

import "fmt"

type MyNode[T any] struct {

    next  *MyNode[T]

    value T

}

type MyLinkedList[T any] struct {

    head *MyNode[T]

    tail *MyNode[T]

}

func (list *MyLinkedList[T]) Add(t T) *MyLinkedList[T] {

    // create node

    node := &MyNode[T]{nil, t}

    // if first node in list

    if list.head == nil {

        list.head = node

        list.tail = node

    } else {

        list.tail.next = node

        list.tail = list.tail.next

    }

    return list

}

func (list *MyLinkedList[T]) AddBeforeHead(t T) *MyLinkedList[T] {

    node := &MyNode[T]{nil, t}

    if list.head != nil {

        node.next = list.head

        list.head = node

    } else {

        // make head

        list.head = node

        list.tail = node

    }

    return list

}

// display the list

func DisplayList[T any](list *MyLinkedList[T]) string {

    var out string = ""

    iter := list.head

    for iter != nil {

        out += fmt.Sprintf("%v -> ", iter.value)

        iter = iter.next

    }

    return out

}

func (list *MyLinkedList[T]) Display() string {

    return DisplayList(list)

}

// for printing node value

// you could also implement Stringer

// but this is besides the point, you can ignore

func (node *MyNode[T]) String() string {

    return fmt.Sprintf("<MyNode: %v>", node.value)

}

// helper func: create list from array

func CreateLinkedList[T any](arr []T) *MyLinkedList[T] {

    list := &MyLinkedList[T]{}

    for _, v := range arr {

        list.Add(v)

    }

    return list

}

func main() {

    // create a list from array of integers

    intArr := []int{10, 20, 30, 40, 50, 60}

    list1 := CreateLinkedList(intArr)

    // create a list from array of strings

    strArr := []string{"foo", "bar", "baz", "faz"}

    list2 := CreateLinkedList(strArr)

    // test inserting at the beginning

    list2.AddBeforeHead("hello")

    fmt.Println(list1.Display())

    fmt.Println(list2.Display())

}

Answer 2

您可以通过使用接口和运行时检查（正如您所发现的那样）或使用代码生成来做到这一点。这些是您在 Go 中用于泛型编程的当前选项。Go 团队正在努力为语言添加泛型——这是一项正在进行的工作，每个人都可以自由参与讨论。一旦泛型存在，它们将提供您在这里寻求的解决方案。

至于接口与代码生成，有你提到的性能影响。代码生成将生成更紧凑的代码，不需要对大多数操作进行运行时检查；另一方面，它为项目的构建过程增加了一些复杂性。这些是在运行时解决某些事情与在编译时预先计算事情的通常权衡。