Golang DSA Chapter 3 Part 1: Lists, Sets, and Tuples in Go
Chapter 3 is where the book starts getting into the real stuff. We’re past the basics of Go syntax and data types, and now it’s time to build actual data structures from scratch. This first half covers three linear data structures: linked lists (both single and double), sets, and tuples.
Linear just means the elements are arranged in a sequence, one after another. Think of it like a line at a coffee shop. Everyone’s in order, and you can walk from the first person to the last without jumping around.
Let’s get into it.
Linked Lists
A linked list is a chain of nodes where each node holds some data and a pointer to the next node. Unlike arrays, linked list elements aren’t sitting next to each other in memory. Each node just knows where the next one lives. That’s it.
This makes linked lists flexible. You can add or remove elements without shifting everything around like you’d have to with an array.
The Building Blocks
The book defines two structs. First, a Node that holds an integer value and a pointer to the next node:
type Node struct {
property int
nextNode *Node
}
Then a LinkedList struct that just keeps track of the head (the first node):
type LinkedList struct {
headNode *Node
}
Simple so far. The whole list is just a pointer to the first node, and from there you follow the chain.
Adding to the Head
The AddToHead method sticks a new node at the beginning of the list. It creates a new node, points it to the current head, then makes that new node the head:
func (linkedList *LinkedList) AddToHead(property int) {
var node = Node{}
node.property = property
if node.nextNode != nil {
node.nextNode = linkedList.headNode
}
linkedList.headNode = &node
}
So if your list is [1] and you add 3 to the head, it becomes [3, 1]. The new node just takes over the front of the line.
Walking Through the List
To see what’s in the list, you iterate from the head and follow each nextNode pointer until you hit nil:
func (linkedList *LinkedList) IterateList() {
var node *Node
for node = linkedList.headNode; node != nil; node = node.nextNode {
fmt.Println(node.property)
}
}
Nothing fancy. Just a for loop that walks the chain.
Finding the Last Node
The LastNode method traverses the whole list and returns whatever node has nextNode == nil. That’s the tail:
func (linkedList *LinkedList) LastNode() *Node {
var node *Node
var lastNode *Node
for node = linkedList.headNode; node != nil; node = node.nextNode {
if node.nextNode == nil {
lastNode = node
}
}
return lastNode
}
Adding to the End
Once you can find the last node, adding to the end is straightforward. Find the last node, point its nextNode to the new one:
func (linkedList *LinkedList) AddToEnd(property int) {
var node = &Node{}
node.property = property
node.nextNode = nil
var lastNode *Node
lastNode = linkedList.LastNode()
if lastNode != nil {
lastNode.nextNode = node
}
}
Finding a Node by Value
Sometimes you need to find a specific node. The NodeWithValue method walks through the list and returns the first node that matches:
func (linkedList *LinkedList) NodeWithValue(property int) *Node {
var node *Node
var nodeWith *Node
for node = linkedList.headNode; node != nil; node = node.nextNode {
if node.property == property {
nodeWith = node
break
}
}
return nodeWith
}
Inserting After a Specific Node
The AddAfter method combines search and insertion. It finds a node with a given value, then inserts a new node right after it:
func (linkedList *LinkedList) AddAfter(nodeProperty int, property int) {
var node = &Node{}
node.property = property
node.nextNode = nil
var nodeWith *Node
nodeWith = linkedList.NodeWithValue(nodeProperty)
if nodeWith != nil {
node.nextNode = nodeWith.nextNode
nodeWith.nextNode = node
}
}
The trick here is getting the pointer reassignment right. The new node’s nextNode grabs whatever was after the found node, and then the found node’s nextNode points to the new node. It’s like cutting in line, but politely.
Putting It All Together
Here’s how all these methods work together:
func main() {
var linkedList LinkedList
linkedList = LinkedList{}
linkedList.AddToHead(1)
linkedList.AddToHead(3)
linkedList.AddToEnd(5)
linkedList.AddAfter(1, 7)
linkedList.IterateList()
}
This prints 3, 1, 7, 5. First 1 goes to the head, then 3 goes to the head (pushing 1 back), then 5 goes to the end, and finally 7 gets inserted after 1.
Doubly Linked Lists
A doubly linked list is the same idea, but each node has TWO pointers: one to the next node and one to the previous node. You can walk forward and backward.
type Node struct {
property int
nextNode *Node
previousNode *Node
}
The LinkedList struct stays the same, just a pointer to the head.
Finding a Node Between Two Values
The NodeBetweenValues method is specific to doubly linked lists. It finds a node whose previous node has one value and whose next node has another:
func (linkedList *LinkedList) NodeBetweenValues(firstProperty int, secondProperty int) *Node {
var node *Node
var nodeWith *Node
for node = linkedList.headNode; node != nil; node = node.nextNode {
if node.previousNode != nil && node.nextNode != nil {
if node.previousNode.property == firstProperty && node.nextNode.property == secondProperty {
nodeWith = node
break
}
}
}
return nodeWith
}
This only works because we have that previousNode pointer. In a singly linked list, you’d have to track the previous node manually.
AddToHead for Doubly Linked Lists
Adding to the head is slightly more involved now. You need to update the old head’s previousNode to point back to the new node:
func (linkedList *LinkedList) AddToHead(property int) {
var node = &Node{}
node.property = property
node.nextNode = nil
if linkedList.headNode != nil {
node.nextNode = linkedList.headNode
linkedList.headNode.previousNode = node
}
linkedList.headNode = node
}
AddAfter for Doubly Linked Lists
Same concept as the singly linked version, but you also set the previousNode on the new node:
func (linkedList *LinkedList) AddAfter(nodeProperty int, property int) {
var node = &Node{}
node.property = property
node.nextNode = nil
var nodeWith *Node
nodeWith = linkedList.NodeWithValue(nodeProperty)
if nodeWith != nil {
node.nextNode = nodeWith.nextNode
node.previousNode = nodeWith
nodeWith.nextNode = node
}
}
AddToEnd for Doubly Linked Lists
Same pattern again. Find the last node, link in both directions:
func (linkedList *LinkedList) AddToEnd(property int) {
var node = &Node{}
node.property = property
node.nextNode = nil
var lastNode *Node
lastNode = linkedList.LastNode()
if lastNode != nil {
lastNode.nextNode = node
node.previousNode = lastNode
}
}
The main method for the doubly linked list builds the same sequence and then uses NodeBetweenValues to find the node sitting between values 1 and 5, which turns out to be 7.
The key takeaway: doubly linked lists cost you a bit more memory (extra pointer per node) but give you the ability to traverse backwards. It’s a classic trade-off.
Sets
A set is a collection of unique values. No duplicates allowed. If you try to add something that’s already there, nothing happens.
Go doesn’t have a built-in set type, so the book builds one using a map with bool values:
type Set struct {
integerMap map[int]bool
}
func (set *Set) New() {
set.integerMap = make(map[int]bool)
}
The map keys are the actual set elements, and the values are just true to indicate presence. It’s a common Go pattern.
Adding Elements
The AddElement method checks if the element already exists before adding:
func (set *Set) AddElement(element int) {
if !set.ContainsElement(element) {
set.integerMap[element] = true
}
}
Deleting Elements
Deletion is just Go’s built-in delete function on the map:
func (set *Set) DeleteElement(element int) {
delete(set.integerMap, element)
}
Checking if an Element Exists
The ContainsElement method does a map lookup:
func (set *Set) ContainsElement(element int) bool {
var exists bool
_, exists = set.integerMap[element]
return exists
}
Intersection
The Intersect method returns a new set containing only elements that exist in both sets:
func (set *Set) Intersect(anotherSet *Set) *Set {
var intersectSet = &Set{}
intersectSet.New()
var value int
for value, _ = range set.integerMap {
if anotherSet.ContainsElement(value) {
intersectSet.AddElement(value)
}
}
return intersectSet
}
Walk through one set, check each element against the other. If it’s in both, add it to the result. Classic set intersection.
Union
The Union method returns a new set containing all elements from both sets:
func (set *Set) Union(anotherSet *Set) *Set {
var unionSet = &Set{}
unionSet.New()
var value int
for value, _ = range set.integerMap {
unionSet.AddElement(value)
}
for value, _ = range anotherSet.integerMap {
unionSet.AddElement(value)
}
return unionSet
}
Since AddElement already prevents duplicates, you just dump everything from both sets in and let it handle the rest.
Using Sets
Here’s how it all comes together:
func main() {
var set *Set
set = &Set{}
set.New()
set.AddElement(1)
set.AddElement(2)
var anotherSet *Set
anotherSet = &Set{}
anotherSet.New()
anotherSet.AddElement(2)
anotherSet.AddElement(4)
anotherSet.AddElement(5)
fmt.Println(set.Intersect(anotherSet)) // {2}
fmt.Println(set.Union(anotherSet)) // {1, 2, 4, 5}
}
Set {1, 2} intersected with {2, 4, 5} gives you {2}. Union gives you {1, 2, 4, 5}. Exactly what you’d expect from your math class.
Tuples
Tuples are ordered sequences of values, often of different types. In relational databases, a tuple is basically a row in a table.
Go doesn’t have a tuple type like Python does. But you can fake it using multiple return values from functions. The book shows this pattern:
func h(x int, y int) int {
return x * y
}
func g(l int, m int) (x int, y int) {
x = 2 * l
y = 4 * m
return
}
func main() {
fmt.Println(h(g()))
}
Function g returns two integers (that’s your “tuple”), and function h takes those two integers and multiplies them. The trick is that you can pass g() directly into h() because Go unpacks the multiple return values as arguments.
It’s a short section in the book, but it makes an important point. Go handles tuples through multiple return values instead of a dedicated data type. If you’ve used Python or Rust, you’re used to actual tuple types. In Go, it’s more of a convention.
What I Think
This chapter is where you start building real things. The linked list implementation is a solid exercise in pointer manipulation, and honestly, if you can follow how AddAfter works with all the pointer reassignment, you understand a big chunk of how data structures work internally.
The set implementation is practical too. That map[int]bool pattern shows up all the time in real Go code when you need to track unique values.
Tuples are the lightweight section here, but understanding multiple return values is fundamental to Go.
Next up, we’ll cover the second half of Chapter 3, which gets into stacks, queues, and heaps.
Book: “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi (Packt Publishing, 2019, ISBN: 978-1-78961-850-1)
Navigation: