13.05-Container and Sort

Containers & Sort

In addition to lists and maps Go has several more collections available underneath the container package. We'll take a look at the container/list package as an example.

List

The container/list package implements a doubly-linked list. A linked list is a type of data structure that looks like this:


Each node of the list contains a value (1, 2, or 3 in this case) and a pointer to the next node. Since this is a doubly-linked list each node will also have pointers to the previous node. This list could be created by this program:

package main

import ("fmt" ; "container/list")

func main() {
    var x list.List
    x.PushBack(1)
    x.PushBack(2)
    x.PushBack(3)

    for e := x.Front(); e != nil; e=e.Next() {
        fmt.Println(e.Value.(int))
    }
}

The zero value for a List is an empty list (a *List can also be created using list.New). Values are appended to the list using PushBack. We loop over each item in the list by getting the first element, and following all the links until we reach nil.

Sort

The sort package contains functions for sorting arbitrary data. There are several predefined sorting functions (for slices of ints and floats) Here's an example for how to sort your own data:

package main

import ("fmt" ; "sort")

type Person struct { 
    Name string
    Age int
}

type ByName []Person

func (this ByName) Len() int {
    return len(this)
}
func (this ByName) Less(i, j int) bool {
    return this[i].Name < this[j].Name
}
func (this ByName) Swap(i, j int) {
    this[i], this[j] = this[j], this[i]
}

func main() {
    kids := []Person{
        {"Jill",9},
        {"Jack",10},
    }
    sort.Sort(ByName(kids))
    fmt.Println(kids)
}

The Sort function in sort takes a sort.Interface and sorts it. The sort.Interface requires 3 methods: LenLess and Swap. To define our own sort we create a new type (ByName) and make it equivalent to a slice of what we want to sort. We then define the 3 methods.

Sorting our list of people is then as easy as casting the list into our new type. We could also sort by age by doing this:

type ByAge []Person
func (this ByAge) Len() int {
    return len(this)
}
func (this ByAge) Less(i, j int) bool {
    return this[i].Age < this[j].Age
}
func (this ByAge) Swap(i, j int) {
    this[i], this[j] = this[j], this[i]
}

Comments