Golang DSA Chapter 1 Part 1: What Are Data Structures Anyway?
Chapter 1 of the book jumps right into classifying data structures and showing some structural design patterns in Go. There’s a lot packed in here, so I’m splitting it into two parts. This first part covers what data structures are, how they’re classified, and a bunch of design patterns with Go code.
Let’s get into it.
What Even Is a Data Structure?
A data structure is just how you organize data in memory so you can work with it quickly. That’s it. You pick one based on what problem you’re solving and what operations you need to do on the data.
The book breaks data structures into a few categories:
- Linear - lists, sets, tuples, queues, stacks, heaps. Things that go in a line, basically.
- Non-linear - trees, tables, containers. Things with more complex relationships.
- Homogeneous - two-dimensional and multi-dimensional arrays. Everything in them is the same type.
- Heterogeneous - linked lists, ordered lists, unordered lists. Can hold different types of data.
- Dynamic - dictionaries, tree sets, sequences. They can grow and shrink as needed.
The key idea is simple: pick the right structure for your problem and you’ll save yourself a lot of headaches.
Lists in Go
A list is a sequence of elements where each one can link to the next (or previous) one. Unlike arrays, lists have variable length, and adding or removing elements is easier.
Go has a built-in container/list package. Here’s how you use it:
package main
import (
"fmt"
"container/list"
)
func main() {
var intList list.List
intList.PushBack(11)
intList.PushBack(23)
intList.PushBack(34)
for element := intList.Front(); element != nil; element = element.Next() {
fmt.Println(element.Value.(int))
}
}
You add stuff with PushBack, then walk through the list with a for loop starting from Front(). Each element has a Value you can type-assert to whatever you put in there.
Tuples
Go doesn’t have tuples like Python does, but it has something just as useful: multiple return values. The book shows this with a power series function:
package main
import "fmt"
func powerSeries(a int) (int, int) {
return a * a, a * a * a
}
func main() {
var square int
var cube int
square, cube = powerSeries(3)
fmt.Println("Square", square, "Cube", cube)
}
You can also name the return values, which makes things cleaner:
func powerSeries(a int) (square int, cube int) {
square = a * a
cube = square * a
return
}
And if something might go wrong, you add an error return:
func powerSeries(a int) (int, int, error) {
square := a * a
cube := square * a
return square, cube, nil
}
This pattern of returning (result, error) is everywhere in Go. You’ll see it a million times.
Heaps
A heap is a partially ordered data structure. It’s not fully sorted, but it has a rule: in a max-heap, every parent node is bigger than its children. In a min-heap, every parent is smaller.
Go gives you container/heap for this. You need to implement a few interface methods (Len, Less, Swap, Push, Pop) on your own type:
package main
import (
"container/heap"
"fmt"
)
type IntegerHeap []int
func (iheap IntegerHeap) Len() int { return len(iheap) }
func (iheap IntegerHeap) Less(i, j int) bool { return iheap[i] < iheap[j] }
func (iheap IntegerHeap) Swap(i, j int) { iheap[i], iheap[j] = iheap[j], iheap[i] }
func (iheap *IntegerHeap) Push(heapintf interface{}) {
*iheap = append(*iheap, heapintf.(int))
}
func (iheap *IntegerHeap) Pop() interface{} {
var previous IntegerHeap = *iheap
n := len(previous)
x1 := previous[n-1]
*iheap = previous[0 : n-1]
return x1
}
func main() {
var intHeap *IntegerHeap = &IntegerHeap{1, 4, 5}
heap.Init(intHeap)
heap.Push(intHeap, 2)
fmt.Printf("minimum: %d\n", (*intHeap)[0])
for intHeap.Len() > 0 {
fmt.Printf("%d \n", heap.Pop(intHeap))
}
}
It’s a bit more setup than a list, but that’s the trade-off. You get efficient access to the minimum (or maximum) element, which is useful for things like priority queues and sorting algorithms.
Structural Design Patterns
The second half of this chapter section covers structural design patterns from the Gang of Four book. These patterns are about how you organize objects and classes to build bigger systems. The book covers adapter, bridge, composite, decorator, facade, and flyweight.
Let me walk through each one.
Adapter
The adapter pattern is basically a translator. You have two things that don’t speak the same language, and the adapter sits in the middle making them work together.
package main
import "fmt"
type IProcess interface {
process()
}
type Adapter struct {
adaptee Adaptee
}
func (adapter Adapter) process() {
fmt.Println("Adapter process")
adapter.adaptee.convert()
}
type Adaptee struct {
adapterType int
}
func (adaptee Adaptee) convert() {
fmt.Println("Adaptee convert method")
}
func main() {
var processor IProcess = Adapter{}
processor.process()
}
The client calls process() on the adapter, and the adapter calls convert() on the adaptee. The client never has to know about the adaptee’s interface. Pretty straightforward.
Bridge
The bridge pattern separates an abstraction from its implementation so you can change either one without breaking the other. Think of it as “composition over inheritance.”
The book’s example uses shapes and contours:
package main
import "fmt"
type IDrawShape interface {
drawShape(x [5]float32, y [5]float32)
}
type DrawShape struct{}
func (drawShape DrawShape) drawShape(x [5]float32, y [5]float32) {
fmt.Println("Drawing Shape")
}
type IContour interface {
drawContour(x [5]float32, y [5]float32)
resizeByFactor(factor int)
}
type DrawContour struct {
x [5]float32
y [5]float32
shape DrawShape
factor int
}
func (contour DrawContour) drawContour(x [5]float32, y [5]float32) {
fmt.Println("Drawing Contour")
contour.shape.drawShape(contour.x, contour.y)
}
func (contour DrawContour) resizeByFactor(factor int) {
contour.factor = factor
}
func main() {
var x = [5]float32{1, 2, 3, 4, 5}
var y = [5]float32{1, 2, 3, 4, 5}
var contour IContour = DrawContour{x, y, DrawShape{}, 2}
contour.drawContour(x, y)
contour.resizeByFactor(2)
}
DrawContour holds a DrawShape instance (composition). When you call drawContour, it delegates to drawShape. If you want to change how shapes are drawn, you swap the DrawShape implementation without touching the contour code.
Composite
The composite pattern lets you treat a group of objects the same way you treat a single one. Think of a file system: a folder can contain files and other folders, but you can “open” both.
package main
import "fmt"
type IComposite interface {
perform()
}
type Leaflet struct {
name string
}
func (leaf *Leaflet) perform() {
fmt.Println("Leaflet " + leaf.name)
}
type Branch struct {
leafs []Leaflet
name string
branches []Branch
}
func (branch *Branch) perform() {
fmt.Println("Branch: " + branch.name)
for _, leaf := range branch.leafs {
leaf.perform()
}
for _, branch := range branch.branches {
branch.perform()
}
}
func (branch *Branch) add(leaf Leaflet) {
branch.leafs = append(branch.leafs, leaf)
}
func (branch *Branch) addBranch(newBranch Branch) {
branch.branches = append(branch.branches, newBranch)
}
func main() {
var branch = &Branch{name: "branch 1"}
var leaf1 = Leaflet{name: "leaf 1"}
var leaf2 = Leaflet{name: "leaf 2"}
var branch2 = Branch{name: "branch 2"}
branch.add(leaf1)
branch.add(leaf2)
branch.addBranch(branch2)
branch.perform()
}
Both Leaflet and Branch implement IComposite. A branch can hold leaflets and other branches. When you call perform() on a branch, it runs through everything inside it recursively.
Decorator
The decorator pattern adds behavior to an object without changing the original class. It wraps the original and adds something extra.
package main
import "fmt"
type IProcess interface {
process()
}
type ProcessClass struct{}
func (process *ProcessClass) process() {
fmt.Println("ProcessClass process")
}
type ProcessDecorator struct {
processInstance *ProcessClass
}
func (decorator *ProcessDecorator) process() {
if decorator.processInstance == nil {
fmt.Println("ProcessDecorator process")
} else {
fmt.Printf("ProcessDecorator process and ")
decorator.processInstance.process()
}
}
func main() {
var process = &ProcessClass{}
var decorator = &ProcessDecorator{}
decorator.process()
decorator.processInstance = process
decorator.process()
}
First call prints just the decorator’s message. Second call, after setting the instance, runs both the decorator logic and the original. You can stack decorators to keep adding behavior.
Facade
The facade pattern gives you a simple interface for a complex system. Instead of calling ten different things, you call one facade that handles the mess behind the scenes.
The book uses a bank branch example:
package main
import "fmt"
type Account struct {
id string
accountType string
}
func (account *Account) create(accountType string) *Account {
fmt.Println("account creation with type")
account.accountType = accountType
return account
}
type Customer struct {
name string
id int
}
func (customer *Customer) create(name string) *Customer {
fmt.Println("creating customer")
customer.name = name
return customer
}
type Transaction struct {
id string
amount float32
srcAccountId string
destAccountId string
}
func (transaction *Transaction) create(srcAccountId string, destAccountId string, amount float32) *Transaction {
fmt.Println("creating transaction")
transaction.srcAccountId = srcAccountId
transaction.destAccountId = destAccountId
transaction.amount = amount
return transaction
}
type BranchManagerFacade struct {
account *Account
customer *Customer
transaction *Transaction
}
func NewBranchManagerFacade() *BranchManagerFacade {
return &BranchManagerFacade{&Account{}, &Customer{}, &Transaction{}}
}
func (facade *BranchManagerFacade) createCustomerAccount(customerName string, accountType string) (*Customer, *Account) {
var customer = facade.customer.create(customerName)
var account = facade.account.create(accountType)
return customer, account
}
func (facade *BranchManagerFacade) createTransaction(srcAccountId string, destAccountId string, amount float32) *Transaction {
var transaction = facade.transaction.create(srcAccountId, destAccountId, amount)
return transaction
}
func main() {
var facade = NewBranchManagerFacade()
customer, account := facade.createCustomerAccount("Thomas Smith", "Savings")
fmt.Println(customer.name)
fmt.Println(account.accountType)
var transaction = facade.createTransaction("21456", "87345", 1000)
fmt.Println(transaction.amount)
}
Instead of the client creating accounts, customers, and transactions separately, the BranchManagerFacade wraps it all up. One call does the work of many.
Flyweight
The flyweight pattern is about saving memory. When you have lots of objects that share common data, you store the shared stuff once and reference it instead of copying it everywhere.
The book uses a factory that creates data transfer objects and caches them by type:
package main
import "fmt"
type DataTransferObjectFactory struct {
pool map[string]DataTransferObject
}
func (factory DataTransferObjectFactory) getDataTransferObject(dtoType string) DataTransferObject {
var dto = factory.pool[dtoType]
if dto == nil {
fmt.Println("new DTO of dtoType: " + dtoType)
switch dtoType {
case "customer":
factory.pool[dtoType] = Customer{id: "1"}
case "employee":
factory.pool[dtoType] = Employee{id: "2"}
case "manager":
factory.pool[dtoType] = Manager{id: "3"}
case "address":
factory.pool[dtoType] = Address{id: "4"}
}
dto = factory.pool[dtoType]
}
return dto
}
type DataTransferObject interface {
getId() string
}
type Customer struct {
id string
name string
ssn string
}
func (customer Customer) getId() string { return customer.id }
type Employee struct {
id string
name string
}
func (employee Employee) getId() string { return employee.id }
type Manager struct {
id string
name string
dept string
}
func (manager Manager) getId() string { return manager.id }
type Address struct {
id string
streetLine1 string
streetLine2 string
state string
city string
}
func (address Address) getId() string { return address.id }
func main() {
var factory = DataTransferObjectFactory{make(map[string]DataTransferObject)}
var customer DataTransferObject = factory.getDataTransferObject("customer")
fmt.Println("Customer", customer.getId())
var employee DataTransferObject = factory.getDataTransferObject("employee")
fmt.Println("Employee", employee.getId())
var manager DataTransferObject = factory.getDataTransferObject("manager")
fmt.Println("Manager", manager.getId())
var address DataTransferObject = factory.getDataTransferObject("address")
fmt.Println("Address", address.getId())
}
First time you ask for a “customer” DTO, it creates one. Next time, it pulls from the pool. When you have thousands of objects, this saves real memory.
Quick Recap
So that’s the first half of Chapter 1. Here’s what we covered:
- Data structures are classified as linear, non-linear, homogeneous, heterogeneous, and dynamic
- Go has built-in packages for lists (
container/list) and heaps (container/heap) - Multiple return values in Go act like tuples
- Six structural design patterns: adapter, bridge, composite, decorator, facade, and flyweight
- Each pattern solves a specific problem around how objects relate to each other
The design patterns section might feel a bit out of place in a data structures book, but it makes sense. Before you build complex data structures, it helps to understand how to organize your code around them.
Next up, we’ll look at algorithms, complexity analysis, and how to think about performance.
This post is part of a series retelling “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi (Packt, 2019, ISBN: 978-1-78961-850-1). The code examples are adapted from the book.
- Previous: Series Introduction
- Next: Chapter 1 Part 2: Algorithms and Performance