list 为什么列表在 Go 中很少使用？

Why are lists used infrequently in Go?

提问by Vector

I'm new to Go, and quite excited about it. But, in all the languages I've worked with extensively: Delphi, C#, C++, Python - Lists are very important because they can be dynamically resized, as opposed to arrays.

我是 Go 的新手，对此感到非常兴奋。但是，在我广泛使用的所有语言中：Delphi、C#、C++、Python - 列表非常重要，因为它们可以动态调整大小，而不是数组。

In Golang, there is indeed a list.Liststruct, but I see very little documentation about it - whether in Go By Exampleor the three Go books that I have - Summerfield, Chisnal and Balbaert - they all spend a lot of time on arrays and slices and then skip to maps. In souce code examples I also find little or no use of list.List.

在 Golang 中确实有一个list.List结构体，但我很少看到关于它的文档——无论是在Go By Example还是我拥有的三本 Go 书籍——Summerfield、Chisnal 和 Balbaert——他们都花了很多时间在数组和切片上然后跳到地图。在源代码示例中，我也发现很少或根本没有使用list.List.

It also appears that, unlike Python, Rangeis not supported for List - big drawback IMO. Am I missing something?

似乎与 Python 不同的Range是，List 不支持 - IMO 的一大缺点。我错过了什么吗？

Slices are certainly nice, but they still need to be based on an array with a hard coded size. That's where List comes in. Is there a way to create an array /slice in Go without a hard coded array size? Why is List ignored?

切片当然很好，但它们仍然需要基于具有硬编码大小的数组。这就是 List 的用武之地。有没有办法在没有硬编码数组大小的情况下在 Go 中创建数组/切片？为什么列表会被忽略？

采纳答案by Vector

I asked this question a few months ago, when I first started investigating Go. Since then, every day I have been reading about Go, and coding in Go.

几个月前，当我第一次开始研究 Go 时，我问过这个问题。从那时起，我每天都在阅读有关 Go 的文章，并使用 Go 进行编码。

Because I did not receive a clear-cut answer to this question (although I had accepted one answer) I'm now going to answer it myself, based on what I have learned, since I asked it:

因为我没有收到这个问题的明确答案（虽然我已经接受了一个答案）我现在要根据我所学到的来自己回答，因为我问过它：

Is there a way to create an array /slice in Go without a hard coded array size?

有没有办法在没有硬编码数组大小的情况下在 Go 中创建数组/切片？

Yes. Slices do not require a hard coded array to slicefrom:

是的。切片不需要硬编码数组即可slice：

var sl []int = make([]int,len,cap)

This code allocates slice sl, of size lenwith a capacity of cap- lenand capare variables that can be assigned at runtime.

此代码分配容量为-sl大小的slice ，并且是可以在运行时分配的变量。lencaplencap

Why is list.Listignored?

为什么被list.List忽略？

It appears the main reasons list.Listseem to get little attention in Go are:

list.List在 Go 中似乎很少受到关注的主要原因是：

• As has been explained in @Nick Craig-Wood's answer, there is virtually nothing that can be done with lists that cannot be done with slices, often more efficiently and with a cleaner, more elegant syntax. For example the range construct:

  for i:=range sl {
    sl[i]=i
  }
  

  cannot be used with list - a C style for loop is required. And in many cases, C++ collection style syntax must be used with lists: push_backetc.

• Perhaps more importantly, list.Listis not strongly typed - it is very similar to Python's lists and dictionaries, which allow for mixing various types together in the collection. This seems to run contrary to the Go approach to things. Go is a very strongly typed language - for example, implicit type conversions never allowed in Go, even an upCast from intto int64must be explicit. But all the methods for list.List take empty interfaces - anything goes.

  One of the reasons that I abandoned Python and moved to Go is because of this sort of weakness in Python's type system, although Python claims to be "strongly typed" (IMO it isn't). Go'slist.Listseems to be a sort of "mongrel", born of C++'s vector<T>and Python's List(), and is perhaps a bit out of place in Go itself.

• 正如@Nick Craig-Wood 的回答中所解释的那样，使用切片无法完成的列表几乎没有任何事情可以完成，通常更有效，并且语法更简洁，更优雅。例如范围构造：

  for i:=range sl {
    sl[i]=i
  }
  

  不能与列表一起使用 - 需要 C 风格的 for 循环。并且在许多情况下，C++ 集合样式语法必须与列表一起使用： push_back等。

• 也许更重要的是，list.List它不是强类型的——它与 Python 的列表和字典非常相似，允许在集合中混合各种类型。这似乎与 Go 处理事物的方法背道而驰。Go 是一种非常强类型的语言——例如，Go 中从不允许隐式类型转换，即使是从intto的 upCast也int64必须是显式的。但是 list.List 的所有方法都采用空接口 - 任何事情都可以。

  我放弃 Python 而转向 Go 的原因之一是因为 Python 类型系统的这种弱点，尽​​管 Python 声称是“强类型”（IMO 并非如此）。Golist.List似乎是一种“杂种”，诞生于 C++vector<T>和 Python 的 List()，并且在 Go 本身中可能有点格格不入。

