Skip to main content

Go Data Structures

Shenzhen, China

Github

Arrays

package main

import (
	"fmt"
)

func main() {
	fmt.Println("Arrays as Data Structures")

	myArray := [8]int{1, 2, 3, 4, 5, 6, 7, 8}

	fmt.Println("Array: ", myArray)

	fmt.Println("First Element: ", myArray[0])

	fmt.Println("Last Element: ", myArray[len(myArray)-1])
}
Arrays as Data Structures
Array:  [1 2 3 4 5 6 7 8]
First Element:  1
Last Element:  8

Slices

package main

import (
	"fmt"
)

func main() {
	fmt.Println("Slices as Data Structures")

	// Slices don't have a pre-defined length
	mySlice := []int{1, 2, 3, 4, 5, 6, 7, 8}

	fmt.Println("Slice: ", mySlice)

	fmt.Println("First Element: ", mySlice[0])

	fmt.Println("Last Element: ", mySlice[len(mySlice)-1])
}
Slices as Data Structures
Slice:  [1 2 3 4 5 6 7 8]
First Element:  1
Last Element:  8

Sets

package main

import (
	"errors"
	"fmt"
)

type Set struct {
	Elements map[string]struct{}
}

// create new set
func NewSet() *Set {
	var set Set
	set.Elements = make(map[string]struct{})
	return &set
}

// add elements to set
// sets don't have an order - we don't need to append
// every element in a set is unique - already existing
// elements will not be duplicated (no checks necessary)
func (s *Set) Add(elem string) {
	s.Elements[elem] = struct{}{}
}

// remove element from set if exists
func (s *Set) Delete(elem string) error {
	// check if element is present
	if _, exists := s.Elements[elem]; !exists {
		return errors.New("Element not present!")
	}
	// if present -delete
	delete(s.Elements, elem)
	return nil
}

// check if set contains element
func (s *Set) Contains(elem string) bool {
	_, exists := s.Elements[elem]
	return exists
}

// list all elements from set
func (s *Set) List() {
	for key, _ := range s.Elements {
		fmt.Println(key)
	}
}

func main() {
	fmt.Println("Sets as Data Structures")

	// instantiate / populate set
	mySet := NewSet()
	mySet.Add("Eddard Stark")
	mySet.Add("Jaime Lannister")
	mySet.Add("Daenerys Targaryen")
	mySet.Add("Arya Stark")
	mySet.Add("Sandor Clegane")
	mySet.Add("Tyrion Lannister")

	// delete element
	mySet.Delete("Eddard Stark")

	// find element
	fmt.Println(mySet.Contains("Jon Snow"))
	fmt.Println(mySet.Contains("Arya Stark"))

	// list all elements
	mySet.List()
}
Sets as Data Structures
false
true
Arya Stark
Sandor Clegane
Tyrion Lannister
Jaime Lannister
Daenerys Targaryen

Queues

package main

import (
	"errors"
	"fmt"
)

type Queue struct {
	Elements []int
}

// show length of queue
func (q *Queue) Length() int {
	return len(q.Elements)
}

// return true when queue length is zero
func (q *Queue) IsEmpty() bool {
	return q.Length() == 0
}

// add element to end of queue
func (q *Queue) Enqueue(elem int) {
	q.Elements = append(q.Elements, elem)
}

// check first element in que without removing it
func (q *Queue) Peek() (int, error) {
	// test queue not empty
	if q.IsEmpty() {
		return 0, errors.New("Empty Queue")
	}
	return q.Elements[0], nil
}

// remove first element from queue
func (q *Queue) Dequeue() (int, error) {
	// test queue not empty
	if q.IsEmpty() {
		return 0, errors.New("Empty Queue")
	}
	// drop first element from slice
	var firstElement int
	firstElement, q.Elements = q.Elements[0], q.Elements[1:]
	return firstElement, nil
}

func main() {
	fmt.Println("Queues as Data Structures")

	// instantiate queue and add element
	var elem int
	queue := Queue{}
	fmt.Println(queue)
	queue.Enqueue(1)
	queue.Enqueue(2)
	queue.Enqueue(3)
	fmt.Println(queue)

	// drop first item
	elem, _ = queue.Dequeue()
	fmt.Println(elem)
	fmt.Println(queue)

	// check first item without removing it
	elem, _ = queue.Peek()
	fmt.Println(elem)
	fmt.Println(queue)
}
Queues as Data Structures
{[]}
{[1 2 3]}
1
{[2 3]}
2
{[2 3]}

Priority Queues

Priority queues are an extension on regular queues as they have two instead of one channel - one for high and one for low priority elements:

package main

import (
	"errors"
	"fmt"
)

type PriorityQueue struct {
	High []int
	Low  []int
}

// show length of complete queue
func (q *PriorityQueue) Length() int {
	return len(q.High) + len(q.Low)
}

// return true when queue length is zero
func (q *PriorityQueue) IsEmpty() bool {
	return q.Length() == 0
}

// add element to end of queue
// differentiate between high/low priority
func (q *PriorityQueue) Enqueue(elem int, priority bool) {
	if priority {
		q.High = append(q.High, elem)
	} else {
		q.Low = append(q.Low, elem)
	}
}

// check first element in que without removing it
// but prefer priority queue
func (q *PriorityQueue) Peek() (int, error) {
	// test queue not empty
	if len(q.High) != 0 {
		return q.High[0], nil
	}
	if len(q.Low) != 0 {
		return q.Low[0], nil
	}
	// return 0 if both queues are empty
	return 0, errors.New("Empty Queues")
}

