Go Data Structures and Algorithms

# CHAPTER 27

Go Data Structures and Algorithms #

1. Introduction #

2. Learning Objectives #

• Understand Time Complexity (Big O Notation).

• Implement a custom Stack (LIFO).

• Implement a custom Queue (FIFO).

• Build a Singly Linked List using Structs and Pointers.

• Understand basic searching concepts.

3. Big O Notation (Time Complexity) #

• O(1) - Constant Time: Excellent. The time does not change regardless of data size. (e.g., Looking up a value in a Go map).

• O(N) - Linear Time: Fair. The time increases linearly. (e.g., A for loop scanning through a Slice).

• O(N^2) - Quadratic Time: Terrible. Time skyrockets as data grows. (e.g., A loop inside a loop, often found in naive sorting algorithms like Bubble Sort).

4. Stacks (LIFO) #

package main
import "fmt"

type Stack struct {
    items []int
}

// Push adds an item to the top of the stack
func (s *Stack) Push(i int) {
    s.items = append(s.items, i)
}

// Pop removes and returns the top item
func (s *Stack) Pop() int {
    length := len(s.items)
    if length == 0 {
        return -1 // Stack is empty
    }
    // Get the last item
    topItem := s.items[length-1]
    
    // Reslice the array to remove the last item
    s.items = s.items[:length-1] 
    
    return topItem
}

func main() {
    myStack := Stack{}
    myStack.Push(10)
    myStack.Push(20)
    fmt.Println(myStack.Pop()) // Prints 20
}

5. Queues (FIFO) #

type Queue struct {
    items []int
}

// Enqueue adds to the back of the line
func (q *Queue) Enqueue(i int) {
    q.items = append(q.items, i)
}

// Dequeue removes from the front of the line
func (q *Queue) Dequeue() int {
    if len(q.items) == 0 {
        return -1
    }
    frontItem := q.items[0]
    
    // Reslice starting from index 1 to the end
    q.items = q.items[1:] 
    return frontItem
}

6. Linked Lists (Pointers in Action!) #

This is a classic interview question and relies heavily on Go's pointer syntax (*).

// 1. The Node Struct
type Node struct {
    Data int
    Next *Node // A pointer to the next node in the chain
}

// 2. The LinkedList Struct
type LinkedList struct {
    Head *Node // Points to the very first node
}

// 3. Add to the front of the list (O(1) Time!)
func (l *LinkedList) Prepend(data int) {
    newNode := &Node{Data: data}
    
    // The new node points to whatever the Head used to point to
    newNode.Next = l.Head 
    
    // The Head now points to the new node
    l.Head = newNode
}

// 4. Print the list
func (l *LinkedList) Print() {
    current := l.Head
    for current != nil {
        fmt.Printf("%d -> ", current.Data)
        current = current.Next
    }
    fmt.Println("nil")
}

func main() {
    list := LinkedList{}
    list.Prepend(3)
    list.Prepend(2)
    list.Prepend(1)
    list.Print() // Output: 1 -> 2 -> 3 -> nil
}

7. Searching Algorithms #

• Linear Search O(N): Looping through an unsorted slice one-by-one. Easy, but slow for massive datasets.

• Binary Search O(log N): If the slice is sorted, you can check the middle element. If your target is smaller, you discard the right half. You repeat this until found. It is incredibly fast. (Go provides sort.SearchInts in the standard library to do this for you!).

8. Common Mistakes #

• Memory Leaks in Queues: In our Queue example, q.items = q.items[1:] reslices the array, but the hidden underlying array doesn't shrink. Over time, a massive, long-running queue can cause memory bloat. For enterprise Queues, developers use Ring Buffers or Channels.

• Nil Pointer Panics: When iterating through a Linked List, forgetting to check if current != nil before accessing current.Data will instantly crash the program.

9. Best Practices #

• In 99% of web development tasks, standard Go Slices and Maps are perfectly optimized and preferable. You should only build custom Linked Lists or Trees if you are building databases, game engines, or highly specialized systems.

10. Exercises #

1. 1. Modify the Stack code so that it holds string values instead of int.

1. 2. Push "A", "B", and "C".

1. 3. Pop twice and print the results to verify "C" and then "B" are removed.

11. MCQs with Answers & Explanations #

12. Interview Preparation #

1. 1. Implement a Stack using Go slices.

1. 2. What is the difference in memory layout between a Slice and a Linked List?

1. 3. Explain the Reslicing operation slice[1:]. Does it create a new array in memory? (Answer: No, it creates a new slice header pointing to index 1 of the existing hidden array).

13. Summary #

14. Next Chapter Recommendation #