Skip to main content

Go Advanced Data Structures

Advanced data structures in Go go beyond the built-in types to create sophisticated, efficient, and reusable data models. By combining Go's built-in types with custom logic, you can create powerful data structures that solve complex problems efficiently. Understanding advanced data structures is crucial for building high-performance applications and solving real-world problems. This comprehensive guide will teach you everything you need to know about implementing advanced data structures in Go.

Understanding Advanced Data Structures in Go​

What Are Advanced Data Structures?​

Advanced data structures are custom implementations that extend beyond Go's built-in types to provide:

  • Specialized functionality - Tailored behavior for specific use cases
  • Performance optimization - Optimized for specific operations and data patterns
  • Complex relationships - Handle intricate data relationships and dependencies
  • Reusability - Generic implementations that can be adapted for different scenarios
  • Domain-specific logic - Business logic embedded in data structure operations

Go's Approach to Advanced Data Structures​

Go provides excellent support for creating advanced data structures:

Composition over Inheritance​

Go encourages composition through struct embedding and interface implementation.

Type Safety​

Go's type system ensures compile-time safety for custom data structures.

Performance Focus​

Go's design enables efficient implementations with predictable performance.

Simplicity and Clarity​

Go's syntax makes complex data structures readable and maintainable.

Custom Collection Implementations​

Stack Implementation​

The Stack Data Structure​

A stack is a Last-In-First-Out (LIFO) data structure with push and pop operations.

Generic Stack with Interface​

Using empty interfaces for generic stack implementation.

package main

import "fmt"

func main() {
    // Custom collection implementations examples
    fmt.Println("Custom collection implementations examples:")
    
    // Stack implementation
    type Stack struct {
        items []interface{}
    }
    
    // NewStack creates a new stack
    func NewStack() *Stack {
        return &Stack{
            items: make([]interface{}, 0),
        }
    }
    
    // Push adds an item to the top of the stack
    func (s *Stack) Push(item interface{}) {
        s.items = append(s.items, item)
    }
    
    // Pop removes and returns the top item from the stack
    func (s *Stack) Pop() interface{} {
        if s.IsEmpty() {
            return nil
        }
        
        index := len(s.items) - 1
        item := s.items[index]
        s.items = s.items[:index]
        return item
    }
    
    // Peek returns the top item without removing it
    func (s *Stack) Peek() interface{} {
        if s.IsEmpty() {
            return nil
        }
        
        return s.items[len(s.items)-1]
    }
    
    // IsEmpty returns true if the stack is empty
    func (s *Stack) IsEmpty() bool {
        return len(s.items) == 0
    }
    
    // Size returns the number of items in the stack
    func (s *Stack) Size() int {
        return len(s.items)
    }
    
    // String returns a string representation of the stack
    func (s *Stack) String() string {
        return fmt.Sprintf("Stack{%v}", s.items)
    }
    
    // Use the stack
    stack := NewStack()
    
    // Push items
    stack.Push(1)
    stack.Push(2)
    stack.Push(3)
    fmt.Printf("Stack after pushing 1, 2, 3: %s\n", stack)
    // Output: Stack after pushing 1, 2, 3: Stack{[1 2 3]}
    
    // Peek at top item
    fmt.Printf("Top item: %v\n", stack.Peek())
    // Output: Top item: 3
    
    // Pop items
    fmt.Printf("Popped: %v\n", stack.Pop())
    fmt.Printf("Popped: %v\n", stack.Pop())
    fmt.Printf("Stack after popping: %s\n", stack)
    // Output:
    // Popped: 3
    // Popped: 2
    // Stack after popping: Stack{[1]}
    
    // Check if empty
    fmt.Printf("Is empty: %t\n", stack.IsEmpty())
    // Output: Is empty: false
    
    // Pop remaining item
    fmt.Printf("Popped: %v\n", stack.Pop())
    fmt.Printf("Is empty: %t\n", stack.IsEmpty())
    // Output:
    // Popped: 1
    // Is empty: true
}

Queue Implementation​

The Queue Data Structure​

A queue is a First-In-First-Out (FIFO) data structure with enqueue and dequeue operations.

