Data Structures ADTs Implementation (In Go)

Data Structures ADTs Implementation (In Go)

Linked list

package main 

import "fmt"

func main (){

	var l = LinkedList{}
	var p Person= Person{"Abdulrahman",3} 

	l.insert(&p)
	l.insert(&Person{"John", 19})
	l.insert(&Person{"Bob", 19})
	l.insert(&Person{"Jack", 19})
	l.insert(&Person{"Martin", 19})

	l.remove()
	
	l.display()

}

type Person struct {
	name string
	age int
}

var p = Person{"",3}

type Node struct {
	data *Person
	next *Node
}

type LinkedList struct {
	head *Node
	current *Node
}

func (l *LinkedList) isEmpty() bool {
	return l.head == nil
} 

func (l *LinkedList) findNext(){
	l.current = l.current.next
}

func (l *LinkedList) insert(val *Person){
	if l.head == nil {
		l.current = &Node{val,nil}	
		l.head = l.current
	} else {
		tmp:= l.current.next
		
		n:= Node{val, tmp}
		
		l.current.next = &n

		l.current = l.current.next
		
	}

}

func (l *LinkedList) remove() {
	if l.current == l.head {
		l.head = l.head.next
	} else {
        	temp:= l.head
        	for temp.next != l.current {
                	temp = temp.next
        	}
		temp.next = l.current.next
	}
	if l.current.next == nil {
		l.current = l.head 
	}else{
		l.current = l.current.next
	}

}

func (l *LinkedList) display(){
	p:= l.head
	for p != nil {
		fmt.Printf("%v -> ", p.data)
		
		p = p.next
	}
	fmt.Println()
}

Stack (Array-based)

package main 

import (
	"fmt"
	"errors"
	"log"
)

func Check(err error) {
	if err != nil {
		log.Fatal(err)
	}
	
}

type Stack [] string

func main (){

	var stack Stack

	stack.Push("John Wick")
	stack.Push("Spiderman")
	stack.Push("Mary Jane")
	stack.Push("Superman")

	stack.Display()

  item ,err:=stack.peek()
  Check(err)
  fmt.Println("Peek Item value: ", item)
  
	item1, err :=stack.Pop()
	Check(err)

	fmt.Println("Item1 value: ", item1)

	stack.Display()

	item2, err :=stack.Pop()
	Check(err)

	fmt.Println("Item2 value: ", item2)

	item3,err :=stack.Pop()

	Check(err)
	fmt.Println("Item3 value: ", item3)

	// Empty stack : This will throw an error
	item4,err :=stack.Pop() 
	Check(err)
	
	fmt.Println("Item4 value: ", item4)

	// Display the stack items
	stack.Display()

}

func (stack *Stack) Pop () (string, error){
	 
  stack.isEmpty()	

	item := (*stack)[len(*stack) - 1]

	*stack = (*stack)[:len(*stack) - 1]
	fmt.Println("Item has been popped out successfully")

	return item, nil
}

func (stack *Stack) Push(item string) {

	*stack = append(*stack, item)

	fmt.Println("Item has been pushed successfully")
}

func (stack *Stack) Display(){

	for i, item := range *stack {
		fmt.Printf("[%d] : %s\n", i, item)
	}
	
}

func (stack *Stack) isEmpty() {
  if len(*stack) == 0 {
		errors.New("The stack is empty")
	}  
}

func (stack *Stack) peek()(string, error) {
  stack.isEmpty()
	item := (*stack)[len(*stack) - 1]
  return item, nil
}

Stack (linked-list based)

Binary Tree

package main

import "fmt"

const  (
  PreOrder  = "preOrder"
  InOrder  = "inOrder"
  PostOrder = "postOrder"
  Root = "root"
  LeftChild = "leftChild"
  RightChild = "rightChild"
  Parent = "parent"
)

type node struct {
  data int 
  left *node
  right *node
}

type binaryTree struct {
  root *node 
  current *node
}

func main(){
    var bt binaryTree = binaryTree{nil, nil}
    
    bt.insert(90, Root)
    fmt.Println(bt.current)
    bt.insert(20, RightChild)
    bt.find(Parent)
    bt.insert(16, LeftChild)
    bt.find(Parent)
  
    fmt.Println(bt.current)

    bt.find(LeftChild)
    
    bt.deleteSubTree()

    fmt.Println(bt.current)
}

