Algorithms and Data Structures in Go: A Practical Guide

Algorithms and Data Structures in Go: A Practical Guide

Go (Golang) is a compiled, statically typed language created at Google. Its simplicity, high performance, and built-in concurrency support make it an excellent choice for backend development, microservices, and systems programming. However, to write efficient code in Go, knowing the syntax is not enough — you need to understand how algorithms and data structures work. In this article, we will break down key data structures and algorithms in Go, providing each section with practical examples.

1. Stack in Go

A stack is a data structure that operates on the LIFO (Last In, First Out) principle. Go does not have a built-in "stack" type, but it is easy to implement using a slice.

Example of a stack implementation:

package main\n\nimport "fmt"\n\ntype Stack struct {\n    items []int\n}\n\n// Push adds an element to the top of the stack\nfunc (s *Stack) Push(item int) {\n    s.items = append(s.items, item)\n}\n\n// Pop removes and returns the element from the top of the stack\nfunc (s *Stack) Pop() (int, bool) {\n    if len(s.items) == 0 {\n        return 0, false\n    }\n    lastIndex := len(s.items) - 1\n    item := s.items[lastIndex]\n    s.items = s.items[:lastIndex]\n    return item, true\n}\n\n// Peek returns the element from the top without removing it\nfunc (s *Stack) Peek() (int, bool) {\n    if len(s.items) == 0 {\n        return 0, false\n    }\n    return s.items[len(s.items)-1], true\n}\n\nfunc main() {\n    stack := Stack{}\n    stack.Push(10)\n    stack.Push(20)\n    stack.Push(30)\n\n    item, ok := stack.Pop()\n    if ok {\n        fmt.Println("Popped:", item) // 30\n    }\n    fmt.Println("Top of stack:", stack.Peek()) // 20\n}

A stack in Go is efficient due to the amortized O(1) complexity for Push and Pop operations. Use it for tasks like checking bracket sequences or implementing undo functionality.

2. Queue in Go

A queue operates on the FIFO (First In, First Out) principle. We will implement it using a slice with pointers to the front and back.

Example of a queue implementation:

package main\n\nimport "fmt"\n\ntype Queue struct {\n    items []int\n}\n\n// Enqueue adds an element to the end of the queue\nfunc (q *Queue) Enqueue(item int) {\n    q.items = append(q.items, item)\n}\n\n// Dequeue removes and returns the element from the front of the queue\nfunc (q *Queue) Dequeue() (int, bool) {\n    if len(q.items) == 0 {\n        return 0, false\n    }\n    item := q.items[0]\n    q.items = q.items[1:]\n    return item, true\n}\n\n// Front returns the first element without removing it\nfunc (q *Queue) Front() (int, bool) {\n    if len(q.items) == 0 {\n        return 0, false\n    }\n    return q.items[0], true\n}\n\nfunc main() {\n    queue := Queue{}\n    queue.Enqueue(1)\n    queue.Enqueue(2)\n    queue.Enqueue(3)\n\n    item, ok := queue.Dequeue()\n    if ok {\n        fmt.Println("Dequeued:", item) // 1\n    }\n    fmt.Println("First in queue:", queue.Front()) // 2\n}

Note: The Dequeue operation in this implementation has O(n) complexity because removing the first element shifts the entire slice. For production code, use a ring buffer or a doubly linked list (container/list).

3. Bubble Sort in Go

Bubble sort is one of the simplest but inefficient algorithms. Nevertheless, it is excellent for learning. Complexity: O(n²).

package main\n\nimport "fmt"\n\nfunc bubbleSort(arr []int) {\n    n := len(arr)\n    for i := 0; i < n-1; i++ {\n        swapped := false\n        for j := 0; j < n-i-1; j++ {\n            if arr[j] > arr[j+1] {\n                arr[j], arr[j+1] = arr[j+1], arr[j]\n                swapped = true\n            }\n        }\n        // If no swaps were made, the array is already sorted\n        if !swap