Efficient Queue with Slice​

Implementing a queue using Go slices with proper memory management.

package main

import "fmt"

func main() {
    // Queue implementation examples
    fmt.Println("Queue implementation examples:")
    
    // Queue implementation
    type Queue struct {
        items []interface{}
    }
    
    // NewQueue creates a new queue
    func NewQueue() *Queue {
        return &Queue{
            items: make([]interface{}, 0),
        }
    }
    
    // Enqueue adds an item to the rear of the queue
    func (q *Queue) Enqueue(item interface{}) {
        q.items = append(q.items, item)
    }
    
    // Dequeue removes and returns the front item from the queue
    func (q *Queue) Dequeue() interface{} {
        if q.IsEmpty() {
            return nil
        }
        
        item := q.items[0]
        q.items = q.items[1:]
        return item
    }
    
    // Front returns the front item without removing it
    func (q *Queue) Front() interface{} {
        if q.IsEmpty() {
            return nil
        }
        
        return q.items[0]
    }
    
    // Rear returns the rear item without removing it
    func (q *Queue) Rear() interface{} {
        if q.IsEmpty() {
            return nil
        }
        
        return q.items[len(q.items)-1]
    }
    
    // IsEmpty returns true if the queue is empty
    func (q *Queue) IsEmpty() bool {
        return len(q.items) == 0
    }
    
    // Size returns the number of items in the queue
    func (q *Queue) Size() int {
        return len(q.items)
    }
    
    // String returns a string representation of the queue
    func (q *Queue) String() string {
        return fmt.Sprintf("Queue{%v}", q.items)
    }
    
    // Use the queue
    queue := NewQueue()
    
    // Enqueue items
    queue.Enqueue("first")
    queue.Enqueue("second")
    queue.Enqueue("third")
    fmt.Printf("Queue after enqueueing: %s\n", queue)
    // Output: Queue after enqueueing: Queue{[first second third]}
    
    // Check front and rear
    fmt.Printf("Front: %v\n", queue.Front())
    fmt.Printf("Rear: %v\n", queue.Rear())
    // Output:
    // Front: first
    // Rear: third
    
    // Dequeue items
    fmt.Printf("Dequeued: %v\n", queue.Dequeue())
    fmt.Printf("Dequeued: %v\n", queue.Dequeue())
    fmt.Printf("Queue after dequeueing: %s\n", queue)
    // Output:
    // Dequeued: first
    // Dequeued: second
    // Queue after dequeueing: Queue{[third]}
    
    // Check size
    fmt.Printf("Size: %d\n", queue.Size())
    // Output: Size: 1
    
    // Dequeue remaining item
    fmt.Printf("Dequeued: %v\n", queue.Dequeue())
    fmt.Printf("Is empty: %t\n", queue.IsEmpty())
    // Output:
    // Dequeued: third
    // Is empty: true
}

Linked List Implementation​

The LinkedList Data Structure​

A linked list is a linear data structure where elements are stored in nodes.

Node Structure and Operations​

Implementing a linked list with proper node management.

package main

import "fmt"

