Why are lists used infrequently in Go?

Question

Is there a way to create an array/slice in Go without a hard-coded array size? Why is List ignored?

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.

In Golang, there is indeed a list.Liststruct, but I see very little documentation about it - whether in Go By Example or 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.

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

Slices are lovely, but they still need to be based on an array with a hard-coded size. That's where List comes in.

Answer 1

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.

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?

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

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

This code allocates slice sl, of size len with a capacity of cap - len and cap are variables that can be assigned at runtime.

Why is list.List ignored?

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

• 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_back etc.

• Perhaps more importantly, list.List is 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 int to int64 must 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.

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 rare situations 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.)

Although coming from a Delphi/C++/Python background, in my initial exposure to Go I found list.List to 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 slice and/or map do not allow me to do, such that I need to use list.List.

Answer 2

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.

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

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)

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

Answer 3

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

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.

In Go, container/list stores 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-asert them or do a type switch on them—both approaches are just different ways to do essentially the same thing.

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 int a type of the original inserted value.

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

Answer 4

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.

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 Next pointers. 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 list type is also array backed and has similar performance characteristics when appending values.

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.

Answer 5

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

Answer 6

From: 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)

---

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

Answer 7

list.List is 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.