Learn Data Structures and Algorithms with Golang

Learn Data Structures and Algorithms with Golang

by Bhagvan Kommadi
Released March 2019
Publisher(s): Packt Publishing
ISBN: 9781789618501

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Explore Golang's data structures and algorithms to design, implement, and analyze code in the professional setting

Key Features

  • Learn the basics of data structures and algorithms and implement them efficiently
  • Use data structures such as arrays, stacks, trees, lists and graphs in real-world scenarios
  • Compare the complexity of different algorithms and data structures for improved code performance

Book Description

Golang is one of the fastest growing programming languages in the software industry. Its speed, simplicity, and reliability make it the perfect choice for building robust applications. This brings the need to have a solid foundation in data structures and algorithms with Go so as to build scalable applications. Complete with hands-on tutorials, this book will guide you in using the best data structures and algorithms for problem solving.

The book begins with an introduction to Go data structures and algorithms. You'll learn how to store data using linked lists, arrays, stacks, and queues. Moving ahead, you'll discover how to implement sorting and searching algorithms, followed by binary search trees. This book will also help you improve the performance of your applications by stringing data types and implementing hash structures in algorithm design. Finally, you'll be able to apply traditional data structures to solve real-world problems.

By the end of the book, you'll have become adept at implementing classic data structures and algorithms in Go, propelling you to become a confident Go programmer.

What you will learn

  • Improve application performance using the most suitable data structure and algorithm
  • Explore the wide range of classic algorithms such as recursion and hashing algorithms
  • Work with algorithms such as garbage collection for efficient memory management
  • Analyze the cost and benefit trade-off to identify algorithms and data structures for problem solving
  • Explore techniques for writing pseudocode algorithm and ace whiteboard coding in interviews
  • Discover the pitfalls in selecting data structures and algorithms by predicting their speed and efficiency

Who this book is for

This book is for developers who want to understand how to select the best data structures and algorithms that will help solve coding problems. Basic Go programming experience will be an added advantage.