It would not surprise me if at some point in the not too distant future, we find list.List deprecated in Go, although perhaps it will remain, to accommodate those raresituations where, even using good design practices, a problem can best be solved with a collection that holds various types. Or perhaps it's there to provide a "bridge" for C family developers to get comfortable with Go before they learn the nuances of slices, which are unique to Go, AFAIK. (In some respects slices seem similar to stream classes in C++ or Delphi, but not entirely.)

如果在不久的将来的某个时候，我们发现 list.List 在 Go 中已被弃用，我不会感到惊讶，尽管它可能会保留，以适应那些即使使用良好的设计实践也能最好地解决问题的罕见情况拥有一个包含各种类型的集合。或者它可能为 C 系列开发人员提供一个“桥梁”，让他们在学习切片的细微差别之前熟悉 Go，AFAIK。（在某些方面，切片似乎类似于 C++ 或 Delphi 中的流类，但并非完全如此。）

Although coming from a Delphi/C++/Python background, in my initial exposure to Go I found list.Listto be more familiar than Go's slices, as I have become more comfortable with Go, I have gone back and changed all my lists to slices. I haven't found anything yet that sliceand/or mapdo not allow me to do, such that I need to use list.List.

虽然来自 Delphi/C++/Python 背景，但在我最初接触 Go 时，我发现list.List比 Go 的 slice 更熟悉，因为我对 Go 越来越熟悉，我回去将所有列表更改为 slice。我还没有发现任何东西slice和/或map不允许我这样做，所以我需要使用list.List.

回答by Nick Craig-Wood

Just about always when you are thinking of a list - use a slice instead in Go. Slices are dynamically re-sized. Underlying them is a contiguous slice of memory which can change size.

当您考虑列表时，几乎总是 - 在 Go 中使用切片代替。切片动态调整大小。它们的底层是一个可以改变大小的连续内存片。

They are very flexible as you'll see if you read the SliceTricks wiki page.

它们非常灵活，如果您阅读SliceTricks wiki 页面，您就会看到。

Here is an excerpt :-

这是摘录：-

Copy

b = make([]T, len(a))
copy(b, a) // or b = append([]T(nil), a...)

Cut

a = append(a[:i], a[j:]...)

Delete

a = append(a[:i], a[i+1:]...) // or a = a[:i+copy(a[i:], a[i+1:])]

Delete without preserving order

a[i], a = a[len(a)-1], a[:len(a)-1]

Pop

x, a = a[len(a)-1], a[:len(a)-1]

Push

a = append(a, x)

复制

b = make([]T, len(a))
copy(b, a) // or b = append([]T(nil), a...)

切

a = append(a[:i], a[j:]...)

删除

a = append(a[:i], a[i+1:]...) // or a = a[:i+copy(a[i:], a[i+1:])]

删除而不保留​​顺序

a[i], a = a[len(a)-1], a[:len(a)-1]

流行音乐

x, a = a[len(a)-1], a[:len(a)-1]

推

a = append(a, x)

Update: Here is a link to a blog post all about slicesfrom the go team itself, which does a good job of explaining the relationship between slices and arrays and slice internals.

更新：这是一篇关于go 团队本身关于切片的博客文章的链接，它很好地解释了切片和数组之间的关系以及切片内部结构。

回答by kostix

I think that's because there's not much to say about them as the container/listpackage is rather self-explanatory onceyou absorbed what is the chief Go idiom for working with generic data.

我认为这是因为关于它们没有太多可说的，因为一旦你吸收了处理通用数据的主要 Go 习语，这个container/list包就相当不言自明了。

In Delphi (without generics) or in C you would store pointers or TObjects in the list, and then cast them back to their real types when obtaining from the list. In C++ STL lists are templates and hence parameterized by type, and in C# (these days) lists are generic.

在 Delphi（没有泛型）或 C 中，您可以将指针或TObjects存储在列表中，然后在从列表中获取时将它们转换回它们的实际类型。在 C++ 中，STL 列表是模板，因此按类型参数化，而在 C# 中（现在）列表是通用的。

