Golang container list Example (Linked List)

Use the container list module for a linked list. Benchmark container list against slices.

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.

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

Slice

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.

Front, Next: These funcs are used to iterate through the list. Iteration in a container list will be slower than in a slice or array.

Golang program that uses container list 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) } } Output 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.

Golang program that benchmarks container list, slice 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)) } Output 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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Golang container list Example (Linked List)

Related Links:

.Net

Java

Related Links