没有内置的动态数组吗？

Question

I have just started to pick up go, and I was going over the data structures. I am used to having a dynamic array like list in python or std::vector in C++, but I don't see anything similar in go. The nice things about dynamic array is that it has O(1) time complexity to add a new element, and O(1) time complexity for indexing.

First I thought that slice is it, but then I realized that when I used append function, the whole slice is being copied, and then therefore it is an O(N) operations as opposed to O(1) in dynamic array.

Then I came across list but this is a doubly linked list, which means that indexing is O(N), as opposed to O(1).

Am I missing the data structure I am looking for?

Answer 1

First I thought that slice is it, but the[n] I realized that when I used append function, the whole slice is being copied, and then therefore it is an O(N) operations as opposed to O(1) in dynamic array.

This is not correct.

Per The Go Programming Language Specification, append examines the capacity of the array that backs the slice, and only allocates new memory (copying the slice) if there's not enough room in the backing array. [link] I don't see anything in the specification proper that specifies how much memory it should allocate, but according to the blog post you link to, the new block of memory will be 1.5 times the current size of the slice. That means that, after a reallocating/copying insertion, the next n/2 insertions will not require reallocating/copying. The overall effect is amortized O(1) time. This is the same approach used by the examples you mention in other languages (list in Python, std::vector in C++).

So, slices are exactly what you need.