Data Structures With Go

array.go

package array

// SearchArray is a wrapper to array for searching
type SearchArray []interface{}

// Search searches an element in the array and returns its index
func (s SearchArray) Search(el interface{}) int {
	for i, e := range s {
		if e == el {
			return i
		}
	}
	return -1
}

bfs.go

func (t *Tree) BFS(f func(*Tree)) {
	q := queue.Queue{}
	q.Enqueue(t)
	for !q.Empty() {
		next := q.Dequeue()
		nextNode := next.(*Tree)
		f(nextNode)
		if len(nextNode.child) > 0 {
			for _, child := range nextNode.child {
				q.Enqueue(child)
			}
		}
	}
}

bfs1.go

	t.BFS(func(c *Tree) {
		fmt.Println(c.el)
	})

dfs.go

func (t *Tree) DFS(f func(*Tree)) {
	f(t)
	if len(t.child) > 0 {
		for _, c := range t.child {
			c.DFS(f)
		}
	}
}

dfs1.go

	t.DFS(func(c *Tree) {
		fmt.Println(c.el)
	})

graph1.go

package graph

import (
	"fmt"
	"strings"
)

// Node element to keep element and next node together
type Node struct {
	value interface{}
}

// Graph is the structure that contains nodes and edges
type Graph struct {
	nodes []*Node
	edges map[Node][]*Node
}

// NewGraph returns a new empty graph
func NewGraph() *Graph {
	return &Graph{
		nodes: make([]*Node, 0),
		edges: make(map[Node][]*Node),
	}
}

graph2.go

// AddNode inserts a new node in the graph
func (g *Graph) AddNode(el interface{}) *Node {
	n := &Node{el}
	g.nodes = append(g.nodes, n)
	return n
}

// AddEdge inserts a new edge in the graph
func (g *Graph) AddEdge(n1, n2 *Node) {
	g.edges[*n1] = append(g.edges[*n1], n2)
	g.edges[*n2] = append(g.edges[*n2], n1)
}

graph3.go

// String returns a string reperesentation of the node
func (n Node) String() string {
	return fmt.Sprintf("%v", n.value)
}

