Golang DSA Chapter 6 Part 2: Circular Lists and Ordered Lists
Welcome back to Chapter 6 of “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi. In Part 1 we covered singly and doubly linked lists. Now we pick up where we left off: circular linked lists, ordered lists, and unordered lists.
These are still linked list variations at heart, but each one solves a slightly different problem. Let’s walk through them.
Circular Linked Lists
A circular linked list is exactly what it sounds like. The last node connects back to the first node, forming a loop. There’s no nil at the end. You just keep going around.
The book mentions that circular linked lists were briefly introduced back in Chapter 4 (non-linear data structures). Here in Chapter 6, the author builds a practical circular queue using this concept.
The CircularQueue Struct
The struct has four fields: size for the queue capacity, nodes as an array of interface{} to hold any type, plus head and last as integer indices tracking where we are in the circle.
type CircularQueue struct {
size int
nodes []interface{}
head int
last int
}
Creating a New Queue
The constructor function takes a number and builds a queue one slot bigger than requested. That extra slot is how circular queues tell the difference between “full” and “empty”, a classic trick.
func NewQueue(num int) *CircularQueue {
var circularQueue CircularQueue
circularQueue = CircularQueue{size: num + 1, head: 0, last: 0}
circularQueue.nodes = make([]interface{}, circularQueue.size)
return &circularQueue
}
Checking Status: IsUnUsed and IsComplete
Two helper methods tell you whether the queue is empty or full. IsUnUsed returns true when head equals last, meaning nothing has been added (or everything has been consumed). IsComplete checks if the queue is at capacity using modular arithmetic:
func (circularQueue CircularQueue) IsUnUsed() bool {
return circularQueue.head == circularQueue.last
}
func (circularQueue CircularQueue) IsComplete() bool {
return circularQueue.head == (circularQueue.last+1)%circularQueue.size
}
That modulo operation is the key to the whole circular behavior. It wraps around instead of running off the end of the array.
Adding Elements
The Add method places an element at the last position, then bumps last forward using modulo. If the queue is full, it panics:
func (circularQueue *CircularQueue) Add(element interface{}) {
if circularQueue.IsComplete() {
panic("Queue is Completely Utilized")
}
circularQueue.nodes[circularQueue.last] = element
circularQueue.last = (circularQueue.last + 1) % circularQueue.size
}
Moving Through the Queue
MoveOneStep grabs the element at head and advances the head pointer forward by one (again, with modulo). If the queue is empty, it returns nil:
func (circularQueue *CircularQueue) MoveOneStep() (element interface{}) {
if circularQueue.IsUnUsed() {
return nil
}
element = circularQueue.nodes[circularQueue.head]
circularQueue.head = (circularQueue.head + 1) % circularQueue.size
return
}
Putting It Together
The main function creates a queue of size 5 and fills it up:
func main() {
var circularQueue *CircularQueue
circularQueue = NewQueue(5)
circularQueue.Add(1)
circularQueue.Add(2)
circularQueue.Add(3)
circularQueue.Add(4)
circularQueue.Add(5)
fmt.Println(circularQueue.nodes)
}
The modulo trick is doing all the heavy lifting here. Without it, you’d need to manually reset indices when they reach the end of the array. With it, everything just wraps naturally.
Ordered Lists
Now we shift gears from circular structures to sorting. The book covers two approaches for lists in Go:
- Ordered lists: you define a group of methods on a slice type and call
sort.Sort - Unordered lists: you use
sort.Slicewith a customlessfunction
The difference is simple. An ordered list cares about the sequence of items. An unordered list does not.
Sorting with sort.Sort
The first example uses an Employee struct with Name, ID, SSN, and Age fields:
type Employee struct {
Name string
ID string
SSN int
Age int
}
To sort employees by age, you create a named type and implement three methods: Len, Swap, and Less. These are required by Go’s sort.Interface:
type SortByAge []Employee
func (sortIntf SortByAge) Len() int { return len(sortIntf) }
func (sortIntf SortByAge) Swap(i int, j int) { sortIntf[i], sortIntf[j] = sortIntf[j], sortIntf[i] }
func (sortIntf SortByAge) Less(i int, j int) bool { return sortIntf[i].Age < sortIntf[j].Age }
Then in main, you just call sort.Sort:
func main() {
var employees = []Employee{
{"Graham", "231", 235643, 31},
{"John", "3434", 245643, 42},
{"Michael", "8934", 32432, 17},
{"Jenny", "24334", 32444, 26},
}
fmt.Println(employees)
sort.Sort(SortByAge(employees))
fmt.Println(employees)
}
You can also use sort.Slice for a quicker approach. Instead of defining a whole type with three methods, you just pass a comparison function:
sort.Slice(employees, func(i int, j int) bool {
return employees[i].Age > employees[j].Age
})
That sorts employees by age in descending order. Less ceremony, same result.
Sorting by Multiple Criteria
The book then shows a more advanced pattern, sorting by single keys using a ByFactor function type. You define a Thing struct with properties like name, mass, and distance:
type Mass float64
type Miles float64
type Thing struct {
name string
mass Mass
distance Miles
meltingpoint int
freezingpoint int
}
The ByFactor type is a function that compares two Things:
type ByFactor func(Thing1 *Thing, Thing2 *Thing) bool
Then you define ThingSorter which wraps a slice of Things along with the comparison function, and you implement Len, Swap, and Less on it:
type ThingSorter struct {
Things []Thing
byFactor func(Thing1 *Thing, Thing2 *Thing) bool
}
func (ThingSorter *ThingSorter) Len() int { return len(ThingSorter.Things) }
func (ThingSorter *ThingSorter) Swap(i int, j int) {
ThingSorter.Things[i], ThingSorter.Things[j] = ThingSorter.Things[j], ThingSorter.Things[i]
}
func (ThingSorter *ThingSorter) Less(i int, j int) bool {
return ThingSorter.byFactor(&ThingSorter.Things[i], &ThingSorter.Things[j])
}
The cool part is you can now sort by any field just by swapping out the comparison function:
var name func(*Thing, *Thing) bool
name = func(Thing1 *Thing, Thing2 *Thing) bool {
return Thing1.name < Thing2.name
}
var distance func(*Thing, *Thing) bool
distance = func(Thing1 *Thing, Thing2 *Thing) bool {
return Thing1.distance < Thing2.distance
}
ByFactor(name).Sort(Things)
fmt.Println("By name:", Things)
ByFactor(distance).Sort(Things)
fmt.Println("By distance:", Things)
You can even flip the order by wrapping one comparison inside another:
var decreasingDistance func(*Thing, *Thing) bool
decreasingDistance = func(p1, p2 *Thing) bool {
return distance(p2, p1)
}
Swapping the arguments is a clean way to reverse sort order. No need for a separate flag or reverse function.
Multi-Key Sorting
The book takes it one step further with the multiSorter pattern. This lets you chain multiple sort criteria together. Think “sort by language, then by number of lines.”
The setup uses a Commit struct:
type Commit struct {
username string
lang string
numlines int
}
And a multiSorter that holds multiple comparison functions:
type lessFunc func(p1 *Commit, p2 *Commit) bool
type multiSorter struct {
Commits []Commit
lessFunction []lessFunc
}
The OrderedBy function accepts any number of comparison functions (using variadic arguments) and returns a multiSorter:
func OrderedBy(lessFunction ...lessFunc) *multiSorter {
return &multiSorter{
lessFunction: lessFunction,
}
}
The Less method is the interesting part. It walks through each comparison function in order. If one function can determine the ordering, it returns immediately. If two elements are equal by that criterion, it falls through to the next function:
func (multiSorter *multiSorter) Less(i int, j int) bool {
var p *Commit
var q *Commit
p = &multiSorter.Commits[i]
q = &multiSorter.Commits[j]
var k int
for k = 0; k < len(multiSorter.lessFunction)-1; k++ {
less := multiSorter.lessFunction[k]
switch {
case less(p, q):
return true
case less(q, p):
return false
}
}
return multiSorter.lessFunction[k](p, q)
}
This is a neat pattern. You build up your sort criteria like building blocks:
OrderedBy(user).Sort(Commits)
OrderedBy(user, increasingLines).Sort(Commits)
OrderedBy(language, decreasingLines, user).Sort(Commits)
Each call chains the criteria. Sort by username first, then by line count, then by language, whatever combination you need.
Unordered Lists
The last topic in this chapter is unordered lists. An unordered list is basically a plain linked list where items sit in whatever order they were added. No sorting, no rearranging.
The implementation is straightforward. A Node holds an integer property and a pointer to the next node:
type Node struct {
property int
nextNode *Node
}
The UnOrderedList just keeps a pointer to the head:
type UnOrderedList struct {
headNode *Node
}
Adding to the Head
The AddToHead method creates a new node, points it at the current head, then makes it the new head:
func (UnOrderedList *UnOrderedList) AddToHead(property int) {
var node = &Node{}
node.property = property
node.nextNode = nil
if UnOrderedList.headNode != nil {
node.nextNode = UnOrderedList.headNode
}
UnOrderedList.headNode = node
}
Since we always add to the front, the list ends up in reverse order of insertion. Add 1, 3, 5, 7, and the list reads 7, 5, 3, 1.
Iterating the List
Iteration is a simple walk from head to the end:
func (UnOrderedList *UnOrderedList) IterateList() {
var node *Node
for node = UnOrderedList.headNode; node != nil; node = node.nextNode {
fmt.Println(node.property)
}
}
Main Function
func main() {
var unOrderedList UnOrderedList
unOrderedList = UnOrderedList{}
unOrderedList.AddToHead(1)
unOrderedList.AddToHead(3)
unOrderedList.AddToHead(5)
unOrderedList.AddToHead(7)
unOrderedList.IterateList()
}
This prints 7, 5, 3, 1. Each new element pushes the previous ones down.
Wrapping Up
Chapter 6 Part 2 covered three distinct topics:
- Circular linked lists through a circular queue implementation, where modulo arithmetic handles the wrap-around behavior
- Ordered lists with Go’s
sort.Interface, including single-key and multi-key sorting patterns - Unordered lists as basic linked lists with no sorting guarantees
The multi-key sorting pattern using multiSorter is probably the most practical takeaway here. It’s a flexible way to handle complex sort logic without writing a bunch of one-off comparators. The circular queue is a solid exercise in understanding how modular arithmetic keeps index-based structures from running off the edge.
Next up, the book moves into dynamic data structures: dictionaries, TreeSets, sequences, and more.
This post is part of a series walking through “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi (Packt, 2019, ISBN: 978-1-78961-850-1). The goal is to retell each chapter in plain language with working code examples.