There are many ways to organize sequential data in the programming world. The most common ones are the abstract data types array and list. They are at the beginning of every programmer's learning journey. With arrays and lists we can implement our first for loops, we can store those notes for the note taking app we are building, or implement our own buffer.
In this post, we will have a look at how these data types are implemented in Go. After defining what exactly those types are, we will inspect static arrays and why we have slices instead of lists in Go. Finally we will look at the complexity of working with these types to get a better grasp on when to use these data types.
Static Arrays
Static arrays are at the core of every programming language. They have a fixed length of n, which has to be defined upfront. In memory, all elements of the array are stored adjacently. If you want to iterate over an array, this can be achieved via an index starting at 0 for the first element and ending at n - 1 for the last. In Go, arrays and slices are both evaluated during runtime. Furthermore, the length of a slice is also part of the array type, so int[10] and int[20] are different types.
Declaration and initialization
There are different ways to declare and initialize an array. We can first declare it and set its values explicitly.
var array [3]string
array[0] = "all"
array[1] = "the"
array[2] = "elements"
Or we declare and initialize it with one line.
var array = [4]int32 {23, 12, -1, 8}
Accessing elements
Elements are accessed by their index. The following statement gives us the second element of an array.
var secondElement = array[1]
Specifying an index lower than 0 or greater than n - 1 results in an index out of bound error. In Go, specifying an index out of range will not even compile.
Searching elements
Searching elements can be done via iteration and a simple if condition.
for i := 0; i < len(array); i++ {
if array[i] == "foo" {
fmt.Println("Found foo")
}
}
Time complexity
Since static arrays are fixed in size, our options to work with them are limited to only accessing and searching for data.
| Action | Complexity |
|---|---|
| Accessing elements | O(1) |
| Searching elements | O(n) |
Slices
With slices things get interesting. The ability to grow and shrink this dynamic-array-like data structure in size gives us a new set of possibilities to work with. Before inspecting how they are used, let's have a closer look at slices and how they are special compared to similiar data structures of different languages.
Compared to other languages, creating a slice from an array is basically just a struct with a pointer to the array and two variables holding length and capacity of the array. It does not allocate any new memory. As a consequence, basic operations on slices are very cheap. Creating, moving on or expanding the respective array (until the capacity is reached) can all be done without any new memory allocation. This leaves the user with the indicated dynamic-array-like feeling when working with slices.
Declaration and initialization
Here, we also have different ways to declare and initialize an array. This time we start with the declaration and initialization combined. This will create a slice with an underlying array of size and capacity 4.
var slice = []int32 {23, 12, -1, 8}
This is fairly convenient, but may not be the most efficient way. This way, when adding an element via the append()function, a new array has to be allocated in memory. On the other hand, Go gives us the tools to handle the allocation ourselves.
var slice = make([]int, 2, 3)
slice[0] = 6
slice[1] = 12
This make function creates a new slice with an underlying array of length 2 and capacity 3.
Appending elements
When we add one more element to the slice above, no new memory is allocated, because of the big enough capacity, which improves our efficiency. Another element more and a new array hast to be created.
slice = append(slice, 7) // still working on the same array
slice = append(slice, 14) // allocates new memory, since we expanded the capacity
You can easily test this behaviour on your own. If you want to know more about what exactly happens when appending new elements in Go, I recommend this article from The Go Blog.
Slicing a slice
We can create a "sub-slice" of a slice by specifying the upper and lower index like this.
var subSlice = slice[2:5]
Note that this does not create a new slice. We are still operating on the same data in memory. You should be aware that this is behaviour might lead to the fact that your program holds more data in memory than you might expect.
Deleting elements
Since Go does not have a respective method in its standard library, let's implement a method to delete an element of a slice of strings.
func remove(slice []string, element string) error {
i := -1
for j := 0; j < len(slice); j++ {
if slice[j] == element {
i = j
}
}
if i == -1 {
return errors.New("element not found in slice")
}
slice = append(slice[:i], slice[i+1:]...)
return nil
}
If you watch closely, you can see that we can use our sub-slicing syntax with variadic arguments to cut the element from our slice. Another quite convenient feature at this place.
Inserting elements
We do the same for inserting new elements.
func insert(slice []string, index int, element string) []string {
return append(slice[:index], append([]string{element}, slice[index:]...)...)
}
In this case, we have no other option than creating a new slice with the append() function. Again we can use variadic arguments as a shortcut.
Time complexity
Now, let's enhance our time complexity chart for the available operations appending, inserting and deleting.
| Action | Complexity |
|---|---|
| Accessing elements | O(1) |
| Searching elements | O(n) |
| Appending elements | O(1) |
| Inserting elements | O(n) |
| Deleting elements | O(n) |
Conclusion
As we can see, working with arrays and slices in Go is quite convenient while there are some specialities which might be surprising for developers with a background in other languages. Generally spoken, working with arrays is very foreseeable and easy, which is why they are so popular. Nevertheless, when we work with large or specially structured data, they might not always suite your use case and come with certain performance downsides.
I will elaborate on this in future posts on data structures in Go. For now, I hope I could shed some light onto these data types and their implementation. If you have any questions, feedback or just want to discuss about the topic, feel free to contact me via mail or follow me on Twitter.
Top comments (0)