func main() {
    // Linked list implementation examples
    fmt.Println("Linked list implementation examples:")
    
    // Node structure
    type Node struct {
        data interface{}
        next *Node
    }
    
    // LinkedList structure
    type LinkedList struct {
        head *Node
        size int
    }
    
    // NewLinkedList creates a new linked list
    func NewLinkedList() *LinkedList {
        return &LinkedList{}
    }
    
    // Add adds an item to the end of the list
    func (ll *LinkedList) Add(data interface{}) {
        newNode := &Node{data: data}
        
        if ll.head == nil {
            ll.head = newNode
        } else {
            current := ll.head
            for current.next != nil {
                current = current.next
            }
            current.next = newNode
        }
        ll.size++
    }
    
    // AddAt adds an item at a specific index
    func (ll *LinkedList) AddAt(index int, data interface{}) error {
        if index < 0 || index > ll.size {
            return fmt.Errorf("index out of bounds")
        }
        
        newNode := &Node{data: data}
        
        if index == 0 {
            newNode.next = ll.head
            ll.head = newNode
        } else {
            current := ll.head
            for i := 0; i < index-1; i++ {
                current = current.next
            }
            newNode.next = current.next
            current.next = newNode
        }
        ll.size++
        return nil
    }
    
    // Remove removes an item at a specific index
    func (ll *LinkedList) Remove(index int) (interface{}, error) {
        if index < 0 || index >= ll.size {
            return nil, fmt.Errorf("index out of bounds")
        }
        
        var data interface{}
        
        if index == 0 {
            data = ll.head.data
            ll.head = ll.head.next
        } else {
            current := ll.head
            for i := 0; i < index-1; i++ {
                current = current.next
            }
            data = current.next.data
            current.next = current.next.next
        }
        ll.size--
        return data, nil
    }
    
    // Get returns the item at a specific index
    func (ll *LinkedList) Get(index int) (interface{}, error) {
        if index < 0 || index >= ll.size {
            return nil, fmt.Errorf("index out of bounds")
        }
        
        current := ll.head
        for i := 0; i < index; i++ {
            current = current.next
        }
        return current.data, nil
    }
    
    // Size returns the number of items in the list
    func (ll *LinkedList) Size() int {
        return ll.size
    }
    
    // IsEmpty returns true if the list is empty
    func (ll *LinkedList) IsEmpty() bool {
        return ll.size == 0
    }
    
    // String returns a string representation of the list
    func (ll *LinkedList) String() string {
        if ll.IsEmpty() {
            return "LinkedList{}"
        }
        
        result := "LinkedList{"
        current := ll.head
        for current != nil {
            result += fmt.Sprintf("%v", current.data)
            if current.next != nil {
                result += " -> "
            }
            current = current.next
        }
        result += "}"
        return result
    }
    
    // Use the linked list
    list := NewLinkedList()
    
    // Add items
    list.Add("first")
    list.Add("second")
    list.Add("third")
    fmt.Printf("List after adding: %s\n", list)
    // Output: List after adding: LinkedList{first -> second -> third}
    
    // Add at specific index
    err := list.AddAt(1, "middle")
    if err != nil {
        fmt.Printf("Error: %v\n", err)
    } else {
        fmt.Printf("List after adding at index 1: %s\n", list)
    }
    // Output: List after adding at index 1: LinkedList{first -> middle -> second -> third}
    
    // Get item at index
    item, err := list.Get(2)
    if err != nil {
        fmt.Printf("Error: %v\n", err)
    } else {
        fmt.Printf("Item at index 2: %v\n", item)
    }
    // Output: Item at index 2: second
    
    // Remove item
    removed, err := list.Remove(1)
    if err != nil {
        fmt.Printf("Error: %v\n", err)
    } else {
        fmt.Printf("Removed item: %v\n", removed)
        fmt.Printf("List after removal: %s\n", list)
    }
    // Output:
    // Removed item: middle
    // List after removal: LinkedList{first -> second -> third}
    
    // Check size
    fmt.Printf("Size: %d\n", list.Size())
    // Output: Size: 3
}

Generic Data Structure Patterns​

Type-Safe Collections​

Generic Stack with Type Parameters​

Using Go's generics (Go 1.18+) for type-safe collections.

The any Type Alias​

The any type is an alias for interface{} in Go 1.18+.

package main

import "fmt"

