Go Cookbook

Chapter 14. More Data Structure Recipes

14.0 Introduction

Chapter 12 discussed structs and Chapter 13 discussed arrays, slices, and maps. These are the four basic data structures in Go. Unlike many other programming languages, Go does not provide other basic data structures (although there is the container package in the standard library it has very few implementations). In your daily programming tasks, you often will have to use some other data structures that are not provided either in the language or in the standard library, and it’s not very difficult to re-create them.

In this chapter, you will be creating a few common data structures with Go:

• Queue

• Stack

• Set

• Linked list

• Heap

• Graph

Each recipe will start by explaining what that data structure is, then go through how to build one from the ground up.

None of the data structures are concurrency-safe. This is because fundamentally they are built on the three basic Go data structures—arrays, slices, and maps—and these are not concurrency-safe. To avoid race conditions, you can add a mutex to the data structure and use it to lock the data structure before any reads or writes. The sync package has a RWMutex that you can use for this purpose.

A word on the terminology: these recipes use the term list to refer to a linear, ordered sequence of items. Items within a list are called elements. Arrays and slices in Go are lists. Similarly, a graph refers to a group of items that are connected. Items within a graph are called ...