Home
Go
container list Example (Linked List)
This page was last reviewed on Dec 1, 2022.
Dot Net Perls
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.
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.
No updates found for this page.
Home
Changes
© 2007-2024 Sam Allen.