func main() {
    // Generic data structure patterns examples
    fmt.Println("Generic data structure patterns examples:")
    
    // Generic Stack implementation (Go 1.18+)
    type GenericStack[T any] struct {
        items []T
    }
    
    // NewGenericStack creates a new generic stack
    func NewGenericStack[T any]() *GenericStack[T] {
        return &GenericStack[T]{
            items: make([]T, 0),
        }
    }
    
    // Push adds an item to the top of the stack
    func (s *GenericStack[T]) Push(item T) {
        s.items = append(s.items, item)
    }
    
    // Pop removes and returns the top item from the stack
    func (s *GenericStack[T]) Pop() (T, bool) {
        if s.IsEmpty() {
            var zero T
            return zero, false
        }
        
        index := len(s.items) - 1
        item := s.items[index]
        s.items = s.items[:index]
        return item, true
    }
    
    // Peek returns the top item without removing it
    func (s *GenericStack[T]) Peek() (T, bool) {
        if s.IsEmpty() {
            var zero T
            return zero, false
        }
        
        return s.items[len(s.items)-1], true
    }
    
    // IsEmpty returns true if the stack is empty
    func (s *GenericStack[T]) IsEmpty() bool {
        return len(s.items) == 0
    }
    
    // Size returns the number of items in the stack
    func (s *GenericStack[T]) Size() int {
        return len(s.items)
    }
    
    // String returns a string representation of the stack
    func (s *GenericStack[T]) String() string {
        return fmt.Sprintf("GenericStack{%v}", s.items)
    }
    
    // Use generic stack with integers
    intStack := NewGenericStack[int]()
    intStack.Push(1)
    intStack.Push(2)
    intStack.Push(3)
    fmt.Printf("Integer stack: %s\n", intStack)
    // Output: Integer stack: GenericStack{[1 2 3]}
    
    // Pop from integer stack
    if item, ok := intStack.Pop(); ok {
        fmt.Printf("Popped integer: %d\n", item)
    }
    // Output: Popped integer: 3
    
    // Use generic stack with strings
    stringStack := NewGenericStack[string]()
    stringStack.Push("hello")
    stringStack.Push("world")
    stringStack.Push("go")
    fmt.Printf("String stack: %s\n", stringStack)
    // Output: String stack: GenericStack{[hello world go]}
    
    // Pop from string stack
    if item, ok := stringStack.Pop(); ok {
        fmt.Printf("Popped string: %s\n", item)
    }
    // Output: Popped string: go
    
    // Use generic stack with custom types
    type Person struct {
        Name string
        Age  int
    }
    
    personStack := NewGenericStack[Person]()
    personStack.Push(Person{Name: "Alice", Age: 30})
    personStack.Push(Person{Name: "Bob", Age: 25})
    fmt.Printf("Person stack: %s\n", personStack)
    // Output: Person stack: GenericStack{[{Alice 30} {Bob 25}]}
    
    // Pop from person stack
    if person, ok := personStack.Pop(); ok {
        fmt.Printf("Popped person: %+v\n", person)
    }
    // Output: Popped person: {Name:Bob Age:25}
}

Generic Map with Constraints​

The comparable Constraint​

Using type constraints for generic map implementations.

Type Constraints and Bounds​

Implementing type-safe maps with proper constraints.

package main

import "fmt"

func main() {
    // Generic map with constraints examples
    fmt.Println("Generic map with constraints examples:")
    
    // Generic Set implementation with comparable constraint
    type GenericSet[T comparable] struct {
        items map[T]bool
    }
    
    // NewGenericSet creates a new generic set
    func NewGenericSet[T comparable]() *GenericSet[T] {
        return &GenericSet[T]{
            items: make(map[T]bool),
        }
    }
    
    // Add adds an item to the set
    func (s *GenericSet[T]) Add(item T) {
        s.items[item] = true
    }
    
    // Remove removes an item from the set
    func (s *GenericSet[T]) Remove(item T) {
        delete(s.items, item)
    }
    
    // Contains returns true if the item is in the set
    func (s *GenericSet[T]) Contains(item T) bool {
        return s.items[item]
    }
    
    // Size returns the number of items in the set
    func (s *GenericSet[T]) Size() int {
        return len(s.items)
    }
    
    // IsEmpty returns true if the set is empty
    func (s *GenericSet[T]) IsEmpty() bool {
        return len(s.items) == 0
    }
    
    // ToSlice returns a slice of all items in the set
    func (s *GenericSet[T]) ToSlice() []T {
        result := make([]T, 0, len(s.items))
        for item := range s.items {
            result = append(result, item)
        }
        return result
    }
    
    // String returns a string representation of the set
    func (s *GenericSet[T]) String() string {
        return fmt.Sprintf("GenericSet{%v}", s.ToSlice())
    }
    
    // Use generic set with integers
    intSet := NewGenericSet[int]()
    intSet.Add(1)
    intSet.Add(2)
    intSet.Add(3)
    intSet.Add(2) // Duplicate
    fmt.Printf("Integer set: %s\n", intSet)
    // Output: Integer set: GenericSet{[1 2 3]}
    
    // Check if set contains item
    fmt.Printf("Contains 2: %t\n", intSet.Contains(2))
    fmt.Printf("Contains 4: %t\n", intSet.Contains(4))
    // Output:
    // Contains 2: true
    // Contains 4: false
    
    // Use generic set with strings
    stringSet := NewGenericSet[string]()
    stringSet.Add("apple")
    stringSet.Add("banana")
    stringSet.Add("orange")
    stringSet.Add("apple") // Duplicate
    fmt.Printf("String set: %s\n", stringSet)
    // Output: String set: GenericSet{[apple banana orange]}
    
    // Remove item from set
    stringSet.Remove("banana")
    fmt.Printf("String set after removal: %s\n", stringSet)
    // Output: String set after removal: GenericSet{[apple orange]}
    
    // Use generic set with custom comparable types
    type Point struct {
        X, Y int
    }
    
    pointSet := NewGenericSet[Point]()
    pointSet.Add(Point{X: 1, Y: 2})
    pointSet.Add(Point{X: 3, Y: 4})
    pointSet.Add(Point{X: 1, Y: 2}) // Duplicate
    fmt.Printf("Point set: %s\n", pointSet)
    // Output: Point set: GenericSet{[{1 2} {3 4}]}
}

