Data Structures and Algorithms implementation in Go

Overview

Data Structures and Algorithms

Go Report Card Build Status License

Clean and simple implementation in Go

Implementation

There are several data structures and algorithms implemented in this project. The list will be replenished with time.

Data structures
  • Circular Buffer
  • Linked List
  • Doubly Linked List
  • Stack
  • Queue
  • Binary Tree
  • Hash Table
  • Trie
Searching algorithms
  • Linear Search
  • Binary Search
  • Jump Search
  • Interpolation Search
  • Exponential Search
  • Ternary Search
String searching algorithms
  • Naive String Search
  • Rabin-Karp Algorithm
Sorting algorithms
  • Selection Sort
  • Insertion Sort
  • Bubble Sort
  • Comb Sort
  • Cocktail Sort
  • Gnome Sort
  • Merge Sort

Usage

The library is not intended for direct use by importing. We strongly recommend copying the necessary implementations and adjusting to your case.

You can download the source using go get command:

go get github.com/floyernick/Data-Structures-and-Algorithms

Don't forget about proverb:

A little copying is better than a little dependency.

Contribute

We would be happy to receive your propositions of improvement! Read Contributing Guide for more details.

License

This project is licensed under the MIT License.

Authors

Mykyta Paliienko - GitHub profile

Comments
  • Binary search test polishing

    Binary search test polishing

    • Use "sort.Slice" for sorting.

    No need to write you own algorithm (unless you want to write tests for it too)

    • TableDriven test instead of random generator.

    Testing randomly generated slice by iterating over its elements is a strange idea. You will obviously get the expected result - you can't suddenly find something that wasn't already there or miss something that was.

    • Formatted Error message.

    You should provide some usefull info about the error. And "Fatal" has a different use case.

    opened by konart 2
  • Make repo go get-able by adding a .go file to top folder level

    Make repo go get-able by adding a .go file to top folder level

    You need to make the top level of the repo a Go package in order to make it go get-able. Otherwise, it returns an error:

    package github.com/floyernick/Data-Structures-and-Algorithms: no Go files in /Users/philip/src/github.com/floyernick/Data-Structures-and-Algorithms
    

    It can as simple as a package declaration and it will work, i.e. in new file dsa.go at the top level of the package, just have a single line of package dsa and you're good to go.

    opened by philipithomas 1
  • Flaky test

    Flaky test

    https://github.com/floyernick/Data-Structures-and-Algorithms/blob/6ae8c0f2e09c371f47f2a3c76f3b73989e4f3c45/BinarySearch/BinarySearch_test.go#L21

    • This line could generate the number 0 in which case it would pass without making any verifications. suggest you add 10 to get some numbers.
    opened by cdluv 1
  • Update MergeSort.go

    Update MergeSort.go

    make it faster than before

    Benchmark_MergeSort_new-12 10 102711316 ns/op Benchmark_MergeSort_new-12 10 102242814 ns/op Benchmark_MergeSort_new-12 10 104988258 ns/op Benchmark_MergeSort_old-12 3 338513872 ns/op Benchmark_MergeSort_old-12 4 334441485 ns/op Benchmark_MergeSort_old-12 3 334280000 ns/op

    opened by Ccheers 0
  • Implement MergeSort more concisely

    Implement MergeSort more concisely

    This version reslices the left and right arrays instead of passing around array indices. This feels like more idiomatic Go to me, but it might not follow the textbook version of mergesort as closely as the old version.

    opened by lukechampine 0
  • Items in README.md should be linked

    Items in README.md should be linked

    Data Structures and Algorithms

    Go Report Card Build Status License

    Clean and simple implementation in Go

    Implementation

    There are several data structures and algorithms implemented in this project. The list will be replenished with time.

    Data structures
    opened by nskrkmz 1
  • Some Changes for MergeSort

    Some Changes for MergeSort

    #18 It Make MergeSort faster than before and I Commit a pull request. ———————————————————————————————————— Benchmark_MergeSort_new Benchmark_MergeSort_new-12 10 101394033 ns/op 209956300 B/op 1000041 allocs/op Benchmark_MergeSort_new-12 10 103156080 ns/op 209956320 B/op 1000041 allocs/op Benchmark_MergeSort_new-12 10 105631558 ns/op 209956272 B/op 1000041 allocs/op Benchmark_MergeSort_old Benchmark_MergeSort_old-12 4 322263281 ns/op 582174710 B/op 4052123 allocs/op Benchmark_MergeSort_old-12 3 333629871 ns/op 582175192 B/op 4052124 allocs/op Benchmark_MergeSort_old-12 3 350259903 ns/op 582174706 B/op 4052122 allocs/op

    opened by Ccheers 0
  • Optimize GetLast() in DoublyLinkedList

    Optimize GetLast() in DoublyLinkedList

    The GetLast() function traverses through the entire LL to get to the last pointer, when there's already a tail node. The fix gets rid of the traversal and returns the tail node value.

    func (list *LinkedList) GetLast() (int, bool) {
    	if list.head == nil {
    		return 0, false
    	}
    	return list.tail.data, true
    }
    
    opened by sammychien 0
  • Question on Exponential Search

    Question on Exponential Search

    Why do you add 1 to the boundValue here https://github.com/floyernick/Data-Structures-and-Algorithms/blob/master/ExponentialSearch/ExponentialSearch.go#L11 in the exponential search algorithm?

    After trying a test case where I search for an element that is not in the data slice I get an error panic: runtime error: index out of range. I'm not sure why a +1 was added but when I remove it the problem goes away.

    All of my code:

    package main
    
    import "fmt"
    
    func exponential_search(data []int, key int) int {
      bound_value := 1
      for bound_value < len(data) && data[bound_value] < key {
        bound_value *= 2
      }
      if bound_value > len(data) {
        bound_value = len(data) - 1
      }
      return binary_search(data, bound_value, key)
    }
    
    func binary_search(data []int, bound int, key int) int {
      min := 0
      max := bound
    
      for min <= max {
        mid := int((max + min) / 2)
        if data[mid] == key {
          return mid
        } else if data[mid] < key {
          min = mid + 1
        } else if data[mid] > key {
          max = mid - 1
        }
      }
      return -1
    }
    
    func main() {
      data1 := []int{0,1,2,3,4,5,6,7,8,9}
      data2 := []int{}
    
      keys := []int{0,4,9,11,2,3,8,-1}
    
      for _, key := range keys {
        fmt.Println("Searching for", key)
        if index := exponential_search(data1, key); index != -1 {
          fmt.Println("Position:", index, "data:", data1[index])
        } else {
          fmt.Println("Key", key, "not found")
        }
      }
      // Search for an element in an empty slice.
      fmt.Println("Position:", exponential_search(data2, 11))
    }
    

    Output:

    Searching for 0
    Position: 0 data: 0
    Searching for 4
    Position: 4 data: 4
    Searching for 9
    Position: 9 data: 9
    Searching for 11
    Key 11 not found
    Searching for 2
    Position: 2 data: 2
    Searching for 3
    Position: 3 data: 3
    Searching for 8
    Position: 8 data: 8
    Searching for -1
    Key -1 not found
    Position: -1
    
    opened by mrmcmuffinz 0