Table of contents

  1. Title Page
  2. Copyright and Credits
    1. Learn Data Structures and Algorithms with Golang
  3. About Packt
    1. Why subscribe?
    2. Packt.com
  4. Contributors
    1. About the author
    2. About the reviewer
    3. Packt is searching for authors like you
  5. Preface
    1. Who this book is for
    2. What this book covers
    3. To get the most out of this book
      1. Download the example code files
      2. Download the color images
      3. Conventions used
    4. Get in touch
      1. Reviews
  6. Section 1: Introduction to Data Structures and Algorithms and the Go Language
  7. Data Structures and Algorithms
    1. Technical requirements
    2. Classification of data structures and structural design patterns
      1. Classification of data structures
        1. Lists
        2. Tuples
        3. Heaps
      2. Structural design patterns
        1. Adapter
        2. Bridge
          1. drawShape method
          2. drawContour method
        3. Composite
        4. Decorator
        5. Facade
        6. Flyweight
        7. Private class data
        8. Proxy
    3. Representation of algorithms
      1. Flow chart
      2. Pseudo code
    4. Complexity and performance analysis
      1. Complexity analysis of algorithms
        1. Big O notation
        2. Linear complexity
        3. Quadratic complexity
        4. Cubic complexity
        5. Logarithmic complexity
    5. Brute force algorithms
    6. Divide and conquer algorithms
    7. Backtracking algorithms
    8. Summary
    9. Questions and exercises
    10. Further reading
  8. Getting Started with Go for Data Structures and Algorithms
    1. Technical requirements
    2. Arrays
    3. Slices
      1. The len function
      2. Slice function
    4. Two-dimensional slices
    5. Maps
    6. Database operations
      1. The GetCustomer method
      2. The InsertCustomer method
    7. Variadic functions
      1. The update operation
      2. The delete operation
    8. CRUD web forms
      1. The defer and panic statements
        1. The InsertCustomer method
        2. The UpdateCustomer method
        3. The DeleteCustomer method
      2. CRM web application
        1. The Create function
        2. The Insert function
        3. The Alter function
        4. The Update function
        5. The Delete function
        6. The main method
      3. The Header template
      4. The Footer template
      5. The Menu template
      6. The Create template
      7. The Update template
      8. The View template
    9. Summary
    10. Questions
    11. Further reading
  9. Section 2: Basic Data Structures and Algorithms using Go
  10. Linear Data Structures
    1. Technical requirements
    2. Lists
      1. LinkedList
        1. The Node class
        2. The LinkedList class
          1. The AddToHead method
          2. The IterateList method
          3. The LastNode method
          4. The AddToEnd method
          5. The NodeWithValue method
          6. The AddAfter method
          7. The main method
      2. Doubly linked list
        1. The NodeBetweenValues method
        2. The AddToHead method
        3. AddAfter method
        4. The AddToEnd method
        5. The main method
    3. Sets
      1. The AddElement method
      2. The DeleteElement method
      3. The ContainsElement method
      4. The main method – contains element
      5. The InterSect method
      6. The Union method
      7. The main method – intersection and union
    4. Tuples
    5. Queues
      1. The New method
      2. The Add method
      3. The main method – queues
      4. Synchronized queue
        1. The New method
        2. The StartTicketIssue method
        3. The EndTicketIssue method
        4. The ticketIssue method
        5. The StartPass method
        6. The EndPass method
        7. The passenger method
        8. The main method
    6. Stacks
      1. The New method
      2. The Push method
      3. The Pop method
      4. The main method
    7. Summary
    8. Questions
    9. Further reading
  11. Non-Linear Data Structures
    1. Technical requirements
    2. Trees
      1. Binary search tree
        1. The BinarySearchTree class
          1. The InsertElement method
          2. The insertTreeNode method
          3. The inOrderTraverse method
          4. The inOrderTraverseTree method
          5. The PreOrderTraverseTree method
          6. The preOrderTraverseTree method
          7. The PostOrderTraverseTree method
          8. The postOrderTraverseTree method
          9. The MinNode method
          10. The MaxNode method
          11. The SearchNode method
          12. The searchNode method
          13. The RemoveNode method
          14. The removeNode method
          15. The String method
          16. The stringify method
          17. The main method
      2. Adelson, Velski, and Landis (AVL) tree
        1. The KeyValue interface
        2. The TreeNode class
          1. The opposite method
          2. The singleRotation method
          3. The doubleRotation method
          4. The adjustBalance method
          5. The BalanceTree method
          6. The insertRNode method
          7. The InsertNode method
          8. The RemoveNode method
          9. The removeBalance method
          10. The removeRNode method
          11. The main method
      3. B+ tree
      4. B-tree
      5. T-tree
    3. Tables
      1. The Table class
      2. The Row class
      3. The Column class
      4. The printTable method
      5. The main method
    4. Symbol tables
    5. Containers
      1. Circular linked list
    6. The hash functions
    7. Summary
    8. Questions
    9. Further reading
  12. Homogeneous Data Structures
    1. Technical requirements
    2. Two-dimensional arrays
      1. Row matrix
      2. Column matrix
      3. Lower triangular matrix
      4. Upper triangular matrix
      5. Null matrix
      6. Identity matrix
      7. Symmetric matrix
      8. Basic 2D matrix operations
        1. The add method
        2. The subtract method
        3. The multiply method
        4. The transpose method
        5. The determinant method
        6. The inverse method
      9. Zig-zag matrix
      10. Spiral matrix
      11. Boolean matrix
        1. The printMatrix method
        2. The main method
    3. Multi-dimensional arrays
      1. Tensors
    4. Summary
    5. Questions
    6. Further reading
  13. Heterogeneous Data Structures
    1. Technical requirements
    2. Linked lists
      1. Singly linked lists
        1. The CreateLinkedList method
        2. The ReverseLinkedList method
        3. The main method
      2. Doubly linked lists
      3. Circular-linked lists
        1. The CircularQueue class
          1. The NewQueue method
          2. The IsUnUsed method
          3. The IsComplete method
          4. The Add method
          5. The MoveOneStep method
          6. The main method
    3. Ordered lists
      1. The ToString method
      2. The SortByAge type
      3. The Thing class
        1. The ByFactor function type
          1. The Sort method
      4. Thing sorter class
        1. The len, swap, and less methods
        2. The main method
      5. The struct type
        1. The multiSorter class
          1. The Sort method
          2. The OrderBy method
          3. The len method
          4. The Swap method
          5. The less method
          6. The main method
    4. Unordered lists
      1. The UnOrderedList class
        1. The AddtoHead method
        2. The IterateList method
        3. The main method
    5. Summary
    6. Questions
    7. Further reading
  14. Dynamic Data Structures
    1. Technical requirements
    2. Dictionaries
      1. DictVal type
      2. Dictionary class
        1. Put method
        2. Remove method
        3. Contains method
        4. Find method
        5. Reset method
        6. NumberOfElements method
        7. GetKeys method
        8. GetValues method
        9. The main method
    3. TreeSets
      1. InsertTreeNode method
      2. Delete method
      3. InOrderTraverseTree method
      4. The inOrderTraverseTree method
      5. PreOrderTraverseTree method
      6. The preOrderTraverseTree method
      7. Search method
      8. The String method
      9. The main method
      10. Synchronized TreeSets
      11. Mutable TreeSets
        1. RemoveNode method
        2. Treeset.bst
    4. Sequences
      1. Farey sequence
        1. String method
        2. The g method
        3. The main method
      2. Fibonacci sequence
        1. FibonacciNumber method
        2. Main method
      3. Look-and-say
      4. Thue–Morse
    5. Summary
    6. Questions
    7. Further reading
  15. Classic Algorithms
    1. Technical requirements
    2. Sorting
      1. Bubble
      2. Selection
        1. The swap method
        2. The main method
      3. Insertion
        1. InsertionSorter method
        2. The main method
      4. Shell
        1. The power method
        2. The main method
      5. Merge
        1. MergeSorter method
        2. JoinArrays method
        3. The main method
      6. Quick
        1. The divideParts method
        2. The swap method
        3. The main method
    3. Searching
      1. Linear
      2. Binary
      3. Interpolation
    4. Recursion
    5. Hashing
      1. The CreateHashMutliple method
      2. The XOR method
      3. The main method
    6. Summary
    7. Questions
    8. Further reading
  16. Section 3: Advanced Data Structures and Algorithms using Go
  17. Network and Sparse Matrix Representation
    1. Technical requirements
    2. Network representation using graphs
      1. The Link class
        1. The NewSocialGraph method
        2. The AddLink method
        3. The PrintLinks method
        4. The main method
        5. Test
      2. Representing a social network
        1. The NewSocialGraph method
        2. The AddEntity method
        3. The AddLink method
        4. The PrintLinks method
        5. The main method
      3. Map layouts
        1. The MapLayout class
          1. The NewMapLayout method
          2. The AddPlace method
          3. The AddLink method
          4. The PrintLinks method
          5. The main method
          6. Test
      4. Knowledge graphs
        1. The KnowledgeGraph class
          1. The NewKnowledgeGraph method
          2. The AddClass method
          3. The AddLink method
          4. The PrintLinks method
          5. The main method
          6. Test
    3. Sparse matrix representation using a list of lists
      1. SparseMatrix class
        1. The Shape method
        2. The NumNonZero method
        3. The LessThan method
        4. The Equal method
        5. The GetValue method
        6. The SetValue method
        7. The NewSparseMatrix method
        8. The main method
    4. Summary
    5. Questions
    6. Further reading
  18. Memory Management
    1. Technical requirements
    2. Garbage collection
      1. The ReferenceCounter class
        1. The newReferenceCounter method
      2. The Stack class
        1. The Stack class – a new method
        2. The main method
      3. Reference counting
        1. Simple reference counting
        2. Deferred reference counting
        3. One-bit reference counting
        4. Weighted reference counting
      4. The mark-and-sweep algorithm
      5. The generational collection algorithm
    3. Cache management
      1. The CacheObject class
        1. The IfExpired method
      2. The Cache class
        1. The NewCache method
        2. The GetObject method
        3. The SetValue method
      3. The main method
    4. Space allocation
      1. Pointers
        1. The addOne method
        2. The main method
    5. Concepts – Go memory management
      1. Profiling
    6. Summary
    7. Questions
    8. Further reading
  19. Next Steps
    1. Technical requirements
    2. Learning outcomes
      1. Key takeaways
      2. Next steps
        1. Chapter 1 – Data Structures and Algorithms
        2. Chapter 2 – Getting Started with Go for Data Structures and Algorithms
        3. Chapter 3 – Linear Data Structures
        4. Chapter 4 – Non-Linear Data Structures
        5. Chapter 5 – Homogeneous Data Structures
        6. Chapter 6 – Heterogeneous Data Structures
        7. Chapter 7 – Dynamic Data Structures
        8. Chapter 8 – Classic Algorithms
        9. Chapter 9 – Network and Sparse Matrix Representation
        10. Chapter 10 – Memory Management
      3. Tips and techniques
        1. Using channel with a timeout interval
        2. Using context instead of channel
        3. Logging with the line number
        4. Go tool usage
        5. Go environment variables
        6. Test table
        7. Importing packages
        8. Panic, defer, and recover
  20. Other Books You May Enjoy
    1. Leave a review - let other readers know what you think

Product information

  • Title: Learn Data Structures and Algorithms with Golang
  • Author(s): Bhagvan Kommadi
  • Release date: March 2019
  • Publisher(s): Packt Publishing
  • ISBN: 9781789618501