Datastructures in Go
linked list stack queue tree trie graph
Linked lists are a data structure that stores data in a linked list of nodes. Linked lists are efficient for storing data that needs to be accessed in a non-sequential order.
To initialize create 2 structs as Linked List and Node
There are 4 primary methods on LinkedList:
- Create
- Insert
- InsertN
- Remove
- Reverse
package main
import "fmt"
// Linked List
type LinkedList struct {
Head *Node
Length int
}
type Node struct {
Data int
Next *Node
}
func main() {
myl := LinkedList{Head: nil}
myl.Create(1)
myl.Create(2)
myl.Create(3)
myl.InsertN(4, 3)
myl.show()
fmt.Println("-------------------------------------deleted-------------")
// myl.Delete()
// myl.deleteN(1)
// myl.deleteFirst()
// myl.reverse()
ReverseRecursion(myl.Head)
myl.show()
}
func (l *LinkedList) Create(data int) {
elem := &Node{Data: data, Next: nil}
if l.Head == nil {
l.Head = elem
} else {
current := l.Head
for current.Next != nil {
current = current.Next
}
current.Next = elem
}
}
func (l *LinkedList) show() {
if l.Head == nil {
fmt.Println("no data")
} else {
current := l.Head
for current != nil {
fmt.Println(current)
current = current.Next
}
}
}
func (l *LinkedList) InsertN(data int, n int) {
elem := &Node{Data: data, Next: nil}
if l.Head == nil {
fmt.Println("no data")
} else {
count := 0
current := l.Head
for current != nil {
count += 1
if count == n {
k := current.Next
current.Next = elem
elem.Next = k
}
current = current.Next
}
}
}
func (l *LinkedList) Delete() {
if l.Head == nil {
fmt.Println("no data")
} else {
current := l.Head
for current.Next.Next != nil {
current = current.Next
}
current.Next = nil
}
}
func (l *LinkedList) deleteN(n int) {
if l.Head == nil {
fmt.Println("no data")
} else {
count := 0
current := l.Head
for current != nil {
count += 1
prev := current
current = current.Next
if count == n {
prev.Next = current.Next
}
}
}
}
func (l *LinkedList) deleteFirst() {
if l.Head == nil {
fmt.Println("no list")
} else {
l.Head = l.Head.Next
}
}
create node Create method on LinkedList takes integer as data and creates a new node elem. It checks if there is no head then the elem node will be the first node else it goes to all nodes by node.Next and adds the node where the node is nil
reverse linked list To reverse a linked list first check for its head. We need 3 variables of node type as current next and previous. we need to store the value of current and nxt and previous before changing any pointer address. once done then current can move to next node with next varialbe address and point it to pevious node with previous variable
func (l *LinkedList) reverse() {
if l.Head == nil {
fmt.Println("no list")
} else {
current := l.Head
var prev *Node
var next *Node
for current != nil {
next = current.Next //first get next location
current.Next = prev // set next location to prev
prev = current //change pointer a -> b to b-> a
current = next //move to third pointer
}
l.Head = prev //add head pointer to last block address
}
}
func ReverseRecursion(node *Node) {
p := node
if p == nil {
return
}
ReverseRecursion(p.Next)
fmt.Println(p.Data)
}
package main
import "fmt"
func DoubleLinkListInit() {
dll := &DoubleLinkList{}
dll.append(100)
dll.append(200)
dll.append(300)
dll.append(400)
dll.TraverseForward()
fmt.Println("------------------reverse---------------")
dll.TraverseBackward()
}
type DoubleNode struct {
Data int
Next *DoubleNode
Prev *DoubleNode
}
type DoubleLinkList struct {
Data int
Head *DoubleNode
Tail *DoubleNode
}
func (l *DoubleLinkList) prepend(data int) {
temp := &DoubleNode{Data: data, Next: nil, Prev: nil}
if l.Head == nil {
l.Head = temp
l.Tail = temp
} else {
temp.Next = l.Head
l.Head.Prev = temp
l.Head = temp
}
}
func (l *DoubleLinkList) append(data int) {
temp := &DoubleNode{Data: data, Next: nil, Prev: nil}
if l.Head == nil {
l.Head = temp
l.Tail = temp
} else {
current := l.Head
for current.Next != nil {
current = current.Next
}
temp.Prev = current
current.Next = temp
l.Tail = temp
}
}
func (l *DoubleLinkList) TraverseForward() {
if l.Head == nil {
fmt.Println("no lisst")
} else {
current := l.Head
for current != nil {
fmt.Printf("value = %v, prev = %v, next = %v\n", current.Data, current.Prev, current.Next)
current = current.Next
}
}
}
func (l *DoubleLinkList) TraverseBackward() {
if l.Head == nil {
fmt.Println("no list")
} else {
current := l.Tail
for current != nil {
fmt.Println(current.Data, current.Next, current.Prev)
current = current.Prev
}
}
}
Stacks are a data structure that stores data in a last-in, first-out (LIFO) order. This means that the last item that is added to the stack is the first item that is removed.
Stacks can be implenmented using underlying array or linked list. they work on last in first out principal.
package main
import "fmt"
// lifo
// Stack implementaion with slice
type Stack struct {
Items []int
}
func main() {
var mys Stack
mys.Push(99)
mys.Push(1)
mys.Push(2)
mys.Push(3)
mys.Push(4)
fmt.Println(mys.isEmpty())
fmt.Println(mys.isEmpty())
fmt.Println(mys.Pop())
fmt.Println(mys.Pop())
fmt.Println(mys.Peek())
}
the main methods on stacks are Push -> add on top Pop -.> remove from top Peek -> see value on top
stack peek Peek method on stack looks for the last variable in the array and returns int value
func (s *Stack) isEmpty() bool {
return len(s.Items) == 0
}
stack push Stack push method takes arguement int and appends it on the last end in case of a array [slice for go]
func (s *Stack) Push(data int) {
s.Items = append(s.Items, data)
}
stack pop On using pop method on stack the last value of underlying array and removes it
func (s *Stack) Pop() (int, bool) {
if len(s.Items) == 0 {
return 0, false
} else {
lastItem := len(s.Items) - 1
s.Items = s.Items[:len(s.Items)-1]
return lastItem, true
}
}
stack peek stack peek is used to peek the top element in stack without removing it.
func (s *Stack) Peek() int {
if len(s.Items) == 0 {
fmt.Println("no stack")
return 0
} else {
lastItem := len(s.Items) - 1
return lastItem
}
}
Queues are a data structure that stores data in a first-in, first-out (FIFO) order. This means that the first item that is added to the queue is the first item that is removed. Queues are efficient for storing data that needs to be processed in a FIFO order.
Main methods on Queue are Enquque -> adds variable on last Dequque -> takes the first value out
enqueue Enqueue takes the data int and appends it to the underlying slice
Dequeue reads the first item in underlying slice and return and removes it
package main
import "fmt"
// first in first out
// Queue implementation
type Queue struct {
Items []int
}
func main() {
myq := Queue{}
myq.enqueue(100)
myq.enqueue(200)
myq.enqueue(300)
myq.enqueue(400)
fmt.Println(myq.Items)
fmt.Println(myq.dequeue())
fmt.Println(myq.dequeue())
}
func (q *Queue) enqueue(data int) int {
q.Items = append(q.Items, data)
return data
}
func (q *Queue) dequeue() (int, bool) {
if len(q.Items) == 0 {
return 0, false
} else {
firstItem := q.Items[0]
q.Items = append(q.Items[1:])
return firstItem, true
}
}
Trees are a data structure that stores data in a hierarchical structure. Trees are efficient for storing data that has a natural hierarchy, such as the file system on a computer.
Trees can be ok many types Binary tree -> both sides with max 2 nodes Tries -> one node can have multiple nodes
insert treenode To insert data into a tree when we use Insert method. when the data is added then a temp node is created and all the branches are looked such as if the data is small than right node then left node is looked for empty space and vice versa. once a empty node is found then the temp node is added to left if data is small than right.
tree lookup To search if a valeus is in the tree we can use BFS, DFS . Our approach is to look for all the nodes in left then to right . if we find a value that matches the lookup value then we return the value else we return nil
traverse tree Lookup of Binary tree has several methods such as Breadth first search or depth first search. for this approach we can traverse a tree by checking all the nodes from left to right and add the node data into a array.
package main
import "fmt"
type Tree struct {
Data int
Left *Tree
Right *Tree
}
func main() {
t := &Tree{Data: 50, Left: nil, Right: nil}
t.Insert(100)
t.Insert(20)
t.Insert(55)
t.Insert(23)
t.Insert(11)
t.Insert(43)
t.Insert(788)
t.Insert(454)
t.Insert(246)
// fmt.Println(t.lenght)
// fmt.Println(t.Right.Right.Data)
// fmt.Println(t.Left.Left.Data)
// fmt.Println(t.Lookup(20))
// out := Traverse(t)
// fmt.Println(out)
out := BFST(t)
fmt.Println(out)
// t.Root.Traverse()
// print(os.Stdout, t.Root, 0, 'M')
}
func BFST(tree *Tree) []int {
result := []int{}
queue := []*Tree{}
queue = append(queue, tree)
return bfstUtil(queue, result)
}
func bfstUtil(queue []*Tree, result []int) []int {
if len(queue) == 0 {
return result
}
result = append(result, queue[0].Data)
if queue[0].Right != nil {
queue = append(queue, queue[0].Right)
}
if queue[0].Left != nil {
queue = append(queue, queue[0].Left)
}
return bfstUtil(queue[1:], result)
}
func DFS(tree *Tree) []int {
// mark node visited
visited := []*Tree{}
result := []int{}
visited = append(visited, tree)
DFSUtil(visited, result)
return result
}
func DFSUtil(visited []*Tree, result []int) []int {
if len(visited) == 0 {
return result
}
result = append(result, visited[0].Data)
if visited[0].Right != nil {
}
return result
}
func (t *Tree) Insert(data int) *Tree {
temp := Tree{Data: data, Left: nil, Right: nil}
if t.Data == 0 {
t.Left = &temp
return &temp
} else {
current := t
for {
if data < current.Data {
// left
if current.Left == nil {
current.Left = &temp
return current
}
current = current.Left
} else {
// right
if current.Right == nil {
current.Right = &temp
return current
}
current = current.Right
}
}
}
}
func (t *Tree) Lookup(data int) *Tree {
if t == nil {
fmt.Println("non tree")
} else {
current := t
for current != nil {
if data < current.Data {
current = current.Left
} else if data > current.Data {
current = current.Right
} else if current.Data == data {
return current
}
}
}
return nil
}
// in order Traverse
func Traverse(root *Tree) []int {
if root == nil {
return nil
}
output := make([]int, 0)
left := Traverse(root.Left)
right := Traverse(root.Right)
output = append(output, left...)
output = append(output, root.Data)
output = append(output, right...)
return output
}
package main
import "fmt"
//Declaring trie_Node for creating node in a trie
type trie_Node struct {
//assigning limit of 26 for child nodes
childrens [26]*trie_Node
//declaring a bool variable to check the word end.
wordEnds bool
}
//Initializing the root of the trie
type trie struct {
root *trie_Node
}
//inititlaizing a new trie
func trieData() *trie {
t := new(trie)
t.root = new(trie_Node)
return t
}
//Passing words to trie
func (t *trie) insert(word string) {
current := t.root
for _, wr := range word {
index := wr - 'a'
if current.childrens[index] == nil {
current.childrens[index] = new(trie_Node)
}
current = current.childrens[index]
}
current.wordEnds = true
}
//Initializing the search for word in node
func (t *trie) search(word string) int {
current := t.root
for _, wr := range word {
index := wr - 'a'
if current.childrens[index] == nil {
return 0
}
current = current.childrens[index]
}
if current.wordEnds {
return 1
}
return 0
}
//initializing the main function
func main() {
trie := trieData()
//Passing the words in the trie
word := []string{"aqua", "jack", "card", "care"}
for _, wr := range word {
trie.insert(wr)
}
//initializing search for the words
words_Search := []string{"aqua", "jack", "card", "care", "cat", "dog", "can"}
for _, wr := range words_Search {
found := trie.search(wr)
if found == 1 {
fmt.Printf("\"%s\"Word found in trie\n", wr)
} else {
fmt.Printf(" \"%s\" Word not found in trie\n", wr)
}
}
}
Graphs are a data structure that stores data in a network of nodes and edges. Graphs are efficient for storing data that can be represented as a network, such as the social network of friends and family.
Graph can be weighted, directed or cyclic.
There are ways to represent graphs Adjecent Matrix -> 2d matix Adjecent list -> used moostly because of better o(n) Incedence matrix
add and get vertex
add edge
show graph
package main
import (
"fmt"
)
type Vertex struct {
Key int
Vertices []*Vertex
}
type Graph struct {
vertices []*Vertex
}
func main() {
g := Graph{}
g.add_vertices(1)
g.add_vertices(2)
g.add_vertices(3)
g.add_edges(1, 2)
g.add_edges(1, 3)
g.add_edges(2, 3)
g.showGraph()
}
func (g *Graph) add_vertices(v int) {
temp := &Vertex{Key: v}
g.vertices = append(g.vertices, temp)
}
func (g *Graph) get_vertex(k int) *Vertex {
for _, v := range g.vertices {
if v.Key == k {
return v
}
}
return nil
}
// add edges to each verteses
func (g *Graph) add_edges(to, from int) {
// change int to vertices
toVertex := g.get_vertex(to)
fromVertex := g.get_vertex(from)
// in graph teake to and from points
for _, v := range g.vertices {
if v.Key == toVertex.Key {
toVertex.Vertices = append(toVertex.Vertices, fromVertex)
// append from.vertices to to
}
}
}
// print all vertex and list of related vertexes
func (g *Graph) showGraph() {
for _, v := range g.vertices {
fmt.Printf("%v", v.Key)
for _, e := range v.Vertices {
fmt.Printf("--> %v", e.Key)
}
fmt.Println()
}
// return nil
}