A data structure is a way of organizing and storing data to perform operations efficiently. Choosing the right data structure is crucial for optimizing performance in different use cases.
A linked list is a sequence of nodes, where each node contains data and a pointer to the next node.
🔹 Advantages:
🔹 Disadvantages:
package main
import "fmt"
type Node struct {
data int
next *Node
}
type LinkedList struct {
head *Node
}
func (l *LinkedList) Insert(data int) {
newNode := &Node{data: data, next: l.head}
l.head = newNode
}
func (l *LinkedList) Print() {
current := l.head
for current != nil {
fmt.Print(current.data, " -> ")
current = current.next
}
fmt.Println("nil")
}
func main() {
list := LinkedList{}
list.Insert(10)
list.Insert(20)
list.Insert(30)
list.Print() // Output: 30 -> 20 -> 10 -> nil
}
🔹 Insertion is O(1) since we insert at the head.
🔹 Searching is O(n) since we traverse the list.
A Red-Black Tree (RBT) is a self-balancing binary search tree (BST), ensuring worst-case O(log n) operations.
🔹 Key Properties:
✅ Every node is either red or black.
✅ The root is always black.
✅ No two consecutive red nodes exist.
✅ Every path from a node to its leaves contains the same number of black nodes.
✔ Balanced search trees (compared to unbalanced BSTs).
✔ Frequent insertions/deletions while maintaining O(log n) efficiency.
✔ Used in STL's map and set in C++.
package main
import (
"fmt"
)
const (
RED = true
BLACK = false
)
type Node struct {
data int
color bool
left *Node
right *Node
parent *Node
}
type RedBlackTree struct {
root *Node
}
// Rotate Left
func (t *RedBlackTree) rotateLeft(x *Node) {
y := x.right
x.right = y.left
if y.left != nil {
y.left.parent = x
}
y.parent = x.parent
if x.parent == nil {
t.root = y
} else if x == x.parent.left {
x.parent.left = y
} else {
x.parent.right = y
}
y.left = x
x.parent = y
}
// Rotate Right
func (t *RedBlackTree) rotateRight(y *Node) {
x := y.left
y.left = x.right
if x.right != nil {
x.right.parent = y
}
x.parent = y.parent
if y.parent == nil {
t.root = x
} else if y == y.parent.right {
y.parent.right = x
} else {
y.parent.left = x
}
x.right = y
y.parent = x
}
// Insert Fix-up to maintain Red-Black properties
func (t *RedBlackTree) insertFixup(z *Node) {
for z.parent != nil && z.parent.color == RED {
if z.parent == z.parent.parent.left {
uncle := z.parent.parent.right
if uncle != nil && uncle.color == RED {
// Case 1: Uncle is red
z.parent.color = BLACK
uncle.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
} else {
if z == z.parent.right {
// Case 2: Triangle formation
z = z.parent
t.rotateLeft(z)
}
// Case 3: Line formation
z.parent.color = BLACK
z.parent.parent.color = RED
t.rotateRight(z.parent.parent)
}
} else {
// Mirror case
uncle := z.parent.parent.left
if uncle != nil && uncle.color == RED {
z.parent.color = BLACK
uncle.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
} else {
if z == z.parent.left {
z = z.parent
t.rotateRight(z)
}
z.parent.color = BLACK
z.parent.parent.color = RED
t.rotateLeft(z.parent.parent)
}
}
}
t.root.color = BLACK
}
// Insert a node
func (t *RedBlackTree) Insert(data int) {
newNode := &Node{data: data, color: RED}
if t.root == nil {
t.root = newNode
t.root.color = BLACK
return
}
var parent *Node
current := t.root
for current != nil {
parent = current
if data < current.data {
current = current.left
} else {
current = current.right
}
}
newNode.parent = parent
if data < parent.data {
parent.left = newNode
} else {
parent.right = newNode
}
t.insertFixup(newNode)
}
// In-order Traversal
func (t *RedBlackTree) inOrderTraversal(node *Node) {
if node != nil {
t.inOrderTraversal(node.left)
color := "RED"
if node.color == BLACK {
color = "BLACK"
}
fmt.Printf("%d (%s) ", node.data, color)
t.inOrderTraversal(node.right)
}
}
func main() {
tree := &RedBlackTree{}
values := []int{10, 20, 30, 15, 25, 5}
for _, v := range values {
tree.Insert(v)
}
fmt.Println("In-order traversal (sorted output with colors):")
tree.inOrderTraversal(tree.root)
}
A hash map stores key-value pairs and provides average O(1) lookup time.
🔹 Best Use Cases:
✔ Fast lookups (e.g., caching, key-value storage).
✔ No fixed size like arrays.
package main
import "fmt"
func main() {
phoneBook := map[string]string{
"Alice": "123-456",
"Bob": "789-012",
}
fmt.Println("Alice's Number:", phoneBook["Alice"]) // 123-456
}
🔹 O(1) average case lookup/insertion.
🔹 O(n) worst case if hash collisions occur.
✔ Used in backtracking, function calls (recursion), undo features.
package main
import "fmt"
type Stack struct {
items []int
}
func (s *Stack) Push(value int) {
s.items = append(s.items, value)
}
func (s *Stack) Pop() int {
if len(s.items) == 0 {
panic("Stack is empty!")
}
val := s.items[len(s.items)-1]
s.items = s.items[:len(s.items)-1]
return val
}
func main() {
stack := Stack{}
stack.Push(1)
stack.Push(2)
fmt.Println(stack.Pop()) // Output: 2
}
🔹 Push & Pop are O(1).
✔ Used in task scheduling, breadth-first search, print spooling.
package main
import "fmt"
type Queue struct {
items []int
}
func (q *Queue) Enqueue(value int) {
q.items = append(q.items, value)
}
func (q *Queue) Dequeue() int {
if len(q.items) == 0 {
panic("Queue is empty!")
}
val := q.items[0]
q.items = q.items[1:]
return val
}
func main() {
queue := Queue{}
queue.Enqueue(1)
queue.Enqueue(2)
fmt.Println(queue.Dequeue()) // Output: 1
}
🔹 Enqueue & Dequeue are O(1).
✔ A graph consists of nodes (vertices) and edges (connections).
✔ Used in social networks, maps (Google Maps), AI pathfinding.
package main
import "fmt"
type Graph struct {
adjList map[int][]int
}
func (g *Graph) AddEdge(u, v int) {
g.adjList[u] = append(g.adjList[u], v)
g.adjList[v] = append(g.adjList[v], u) // Undirected graph
}
func (g *Graph) Print() {
for key, val := range g.adjList {
fmt.Println(key, "->", val)
}
}
func main() {
graph := Graph{adjList: make(map[int][]int)}
graph.AddEdge(1, 2)
graph.AddEdge(2, 3)
graph.Print()
}
🔹 Adjacency lists (O(V+E)) are more efficient for sparse graphs.
🔹 Adjacency matrix (O(V²)) is better for dense graphs.
✔ Used in autocomplete, dictionary search, IP routing.
package main
import "fmt"
type TrieNode struct {
children map[rune]*TrieNode
isEnd bool
}
type Trie struct {
root *TrieNode
}
func NewTrie() *Trie {
return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}
func (t *Trie) Insert(word string) {
node := t.root
for _, ch := range word {
if _, found := node.children[ch]; !found {
node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
}
node = node.children[ch]
}
node.isEnd = true
}
func (t *Trie) Search(word string) bool {
node := t.root
for _, ch := range word {
if _, found := node.children[ch]; !found {
return false
}
node = node.children[ch]
}
return node.isEnd
}
func main() {
trie := NewTrie()
trie.Insert("hello")
fmt.Println(trie.Search("hello")) // Output: true
}
🔹 Efficient for prefix-based searches.
🚀 This covers key data structures in Golang! Let me know if you need more details.