In Go, container/liststores values of type interface{}which is a special type capable to represent values of any other (real) type—by storing a pair of pointers: one to the type info of the contained value, and a pointer to the value (or the value directly, if it's size is no greater than the size of a pointer). So when you want to add an element to the list, you just do that as function parameters of type interface{}accept values coo any type. But when you extract values from the list, and what to work with their real types you have to either type-asertthem or do a type switchon them—both approaches are just different ways to do essentially the same thing.

在 Go 中，container/list存储类型的值interface{}是一种能够表示任何其他（实数）类型值的特殊类型——通过存储一对指针：一个指向所包含值的类型信息，一个指向该值（或value 直接，如果它的大小不大于指针的大小）。因此，当您想向列表中添加一个元素时，您只需将其作为interface{}接受值 coo 任何类型的函数参数即可。但是，当您从列表中提取值，以及如何处理它们的真实类型时，您必须对它们进行类型置位或对它们进行类型切换——这两种方法只是做本质上相同的事情的不同方法。

Here is an example taken from here:

这是取自此处的示例：

package main

import ("fmt" ; "container/list")

func main() {
    var x list.List
    x.PushBack(1)
    x.PushBack(2)
    x.PushBack(3)

    for e := x.Front(); e != nil; e=e.Next() {
        fmt.Println(e.Value.(int))
    }
}

Here we obtain an element's value using e.Value()and then type-assert it as inta type of the original inserted value.

在这里，我们使用获取元素的值e.Value()，然后将其类型断言为int原始插入值的类型。

You can read up on type assertions and type switches in "Effective Go" or any other introduction book. The container/listpackage's documentation summaries all the methods lists support.

您可以在“Effective Go”或任何其他介绍书籍中阅读类型断言和类型切换。该container/list包的文档总结了所有支持的方法列表。

回答by James Henstridge

Note that Go slices can be expanded via the append()builtin function. While this will sometimes require making a copy of the backing array, it won't happen every time, since Go will over-size the new array giving it a larger capacity than the reported length. This means that a subsequent append operation can be completed without another data copy.

请注意，可以通过append()内置函数扩展 Go 切片。虽然这有时需要复制后备数组，但不会每次都发生，因为 Go 会使新数组过大，使其容量大于报告的长度。这意味着可以在没有另一个数据副本的情况下完成后续的追加操作。

While you do end up with more data copies than with equivalent code implemented with linked lists, you remove the need to allocate elements in the list individually and the need to update the Nextpointers. For many uses the array based implementation provides better or good enough performance, so that is what is emphasised in the language. Interestingly, Python's standard listtype is also array backed and has similar performance characteristics when appending values.

虽然与使用链表实现的等效代码相比，最终得到的数据副本更多，但您无需单独分配列表中的元素，也无需更新Next指针。对于许多用途，基于数组的实现提供了更好或足够好的性能，因此这就是语言中所强调的。有趣的是，Python 的标准list类型也是数组支持的，并且在附加值时具有类似的性能特征。

That said, there are cases where linked lists are a better choice (e.g. when you need to insert or remove elements from the start/middle of a long list), and that is why a standard library implementation is provided. I guess they didn't add any special language features to work with them because these cases are less common than those where slices are used.

也就是说，在某些情况下，链接列表是更好的选择（例如，当您需要从长列表的开头/中间插入或删除元素时），这就是提供标准库实现的原因。我猜他们没有添加任何特殊的语言功能来使用它们，因为这些情况比使用切片的情况少见。

回答by Manohar

Unless the slice is updated way too often (delete, add elements at random locations) the memory contiguity of slices will offer excellent cache hit ratio compared to linked lists.

除非切片更新太频繁（删除，在随机位置添加元素），与链表相比，切片的内存连续性将提供出色的缓存命中率。

Scott Meyer's talk on the importance of cache.. https://www.youtube.com/watch?v=WDIkqP4JbkE

Scott Meyer 关于缓存重要性的演讲.. https://www.youtube.com/watch?v=WDIkqP4JbkE

回答by woodings

list.Listis implemented as a doubly linked list. Array-based lists (vectors in C++, or slices in golang) are better choice than linked lists in most conditions if you don't frequently insert into the middle of the list. The amortized time complexity for append is O(1) for both array list and linked list even though array list has to extend the capacity and copy over existing values. Array lists have faster random access, smaller memory footprint, and more importantly friendly to garbage collector because of no pointers inside the data structure.

list.List被实现为一个双向链表。如果您不经常插入列表的中间，那么在大多数情况下，基于数组的列表（C++ 中的向量，或 golang 中的切片）比链表更好。尽管数组列表必须扩展容量并复制现有值，但 append 的摊销时间复杂度对于数组列表和链表都是 O(1)。数组列表具有更快的随机访问，更小的内存占用，更重要的是由于数据结构内部没有指针，因此对垃圾收集器更友好。

回答by Manohar Reddy Poreddy

From: https://groups.google.com/forum/#!msg/golang-nuts/mPKCoYNwsoU/tLefhE7tQjMJ

来自：https: //groups.google.com/forum/#!msg/golang-nuts/mPKCoYNwsoU/tLefhE7tQjMJ

It depends a lot on the number of elements in your lists,
 whether a true list or a slice will be more efficient
 when you need to do many deletions in the 'middle' of the list.

#1
The more elements, the less attractive a slice becomes. 

#2
When the ordering of the elements isn't important,
 it is most efficient to use a slice and
 deleting an element by replacing it by the last element in the slice and
 reslicing the slice to shrink the len by 1
 (as explained in the SliceTricks wiki)

So
use slice
1. If order of elements in list is Not important, and you need to delete, just
use List swap the element to delete with last element, & re-slice to (length-1)
2. when elements are more (whatever more means)

所以
使用切片
1。如果列表中元素的顺序不重要，并且您需要删除，只需
使用List交换要删除的元素与最后一个元素，&重新切片为（长度-1）
2.当元素更多时（还有什么意思）

---

---

There are ways to mitigate the deletion problem --
e.g. the swap trick you mentioned or
just marking the elements as logically deleted.
But it's impossible to mitigate the problem of slowness of walking linked lists.

So
use slice
1. If you need speed in traversal

所以
使用切片
1。如果你需要速度遍历