Owner
Mykyta Paliienko
Backend Engineer
Mykyta Paliienko
Data Structures and Algorithms implementation in Go

Data Structures and Algorithms Clean and simple implementation in Go Implementation There are several data structures and algorithms implemented in th

Mykyta Paliienko 2.5k Sep 23, 2022
Graph algorithms and data structures

Your basic graph Golang library of basic graph algorithms Topological ordering, image by David Eppstein, CC0 1.0. This library offers efficient and we

Algorithms to Go 580 Sep 27, 2022
Graph algorithms and data structures

Your basic graph Golang library of basic graph algorithms Topological ordering, image by David Eppstein, CC0 1.0. This library offers efficient and we

Algorithms to Go 9 Jan 25, 2021
Algorithms and Data Structures Solved in Golang

Algorithms and Data Structures Solved in Golang Hi! I'm Bruno Melo and this repository contains a lot challenges solved on many plataforms using go as

Bruno Melo 3 Aug 13, 2022
Some data structures and algorithms using golang

Some data structures and algorithms using golang

null 62 Aug 13, 2022
Practice-dsa-go - Data Structures and Algorithms for Interview Preparation in Go

Data Structures and Algorithms for Interview Preparation in Go Data Structures K

Sparsh Srivastava 2 Jul 3, 2022
Data Structures & Algorithms in Go

Data Structures and Algorithms with Go The aim of this repository is to provide Gophers with how data structures and algorithms are implemented in the

Chris Gonzalez 0 Dec 28, 2021
Grokking-algorithms-go - Solutions to common Data Structures problems

This is a repository dedicated to study, learn and solve Data Structure algorith

Gabriel Magalhães 0 Apr 4, 2022
Golang string comparison and edit distance algorithms library, featuring : Levenshtein, LCS, Hamming, Damerau levenshtein (OSA and Adjacent transpositions algorithms), Jaro-Winkler, Cosine, etc...

Go-edlib : Edit distance and string comparison library Golang string comparison and edit distance algorithms library featuring : Levenshtein, LCS, Ham

Hugo Bollon 361 Sep 27, 2022
Go translations of the algorithms and clients in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Overview Go translations of the Java source code for the algorithms and clients in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin

youngzy 168 Jun 30, 2022
Basic Implementation of Data-structures in Go

Data structures in Go v1.15.6 This repo consists the implementation of the following: Stacks Queues Linked Lists (Singly) Binary Search Trees Heaps (M

Shehab Abdel-Salam 4 May 24, 2021
Data Structure Libraries and Algorithms implementation

Algorithms Data Structure Libraries and Algorithms implementation in C++ Disclaimer This repository is meant to be used as a reference to learn data s

Priyank Chheda 640 Sep 17, 2022
Tutorial code for my video Learn to Use Basic Data Structures - Slices, Structs and Maps in Golang

Learn to Use Basic Data Structures - Slices, Structs and Maps in Golang Read text from a file and split into words. Introduction to slices / lists. Co

null 0 Jan 26, 2022
A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

dreamersdw 19 Mar 17, 2022
Probabilistic data structures for processing continuous, unbounded streams.

Boom Filters Boom Filters are probabilistic data structures for processing continuous, unbounded streams. This includes Stable Bloom Filters, Scalable

Tyler Treat 1.5k Sep 24, 2022
This is the course materials for the Go Data Structures Crash Course!

Go Data Structures Course ?? Welcome Gophers! This is the official repository that contains all of the data structures we cover in the Go Data Structu

TutorialEdge 9 May 10, 2022
Concurrent data structures for Go

xsync Concurrent data structures for Go. An extension for the standard sync package. This library should be considered experimental, so make sure to r

Andrey Pechkurov 262 Sep 22, 2022
Data Structures in Go: Hash Table

Data Structures in Go: Hash Table he time has come to implement one of the most commonly used data structures in software development - the Hash Table

Milad Samani 3 Oct 20, 2021