func (bt *binaryTree) insert(data int, relative string ) bool {
  switch relative {
    case Root:
      if !bt.isTreeEmpty() {
        return false
      }
      n := node{data,nil,nil}
      bt.root = &n
      bt.current = bt.root
      return true
    case Parent:{
      // You can't find the parent of the root
      if bt.current == bt.root {
        return false 
      }
      bt.current = findParent(bt.current, bt.root)
      return true
    }
    case LeftChild:
      if bt.current.left != nil {
        return false
      }
      n := node{data, nil, nil}
      bt.current.left = &n
      bt.current = bt.current.left
      return true
    case RightChild:
      if bt.current.right != nil {
        return false
      }
      n := node{data, nil, nil}
      bt.current.right = &n
      bt.current = bt.current.right
      return true
    default:
      return false
  }
}

func (bt *binaryTree) deleteSubTree() {
  if bt.current == bt.root {
    bt.root = nil
    bt.current = bt.root
  } else {
    n := bt.current
    bt.find(Parent)
    if(bt.current.left == n){
      bt.current.left = nil
    } else if (bt.current.right == n){
      bt.current.right = nil
    }
    bt.current = bt.root
  }
  
}

func (bt *binaryTree) update(data int){
  bt.current.data = data
}

func (bt *binaryTree) retrieve(data int) *node{
  return bt.current
}

func  (bt *binaryTree) find(relative string)bool{
  switch relative{
    case Root :{
      bt.current = bt.root
      return true
    }
    case Parent:{
      if bt.current == bt.root {
        return false
      }
      bt.current = findParent(bt.current, bt.root)
      return true
    }
    case LeftChild:{
      if bt.current.left == nil {
        return false
      }
      bt.current  = bt.current.left
      return true
    }
    case RightChild:{
      if bt.current.right == nil {
        return false
      }
      bt.current  = bt.current.right
      return true
    }
    default:{
      return false
    }
  }

}

func findParent (n *node, root *node)*node{
  if root == nil {
    return nil
  }
  if root.right == nil && root.left == nil {
    return nil
  } else if root.right == n || root.left == n {
      return root
  }else {
    tmp:= findParent(n, root.right)
    if tmp != nil {
      return tmp.left
    }else {
      return findParent(n, root.left)
    }
  }
} 

func (bt *binaryTree) isTreeEmpty() bool {
  return bt.root == nil
}

Queue

package main
import "fmt"

type node struct {
  data int 
  next *node
}

type queue struct {
  head *node
  tail *node
  size int
}

func main(){
  q:= queue{nil,nil,10}
  fmt.Println(q)

  q.enqueue(10)
  q.enqueue(20)
  q.enqueue(0)

  fmt.Println(*q.find(10))

  q.display()
} 

func (q *queue) enqueue(data int){
  n:= node{data, nil}
  if q.head == nil {
    q.head = &n
    q.tail = &n
  }else {  
    q.tail.next = &n
    q.tail = q.tail.next
  }
  q.size++
}

func (q *queue) dequeue () int {
  data := q.head.data
  q.head = q.head.next
  q.size--
  if q.size == 0 {
    q.tail = nil
  }
  return data
}

func (q *queue) find(data int) *node{
  tmp := q.head

  for tmp != nil {
    if tmp.data == data {
      return tmp
    }
    tmp = tmp.next
  }
  return nil
}

func (q *queue) display(){
  tmp := q.head
  for tmp.next != nil {
    fmt.Print(tmp.data ," --> ")
    tmp = tmp.next
  }
  if &tmp != nil {
    fmt.Print(tmp.data )
  }
}

Ring Buffer (Circular Queue)

type MyCircularQueue struct {
    size int
    head int
    queue []int
}

func Constructor(k int) MyCircularQueue {
    queue := make([]int, k)
    size := 0
    head := 0
    
    return MyCircularQueue{
        queue:queue,
        size:size,
        head:head,
    }
}

func (this *MyCircularQueue) EnQueue(value int) bool {
    if this.IsFull(){
        return false
    }
    
    this.queue[(this.head + this.size) % cap(this.queue)] = value
    
    this.size++
    
    return true
}

func (this *MyCircularQueue) DeQueue() bool {
    if this.IsEmpty(){
        return false
    }
    
    this.head = (this.head+1) % cap(this.queue)
   
    this.size--
    return true
}

func (this *MyCircularQueue) Front() int {
    if this.IsEmpty(){
        return -1
    }
    return this.queue[this.head]   
}

func (this *MyCircularQueue) Rear() int {
     if this.IsEmpty(){
        return -1
    }
    return this.queue[(this.head + this.size -1) % cap(this.queue)] 
}

func (this *MyCircularQueue) IsEmpty() bool {
    return this.size == 0
}

func (this *MyCircularQueue) IsFull() bool {
    return this.size == cap(this.queue)
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.EnQueue(value);
 * param_2 := obj.DeQueue();
 * param_3 := obj.Front();
 * param_4 := obj.Rear();
 * param_5 := obj.IsEmpty();
 * param_6 := obj.IsFull();
 */