// remove first element from queue
// but prefer priority queue
func (q *PriorityQueue) Dequeue() (int, error) {
	// test if priority queue not empty
	// if true remove first element
	if len(q.High) != 0 {
		var firstElement int
		firstElement, q.High = q.High[0], q.High[1:]
		return firstElement, nil
	}
	// test if regular queue not empty
	// if true remove first element
	if len(q.Low) != 0 {
		var firstElement int
		firstElement, q.Low = q.Low[0], q.Low[1:]
		return firstElement, nil
	}
	// return 0 if both queues are empty
	return 0, errors.New("Empty Queues")
}

func main() {
	fmt.Println("Priority Queues as Data Structures")

	// instantiate queue and add element
	var elem int
	queue := PriorityQueue{}
	fmt.Println(queue)
	queue.Enqueue(1, true)
	queue.Enqueue(2, true)
	queue.Enqueue(3, false)
	queue.Enqueue(4, false)
	fmt.Println(queue)

	// drop first item
	elem, _ = queue.Dequeue()
	fmt.Println(elem)
	fmt.Println(queue)

	// check first item without removing it
	elem, _ = queue.Peek()
	fmt.Println(elem)
	fmt.Println(queue)
}

All elements from the high priority queue will no be handled first before the low priority queue is started:

Priority Queues as Data Structures
{[] []}
{[1 2] [3 4]}
1
{[2] [3 4]}
2
{[2] [3 4]}

Stacks

Stacks are almost identical to queues but elements here are removed by last-in/first-out:

package main

import (
	"errors"
	"fmt"
)

type Stack struct {
	Elements []int
}

// check stack size
func (s *Stack) Length() int {
	return len(s.Elements)
}

// stack is empty?
func (s *Stack) IsEmpty() bool {
	return s.Length() == 0
}

// add an element to top of the stack
func (s *Stack) Push(elem int) {
	s.Elements = append(s.Elements, elem)
}

// remove top element from stack
func (s *Stack) Pop() (int, error) {
	// check if stack is empty
	if s.IsEmpty() {
		return 0, errors.New("Stack is Empty")
	} else {
		var lastElement int
		lastElementIndex := len(s.Elements) - 1
		lastElement, s.Elements = s.Elements[lastElementIndex], s.Elements[:lastElementIndex]
		return lastElement, nil
	}
}

// check top element without removing
func (s *Stack) Peek() (int, error) {
	// check if stack is empty
	if s.IsEmpty() {
		return 0, errors.New("Stack is Empty")
	} else {
		return s.Elements[len(s.Elements)-1], nil
	}
}

func main() {
	fmt.Println("Stacks as Data Structures")

	stack := Stack{}
	stack.Push(1)
	stack.Push(2)
	stack.Push(3)

	elem1, _ := stack.Pop()
	fmt.Println(elem1)
	elem2, _ := stack.Pop()
	fmt.Println(elem2)

	peek3, _ := stack.Peek()
	fmt.Println(peek3)

	elem3, _ := stack.Pop()
	fmt.Println(elem3)

	fmt.Println(stack.IsEmpty())
}
Stacks as Data Structures
3
2
1
1
true

Linked Lists

package main

import (
	"fmt"
)

type LinkedList struct {
	Head *Node
	Size int
}

// nodes are linked elements in list
type Node struct {
	Value string
	Next  *Node
}

// add new node to head of linked list
func (l *LinkedList) Insert(elem string) {
	node := Node{
		Value: elem,
		Next:  l.Head,
	}
	l.Head = &node
	l.Size++
}

// remove first element
func (l *LinkedList) DeleteFirst() {
	l.Head = l.Head.Next
	l.Size--
}

// iterate through list and print
func (l *LinkedList) List() {
	current := l.Head
	for current != nil {
		fmt.Printf("%+v\n", current)
		current = current.Next
	}
}

// find element in list
func (l *LinkedList) Search(elem string) *Node {
	current := l.Head
	for current != nil {
		if current.Value == elem {
			return current
		}
		current = current.Next
	}
	return nil
}

// delete element
func (l *LinkedList) Delete(elem string) {
	previous := l.Head
	current := l.Head
	// check if element exists
	for current != nil {
		// link previous to next to remove current
		if current.Value == elem {
			previous.Next = current.Next
			l.Size--
		}
		previous = current
		current = current.Next
	}
}

func main() {
	fmt.Println("Linked Lists as Data Structures")
	var ll LinkedList

	ll.Insert("Camina Drummer")
	ll.Insert("Joe Miller")
	ll.Insert("Amos Burton")
	ll.Insert("Chrisjen Avasarala")

	ll.List()
	fmt.Println("-----------------------------")

	ll.DeleteFirst()
	ll.List()
	fmt.Println("-----------------------------")

	if element := ll.Search("Joe Miller"); element != nil {
		fmt.Printf("%+v\n", element)
	}
	fmt.Println("-----------------------------")

	ll.Delete("Joe Miller")
	ll.List()
	fmt.Println(ll.Size)
}
Linked Lists as Data Structures
&{Value:Chrisjen Avasarala Next:0xc000010060}
&{Value:Amos Burton Next:0xc000010048}
&{Value:Joe Miller Next:0xc000010030}
&{Value:Camina Drummer Next:<nil>}
-----------------------------
&{Value:Amos Burton Next:0xc000010048}
&{Value:Joe Miller Next:0xc000010030}
&{Value:Camina Drummer Next:<nil>}
-----------------------------
&{Value:Joe Miller Next:0xc000010030}
-----------------------------
&{Value:Amos Burton Next:0xc000010030}
&{Value:Camina Drummer Next:<nil>}
2