Go Data Structures
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