Complex Data Relationships​

Tree Data Structures​

Binary Tree Implementation​

Implementing a binary tree with proper node management.

Tree Traversal Algorithms​

Implementing depth-first and breadth-first traversal.

package main

import "fmt"

func main() {
    // Complex data relationships examples
    fmt.Println("Complex data relationships examples:")
    
    // Binary Tree Node
    type TreeNode struct {
        data  interface{}
        left  *TreeNode
        right *TreeNode
    }
    
    // Binary Tree
    type BinaryTree struct {
        root *TreeNode
    }
    
    // NewBinaryTree creates a new binary tree
    func NewBinaryTree() *BinaryTree {
        return &BinaryTree{}
    }
    
    // Insert inserts a value into the tree
    func (bt *BinaryTree) Insert(data interface{}) {
        if bt.root == nil {
            bt.root = &TreeNode{data: data}
        } else {
            bt.insertNode(bt.root, data)
        }
    }
    
    // insertNode inserts a value into the tree recursively
    func (bt *BinaryTree) insertNode(node *TreeNode, data interface{}) {
        // Simple insertion logic (for demonstration)
        // In a real implementation, you'd have proper comparison logic
        if node.left == nil {
            node.left = &TreeNode{data: data}
        } else if node.right == nil {
            node.right = &TreeNode{data: data}
        } else {
            // Insert into left subtree
            bt.insertNode(node.left, data)
        }
    }
    
    // InOrderTraversal performs in-order traversal
    func (bt *BinaryTree) InOrderTraversal() []interface{} {
        var result []interface{}
        bt.inOrderTraversal(bt.root, &result)
        return result
    }
    
    // inOrderTraversal performs in-order traversal recursively
    func (bt *BinaryTree) inOrderTraversal(node *TreeNode, result *[]interface{}) {
        if node != nil {
            bt.inOrderTraversal(node.left, result)
            *result = append(*result, node.data)
            bt.inOrderTraversal(node.right, result)
        }
    }
    
    // PreOrderTraversal performs pre-order traversal
    func (bt *BinaryTree) PreOrderTraversal() []interface{} {
        var result []interface{}
        bt.preOrderTraversal(bt.root, &result)
        return result
    }
    
    // preOrderTraversal performs pre-order traversal recursively
    func (bt *BinaryTree) preOrderTraversal(node *TreeNode, result *[]interface{}) {
        if node != nil {
            *result = append(*result, node.data)
            bt.preOrderTraversal(node.left, result)
            bt.preOrderTraversal(node.right, result)
        }
    }
    
    // PostOrderTraversal performs post-order traversal
    func (bt *BinaryTree) PostOrderTraversal() []interface{} {
        var result []interface{}
        bt.postOrderTraversal(bt.root, &result)
        return result
    }
    
    // postOrderTraversal performs post-order traversal recursively
    func (bt *BinaryTree) postOrderTraversal(node *TreeNode, result *[]interface{}) {
        if node != nil {
            bt.postOrderTraversal(node.left, result)
            bt.postOrderTraversal(node.right, result)
            *result = append(*result, node.data)
        }
    }
    
    // LevelOrderTraversal performs level-order (breadth-first) traversal
    func (bt *BinaryTree) LevelOrderTraversal() []interface{} {
        if bt.root == nil {
            return nil
        }
        
        var result []interface{}
        queue := []*TreeNode{bt.root}
        
        for len(queue) > 0 {
            node := queue[0]
            queue = queue[1:]
            
            result = append(result, node.data)
            
            if node.left != nil {
                queue = append(queue, node.left)
            }
            if node.right != nil {
                queue = append(queue, node.right)
            }
        }
        
        return result
    }
    
    // Use the binary tree
    tree := NewBinaryTree()
    
    // Insert values
    tree.Insert(1)
    tree.Insert(2)
    tree.Insert(3)
    tree.Insert(4)
    tree.Insert(5)
    
    // Perform traversals
    fmt.Printf("In-order traversal: %v\n", tree.InOrderTraversal())
    fmt.Printf("Pre-order traversal: %v\n", tree.PreOrderTraversal())
    fmt.Printf("Post-order traversal: %v\n", tree.PostOrderTraversal())
    fmt.Printf("Level-order traversal: %v\n", tree.LevelOrderTraversal())
    // Output:
    // In-order traversal: [4 2 1 3 5]
    // Pre-order traversal: [1 2 4 3 5]
    // Post-order traversal: [4 2 5 3 1]
    // Level-order traversal: [1 2 3 4 5]
}