// String returns a string representation of the graph
func (g Graph) String() string {
	sb := strings.Builder{}
	for _, v := range g.nodes {
		sb.WriteString(v.String())
		sb.WriteString(" -> [ ")
		neighbors := g.edges[*v]
		for _, u := range neighbors {
			sb.WriteString(u.String())
			sb.WriteString(" ")
		}
		sb.WriteString("]\n")
	}
	return sb.String()

graph4.go

	g := NewGraph()
	nA := g.AddNode("a")
	nB := g.AddNode("b")
	nC := g.AddNode("c")
	nD := g.AddNode("d")
	nE := g.AddNode("e")

	g.AddEdge(nA, nB)
	g.AddEdge(nA, nC)
	g.AddEdge(nA, nE)
	g.AddEdge(nC, nD)
	g.AddEdge(nD, nE)

	fmt.Print(g.String())

linked-list.go

package linked_list

import (
	"fmt"
	"strings"
)

// node element to keep element and next node together
type node struct {
	el 	 interface{}
	next *node
}

// LinkedList of nodes
type LinkedList struct {
	head 	*node
}

// Get returns the element at postition i
func (l LinkedList) Get(i int) interface{} {
	cur := l.head
	for pos := 0; pos < i; pos++ {
		if cur == nil {	// limit exceeded
			return nil
		}
		cur = cur.next
	}
	return cur.el
}

// Search searches the element e and returns its index
func (l LinkedList) Search(e interface{}) int {
	pos := 0
	cur := l.head
	for cur.el != e {
		cur = cur.next
		pos++
	}
	return pos
}

// Add inserts the element e to the list at position i
func (l *LinkedList) Add(i int, e interface{}) {
	n := node{el: e}
	if i == 0 {
		n.next = l.head
		l.head = &n
		return
	}
	prev := l.head
	cur := l.head.next
	pos := 1
	for pos < i {
		prev = prev.next
		cur = cur.next
		pos++
	}
	prev.next = &n
	n.next = cur
}

// Delete removes the element at position i
func (l *LinkedList) Delete(i int) {
	if i == 0 {	// deleting the head
		l.head = l.head.next
		return
	}
	prev := l.head
	cur := l.head.next
	pos := 1
	for pos < i {
		prev = prev.next
		cur = cur.next
		pos++
	}
	prev.next = cur.next
}

// String return the representation of the list
func (l LinkedList) String() string {
	sb := strings.Builder{}
	sb.WriteString("[ ")
	for cur := l.head; cur != nil; cur = cur.next {
		sb.WriteString(fmt.Sprintf("%v ", cur.el))
	}
	sb.WriteByte(']')
	return sb.String()
}

linked-list1.go

package linked_list

import (
	"fmt"
	"strings"
)

// node element to keep element and next node together
type node struct {
	el 	 interface{}
	next *node
}

// LinkedList of nodes
type LinkedList struct {
	head 	*node
}

linked-list2.go

// Get returns the element at postition i
func (l LinkedList) Get(i int) interface{} {
	cur := l.head
	for pos := 0; pos < i; pos++ {
		if cur == nil {	// limit exceeded
			return nil
		}
		cur = cur.next
	}
	return cur.el
}

// Search searches the element e and returns its index
func (l LinkedList) Search(e interface{}) int {
	pos := 0
	cur := l.head
	for cur.el != e {
		cur = cur.next
		pos++
	}
	return pos
}

linked-list3.go

// Add inserts the element e to the list at position i
func (l *LinkedList) Add(i int, e interface{}) {
	n := node{el: e}
	if i == 0 {
		n.next = l.head
		l.head = &n
		return
	}
	prev := l.head
	cur := l.head.next
	pos := 1
	for pos < i {
		prev = prev.next
		cur = cur.next
		pos++
	}
	prev.next = &n
	n.next = cur
}

linked-list4.go

// Delete removes the element at position i
func (l *LinkedList) Delete(i int) {
	if i == 0 {	// deleting the head
		l.head = l.head.next
		return
	}
	prev := l.head
	cur := l.head.next
	pos := 1
	for pos < i {
		prev = prev.next
		cur = cur.next
		pos++
	}
	prev.next = cur.next
}

linked-list5.go

// String return the representation of the list
func (l LinkedList) String() string {
	sb := strings.Builder{}
	sb.WriteString("[ ")
	for cur := l.head; cur != nil; cur = cur.next {
		sb.WriteString(fmt.Sprintf("%v ", cur.el))
	}
	sb.WriteByte(']')
	return sb.String()
}

queue.go

package queue

import (
	"fmt"
	"strings"
)

// node element to keep element and next node together
type node struct {
	el interface{}
	next *node
}

// Queue of nodes
type Queue struct {
	head *node
	tail *node
}

// Enqueue method adds an element to the queue
func (q *Queue) Enqueue(e interface{}) {
	n := node{el: e}
	if q.tail == nil {
		q.head = &n
		q.tail = &n
		return
	}
	q.tail.next = &n
	q.tail = &n
}

// Dequeue method removes an element from the queue
func (q *Queue) Dequeue() interface{}{
	if q.head == nil {
		return nil
	}
	n := q.head
	q.head = q.head.next
	if q.head == nil {
		q.tail = nil
	}
	return n.el
}

queue1.go

package queue

import (
	"fmt"
	"strings"
)

// node element to keep element and next node together
type node struct {
	el interface{}
	next *node
}

// Queue of nodes
type Queue struct {
	head *node
	tail *node
}

queue2.go

// Enqueue method adds an element to the queue
func (q *Queue) Enqueue(e interface{}) {
	n := node{el: e}
	if q.tail == nil {
		q.head = &n
		q.tail = &n
		return
	}
	q.tail.next = &n
	q.tail = &n
}

queue3.go

// Dequeue method removes an element from the queue
func (q *Queue) Dequeue() interface{}{
	if q.head == nil {
		return nil
	}
	n := q.head
	q.head = q.head.next
	if q.head == nil {
		q.tail = nil
	}
	return n.el
}

stack.go

package stack

// Stack is the structure which contains our elements
type Stack struct {
	stack 	[]interface{}
	curInd 	int
}

// NewStack returns a pointer to a new stack having:
// - the array initialized with the provided size
// - the current index initialized with -1 (empty stack)
func NewStack(size int) *Stack {
	return &Stack{
		stack: make([]interface{}, size),
		curInd: -1,
	}
}

// IsEmpty returns true if the stack is empty
func (s *Stack) IsEmpty() bool {
	return s.curInd < 0
}

// Top returns the element at the top of the stack without removing it. 
// This method panics if the stack is empty
func (s *Stack) Top() interface{} {
	if s.IsEmpty() {
		panic("stack is empty")
	}
	return s.stack[s.curInd]
}

// Pop removes and returns the element at the top of the stack. 
// This method panics if the stack is empty
func (s *Stack) Pop() interface{} {
	if s.IsEmpty() {
		panic("stack is empty")
	}
	el := s.stack[s.curInd]
	s.stack[s.curInd] = nil
	s.curInd--
	return el
}

// Push inserts the element at the top of the stack. 
// This method panics if the stack is full
func (s *Stack) Push(el interface{}) {
	s.curInd++
	s.stack[s.curInd] = el
}

stack1.go

package stack

// Stack is the structure which contains our elements
type Stack struct {
	stack 	[]interface{}
	curInd 	int
}

stack2.go

// NewStack returns a pointer to a new stack having:
// - the array initialized with the provided size
// - the current index initialized with -1 (empty stack)
func NewStack(size int) *Stack {
	return &Stack{
		stack: make([]interface{}, size),
		curInd: -1,
	}
}

// IsEmpty returns true if the stack is empty
func (s *Stack) IsEmpty() bool {
	return s.curInd < 0
}

stack3.go

// Top returns the element at the top of the stack without removing it. 
// This method panics if the stack is empty
func (s *Stack) Top() interface{} {
	if s.IsEmpty() {
		panic("stack is empty")
	}
	return s.stack[s.curInd]
}

// Pop removes and returns the element at the top of the stack. 
// This method panics if the stack is empty
func (s *Stack) Pop() interface{} {
	if s.IsEmpty() {
		panic("stack is empty")
	}
	el := s.stack[s.curInd]
	s.stack[s.curInd] = nil
	s.curInd--
	return el
}

// Push inserts the element at the top of the stack. 
// This method panics if the stack is full
func (s *Stack) Push(el interface{}) {
	s.curInd++
	s.stack[s.curInd] = el
}

tree1.go

package tree

// Tree is a recursive structure containing an element and its child
type Tree struct {
	el 		interface{}
	child 	[]*Tree
}

// AddChild appends a new child to a node
func (t *Tree) AddChild(el interface{}) *Tree {
	c := &Tree{el: el}
	t.child = append(t.child, c)
	return c
}

tree2.go

	t := Tree{el: "r"}
	a := t.AddChild("a")
	a.AddChild("d")
	t.AddChild("b")
	t.AddChild("c")