Go - container list Example (Linked List)

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 Go 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.

Note PushBack adds an element to the end of the list. It is like the append() method on a slice.

Slice

Note 2 PushFront inserts an element at the front of the list. This shows the advantage of using a container list—inserting at the front is fast.

Finally The Front and Next 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

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.