Graph Data Structures​

Adjacency List Implementation​

Implementing a graph using adjacency lists.

Graph Traversal Algorithms​

Implementing depth-first and breadth-first search.

package main

import "fmt"

func main() {
    // Graph data structures examples
    fmt.Println("Graph data structures examples:")
    
    // Graph using adjacency list
    type Graph struct {
        vertices map[interface{}][]interface{}
    }
    
    // NewGraph creates a new graph
    func NewGraph() *Graph {
        return &Graph{
            vertices: make(map[interface{}][]interface{}),
        }
    }
    
    // AddVertex adds a vertex to the graph
    func (g *Graph) AddVertex(vertex interface{}) {
        if _, exists := g.vertices[vertex]; !exists {
            g.vertices[vertex] = make([]interface{}, 0)
        }
    }
    
    // AddEdge adds an edge between two vertices
    func (g *Graph) AddEdge(from, to interface{}) {
        g.AddVertex(from)
        g.AddVertex(to)
        
        g.vertices[from] = append(g.vertices[from], to)
        // For undirected graph, also add reverse edge
        g.vertices[to] = append(g.vertices[to], from)
    }
    
    // GetNeighbors returns the neighbors of a vertex
    func (g *Graph) GetNeighbors(vertex interface{}) []interface{} {
        return g.vertices[vertex]
    }
    
    // GetVertices returns all vertices in the graph
    func (g *Graph) GetVertices() []interface{} {
        vertices := make([]interface{}, 0, len(g.vertices))
        for vertex := range g.vertices {
            vertices = append(vertices, vertex)
        }
        return vertices
    }
    
    // DFS performs depth-first search starting from a vertex
    func (g *Graph) DFS(start interface{}) []interface{} {
        visited := make(map[interface{}]bool)
        var result []interface{}
        
        g.dfs(start, visited, &result)
        return result
    }
    
    // dfs performs depth-first search recursively
    func (g *Graph) dfs(vertex interface{}, visited map[interface{}]bool, result *[]interface{}) {
        if visited[vertex] {
            return
        }
        
        visited[vertex] = true
        *result = append(*result, vertex)
        
        for _, neighbor := range g.vertices[vertex] {
            g.dfs(neighbor, visited, result)
        }
    }
    
    // BFS performs breadth-first search starting from a vertex
    func (g *Graph) BFS(start interface{}) []interface{} {
        visited := make(map[interface{}]bool)
        var result []interface{}
        queue := []interface{}{start}
        
        for len(queue) > 0 {
            vertex := queue[0]
            queue = queue[1:]
            
            if !visited[vertex] {
                visited[vertex] = true
                result = append(result, vertex)
                
                for _, neighbor := range g.vertices[vertex] {
                    if !visited[neighbor] {
                        queue = append(queue, neighbor)
                    }
                }
            }
        }
        
        return result
    }
    
    // String returns a string representation of the graph
    func (g *Graph) String() string {
        result := "Graph{\n"
        for vertex, neighbors := range g.vertices {
            result += fmt.Sprintf("  %v: %v\n", vertex, neighbors)
        }
        result += "}"
        return result
    }
    
    // Use the graph
    graph := NewGraph()
    
    // Add edges
    graph.AddEdge("A", "B")
    graph.AddEdge("A", "C")
    graph.AddEdge("B", "D")
    graph.AddEdge("C", "D")
    graph.AddEdge("D", "E")
    
    fmt.Printf("Graph: %s\n", graph)
    // Output:
    // Graph{
    //   A: [B C]
    //   B: [A D]
    //   C: [A D]
    //   D: [B C E]
    //   E: [D]
    // }
    
    // Perform traversals
    fmt.Printf("DFS from A: %v\n", graph.DFS("A"))
    fmt.Printf("BFS from A: %v\n", graph.BFS("A"))
    // Output:
    // DFS from A: [A B D C E]
    // BFS from A: [A B C D E]
    
    // Get neighbors
    fmt.Printf("Neighbors of D: %v\n", graph.GetNeighbors("D"))
    // Output: Neighbors of D: [B C E]
}

