Golang DSA Chapter 6 Part 1: Singly and Doubly Linked Lists

Chapter 6 of “Learn Data Structures and Algorithms with Golang” is all about heterogeneous data structures. That’s a fancy way of saying “data structures that can hold different types of data.” Think integers, floats, strings, whatever you need, all mixed together. Linked lists and ordered lists are the main examples here.

We touched on linked lists back in Chapters 3 and 4, but Chapter 6 goes deeper. This first part covers singly linked lists and doubly linked lists with full Go code. Part 2 will handle circular linked lists and ordered lists.

What Are Linked Lists Again?

A linked list is a chain of elements where each element points to the next one. Unlike arrays, linked lists don’t need a continuous block of memory. Each node can live anywhere in memory, and the pointers connect them together.

The tradeoff? Linked lists use more memory than arrays because of those pointers. And you can’t just jump to element number 47. You have to start at the beginning and walk through each node until you get there.

But they’re great when you need to add or remove elements a lot, because you just update the pointers instead of shifting everything around.

Singly Linked Lists

A singly linked list is the simplest flavor. Each node has some data and a pointer to the next node. That’s it. You can only move forward through the list.

Here’s the basic Node struct from the book:

package main

import (
    "fmt"
)

// Node struct
type Node struct {
    nextNode *Node
    property rune
}

Each Node holds a rune (basically a character) and a pointer to the next node. Simple enough.

Creating a Linked List

The CreateLinkedList function builds a list of all lowercase letters from ‘a’ to ‘z’. It starts by making the head node with ‘a’, then loops through the rest of the alphabet and chains them together:

func CreateLinkedList() *Node {
    var headNode *Node
    headNode = &Node{nil, 'a'}
    var currNode *Node
    currNode = headNode
    var i rune
    for i = 'b'; i <= 'z'; i++ {
        var node *Node
        node = &Node{nil, i}
        currNode.nextNode = node
        currNode = node
    }
    return headNode
}

The pattern is straightforward. You keep a currNode that tracks where you are. Each time through the loop you create a new node, point the current node’s nextNode to it, then move currNode forward. At the end, you return the head, which gives you access to the whole chain.

Reversing a Singly Linked List

Reversing a singly linked list is one of those classic problems that shows up everywhere, interviews included. The idea is to walk through the list and flip all the pointers so they point backward instead of forward.

func ReverseLinkedList(nodeList *Node) *Node {
    var currNode *Node
    currNode = nodeList
    var topNode *Node = nil
    for {
        if currNode == nil {
            break
        }
        var tempNode *Node
        tempNode = currNode.nextNode
        currNode.nextNode = topNode
        topNode = currNode
        currNode = tempNode
    }
    return topNode
}

Here’s what’s happening step by step:

1. Start at the head of the list
2. Save the next node in a temp variable (so you don’t lose it)
3. Point the current node’s nextNode backward to topNode
4. Move topNode forward to the current node
5. Move to the next node using your temp variable
6. Repeat until you hit the end

When you’re done, topNode is the new head of the reversed list. The original ‘a’ to ‘z’ list becomes ‘z’ to ‘a’.

Putting It Together

The main function creates the list, prints it, reverses it, and prints again:

func main() {
    var linkedList = CreateLinkedList()
    StringifyList(linkedList)
    StringifyList(ReverseLinkedList(linkedList))
}

You run it with go run linked_list.go and you’ll see the alphabet printed forward, then backward. Nothing surprising, but it proves the reversal works.

Doubly Linked Lists

A doubly linked list is like a singly linked list, but each node has two pointers: one to the next node and one to the previous node. This means you can walk the list in both directions.

Go actually has a built-in doubly linked list in the container/list package. So instead of building one from scratch, the book shows you how to use the standard library version.

package main

import (
    "container/list"
    "fmt"
)

func main() {
    var linkedList *list.List
    linkedList = list.New()
    var element *list.Element
    element = linkedList.PushBack(14)
    var frontElement *list.Element
    frontElement = linkedList.PushFront(1)
    linkedList.InsertBefore(6, element)
    linkedList.InsertAfter(5, frontElement)

    var currElement *list.Element
    for currElement = linkedList.Front(); currElement != nil; currElement = currElement.Next() {
        fmt.Println(currElement.Value)
    }
}

Let’s break down what’s happening:

• list.New() creates an empty doubly linked list
• PushBack(14) adds 14 to the end of the list
• PushFront(1) adds 1 to the front
• InsertBefore(6, element) puts 6 right before the element holding 14
• InsertAfter(5, frontElement) puts 5 right after the element holding 1

So the final order is: 1, 5, 6, 14.

The for loop at the bottom starts at Front() and walks forward using Next() until it hits nil. If you wanted to go backward, you’d start at Back() and use Prev() instead. That’s the whole point of a doubly linked list, you can go either direction.

Run it with go run double_linked_list.go and you get each number printed on its own line.

Singly vs Doubly: When to Use Which

The big question is always “which one should I pick?” Here’s the short version:

Singly linked lists are lighter on memory because each node only has one pointer. If you only ever need to go forward through your data, they’re the better pick. Stacks and simple queues are often built on singly linked lists.

Doubly linked lists cost more memory (two pointers per node instead of one) but give you the ability to traverse backward. If you need to delete a node and you already have a reference to it, a doubly linked list can do that in O(1) time because you can access the previous node directly. With a singly linked list, you’d have to walk from the head to find the node before it.

Go’s standard library chose doubly linked lists for its container/list package, which tells you something about what the language designers thought was more generally useful.

What We Covered

This first half of Chapter 6 walked through:

• Heterogeneous data structures as a concept, data structures that hold mixed types
• Singly linked lists with creation, traversal, and reversal in Go
• Doubly linked lists using Go’s built-in container/list package
• The practical differences between the two and when you’d pick one over the other

In Part 2, we’ll look at circular linked lists (where the last node points back to the first) and ordered lists with sorting. Things get more interesting from there.

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). You can find all posts in the series introduction.