Container list. In a linked list, pointers are maintained on each element. This makes insertion and removal from the list fast, but slows down iteration.
In Golang we can use the "container/list" package. This implements a linked list. We can make some list-building programs much faster with this package.
An example. We create a list with the list.New func. We must be careful to include "container/list" with an import at the top of the program.
Detail This adds an element to the end of the list. It is like the append() method on a slice.
Detail Inserts an element at the front of the list. This shows the advantage of using a container list—inserting at the front is fast.
Detail These funcs are used to iterate through the list. Iteration in a container list will be slower than in a slice or array.
package main
import (
"container/list""fmt""strconv"
)
func main() {
// New list.
values := list.New()
// Add 3 elements to the list.
values.PushBack("bird")
values.PushBack("cat")
values.PushFront("snake")
// Add 100 elements at the front.
for i := 0; i < 20; i++ {
// Convert ints to strings.
values.PushFront(strconv.Itoa(i))
}
// Loop over container list.
for temp := values.Front(); temp != nil; temp = temp.Next() {
fmt.Println(temp.Value)
}
}19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
snake
bird
cat
List performance. Let us test the performance of the PushFront() method on a container list. Here we test PushFront against a slice where we use append, and then add all following elements.
Version 1 We use a container list, and use PushFront to add 20 strings to the start of the list.
Version 2 We use slices, and then append an element and all following elements (to duplicate PushFront functionality).
Result The container list is many times faster than the slice implementation. A doubly-linked list has advantages for this use case.
package main
import (
"container/list""fmt""time""strconv"
)
func main() {
t0 := time.Now()
// Version 1: use container list.
for i := 0; i < 10000; i++ {
// New list.
values := list.New()
// Add 2 elements to the list.
values.PushBack("bird")
values.PushBack("cat")
// Add 20 elements at the front.
for i := 0; i < 20; i++ {
// Convert ints to strings.
values.PushFront(strconv.Itoa(i))
}
}
t1 := time.Now()
// Version 2: use slice.
for i := 0; i < 10000; i++ {
// New empty slice.
values := []string{}
// Add 2 elements to the slice.
values = append(values, "bird")
values = append(values, "cat")
// Add 20 elements at the front.
for i := 0; i < 20; i++ {
// Create a new slice and put the string at its start.// ... This inserts as the front.
tempSlice := []string{}
tempSlice = append(tempSlice, strconv.Itoa(i))
// Now append all previous strings after the first one.
for x := range(values) {
tempSlice = append(tempSlice, values[x])
}
// Use the new slice.
values = tempSlice
}
}
t2 := time.Now()
// Results.
fmt.Println(t1.Sub(t0))
fmt.Println(t2.Sub(t1))
} 24.4054ms container/list
119.5599ms slice
A review. The container list has performance tradeoffs. If your Go program does many insertions or deletions at various places in a list, the container list is a good choice.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.