Performance Optimization Techniques​

Memory Pool Patterns​

Object Pool Implementation​

Implementing object pools for memory efficiency.

Buffer Pool Management​

Managing buffers efficiently to reduce allocations.

package main

import "fmt"

func main() {
    // Performance optimization techniques examples
    fmt.Println("Performance optimization techniques examples:")
    
    // Object Pool implementation
    type ObjectPool struct {
        pool chan interface{}
        new  func() interface{}
    }
    
    // NewObjectPool creates a new object pool
    func NewObjectPool(size int, newFunc func() interface{}) *ObjectPool {
        return &ObjectPool{
            pool: make(chan interface{}, size),
            new:  newFunc,
        }
    }
    
    // Get gets an object from the pool
    func (op *ObjectPool) Get() interface{} {
        select {
        case obj := <-op.pool:
            return obj
        default:
            return op.new()
        }
    }
    
    // Put puts an object back into the pool
    func (op *ObjectPool) Put(obj interface{}) {
        select {
        case op.pool <- obj:
        default:
            // Pool is full, discard the object
        }
    }
    
    // Use object pool
    pool := NewObjectPool(10, func() interface{} {
        return make([]byte, 1024)
    })
    
    // Get buffer from pool
    buffer1 := pool.Get().([]byte)
    buffer2 := pool.Get().([]byte)
    
    fmt.Printf("Got buffer 1: %d bytes\n", len(buffer1))
    fmt.Printf("Got buffer 2: %d bytes\n", len(buffer2))
    // Output:
    // Got buffer 1: 1024 bytes
    // Got buffer 2: 1024 bytes
    
    // Put buffers back to pool
    pool.Put(buffer1)
    pool.Put(buffer2)
    
    // Get buffer from pool again (should reuse)
    buffer3 := pool.Get().([]byte)
    fmt.Printf("Got buffer 3: %d bytes\n", len(buffer3))
    // Output: Got buffer 3: 1024 bytes
    
    // Ring Buffer implementation
    type RingBuffer struct {
        buffer []interface{}
        head   int
        tail   int
        size   int
    }
    
    // NewRingBuffer creates a new ring buffer
    func NewRingBuffer(capacity int) *RingBuffer {
        return &RingBuffer{
            buffer: make([]interface{}, capacity),
            head:   0,
            tail:   0,
            size:   0,
        }
    }
    
    // Enqueue adds an item to the ring buffer
    func (rb *RingBuffer) Enqueue(item interface{}) bool {
        if rb.size == len(rb.buffer) {
            return false // Buffer is full
        }
        
        rb.buffer[rb.tail] = item
        rb.tail = (rb.tail + 1) % len(rb.buffer)
        rb.size++
        return true
    }
    
    // Dequeue removes an item from the ring buffer
    func (rb *RingBuffer) Dequeue() (interface{}, bool) {
        if rb.size == 0 {
            return nil, false // Buffer is empty
        }
        
        item := rb.buffer[rb.head]
        rb.head = (rb.head + 1) % len(rb.buffer)
        rb.size--
        return item, true
    }
    
    // Size returns the number of items in the buffer
    func (rb *RingBuffer) Size() int {
        return rb.size
    }
    
    // IsFull returns true if the buffer is full
    func (rb *RingBuffer) IsFull() bool {
        return rb.size == len(rb.buffer)
    }
    
    // IsEmpty returns true if the buffer is empty
    func (rb *RingBuffer) IsEmpty() bool {
        return rb.size == 0
    }
    
    // Use ring buffer
    ringBuffer := NewRingBuffer(3)
    
    // Enqueue items
    ringBuffer.Enqueue("first")
    ringBuffer.Enqueue("second")
    ringBuffer.Enqueue("third")
    
    fmt.Printf("Ring buffer size: %d\n", ringBuffer.Size())
    fmt.Printf("Is full: %t\n", ringBuffer.IsFull())
    // Output:
    // Ring buffer size: 3
    // Is full: true
    
    // Try to enqueue when full
    success := ringBuffer.Enqueue("fourth")
    fmt.Printf("Enqueue when full: %t\n", success)
    // Output: Enqueue when full: false
    
    // Dequeue items
    if item, ok := ringBuffer.Dequeue(); ok {
        fmt.Printf("Dequeued: %v\n", item)
    }
    
    fmt.Printf("Ring buffer size after dequeue: %d\n", ringBuffer.Size())
    // Output:
    // Dequeued: first
    // Ring buffer size after dequeue: 2
    
    // Enqueue after dequeue
    ringBuffer.Enqueue("fourth")
    fmt.Printf("Ring buffer size after enqueue: %d\n", ringBuffer.Size())
    // Output: Ring buffer size after enqueue: 3
}

What You've Learned​

Congratulations! You now have a comprehensive understanding of Go's advanced data structures:

Custom Collection Implementations​

  • Understanding and implementing stacks, queues, and linked lists
  • Working with generic data structures using Go's type system
  • Implementing type-safe collections with proper error handling
  • Understanding memory management in custom collections

Generic Data Structure Patterns​

  • Using Go's generics for type-safe implementations
  • Implementing generic stacks, sets, and maps
  • Understanding type constraints and bounds
  • Creating reusable data structure implementations

Complex Data Relationships​

  • Implementing tree data structures with proper traversal
  • Working with graph data structures and algorithms
  • Understanding adjacency lists and traversal algorithms
  • Implementing depth-first and breadth-first search

Performance Optimization Techniques​

  • Implementing object pools for memory efficiency
  • Creating ring buffers for circular data structures
  • Understanding memory management patterns
  • Optimizing data structure performance

Key Concepts​

  • Custom types - Creating specialized data structures
  • Generics - Type-safe generic implementations
  • Memory management - Efficient memory usage patterns
  • Algorithms - Implementing traversal and search algorithms

Next Steps​

You now have a solid foundation in Go's advanced data structures. In the next chapter, we'll explore Go's object-oriented programming features, including methods, interfaces, and composition patterns.

Understanding advanced data structures is crucial for building high-performance applications and solving complex problems. These concepts form the foundation for all the more advanced programming techniques we'll cover in the coming chapters.

Ready to learn about object-oriented programming? Let's explore Go's object-oriented features and learn how to build sophisticated software architectures!