# Ruby Data Structures and Algorithms — Ruby Deep Dive [04]

Let’s dive into the different data structures and algorithms provided by most programming languages, and some specific to ruby, showing the ease of use if we follow the Ruby-way.

# Before We Begin

Big O complexity, also known as Big O notation, is a mathematical notation used in computer science to describe the performance or complexity of an algorithm. Specifically, it describes the worst-case scenario for the time or space an algorithm needs as the input size grows.

## Key points about Big O complexity:

- It expresses the upper bound of an algorithm’s growth rate.
- It focuses on the dominant term as the input size approaches infinity.
- Common Big O notations include:

- O(1): Constant time
- O(log n): Logarithmic time
- O(n): Linear time
- O(n log n): Linearithmic time
- O(n²): Quadratic time
- O(2^n): Exponential time

4. It helps compare algorithms’ efficiency and scalability.

5. It ignores constants and lower-order terms.

Big O notation is crucial for analyzing and optimizing algorithms, especially when dealing with large datasets.

# Why Data Structures and Algorithms (DSA)?

Frameworks and libraries are built on top of data structures and algorithms, and they keep getting updated. The only foolproof plan to stay updated is to understand the foundational principles upon which these updates and new tools are based. This is why learning Data Structures and Algorithms is crucial.

# Characteristics of the Best Code:

**Readable**: Easy to understand and maintain.**Memory Efficient**: Uses the least amount of memory necessary.**Time Efficient**: Executes as quickly as possible.

# Important Data Structures:

- Arrays
- Hashes
- Sets
- Strings
- Symbols
- Ranges
- Structs
- OpenStructs
- Queues
- Stacks
- Linked Lists
- Trees

# Important Algorithms:

- Sorting
- Dynamic Programming
- BFS (Breadth-First Search) + DFS (Depth-First Search)
- Recursion

# Why Data Structures?

Data structures are used to store data on our computers efficiently.

# Where Data Gets Stored:

**Permanent**: Storage devices (like hard drives).**Temporary**: RAM (Random Access Memory).

# Who Processes This Data?

**CPU**: The central processing unit processes the data.

# Common Operations:

- Insertion
- Traversal
- Deletion
- Searching
- Sorting
- Access

# Data Structures in Ruby

# 1. Arrays

Arrays are sequential data structures stored in order in memory.

## Usage:

- Fast for finding elements, push/pop operations.
- Slow for insert/delete operations in the middle.

## Big O Complexity:

- Access: O(1)
- Search: O(n)
- Insertion: O(n)
- Deletion: O(n)

## Example:

`# Creating an array`

arr = [1, 2, 3, 4, 5]

# Accessing elements

puts arr[2] # Output: 3

# Adding elements

arr.push(6) # [1, 2, 3, 4, 5, 6]

arr << 7 # [1, 2, 3, 4, 5, 6, 7]

# Removing elements

arr.pop # [1, 2, 3, 4, 5, 6]

arr.shift # [2, 3, 4, 5, 6]

# Iterating over elements

arr.each do |element|

puts element

end

# Multidimensional array (matrix)

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

puts matrix[1][2] # Output: 6

# 2. Hashes

Hashes (also known as hash maps) are key-value pairs, offering fast lookups.

## Usage:

- Ideal for quick lookups and associative arrays.

## Big O Complexity:

- Access: O(1)
- Search: O(1)
- Insertion: O(1)
- Deletion: O(1)

## Example:

`# Creating a hash`

char_count = { 'a' => 1, 'b' => 2, 'c' => 3 }

# Accessing elements

puts char_count['b'] # Output: 2

# Adding elements

char_count['d'] = 4

# Removing elements

char_count.delete('a')

# Iterating over elements

char_count.each do |key, value|

puts "#{key}: #{value}"

end

# 3. Sets

Sets are collections of unordered values with no duplicates, implemented using hashes under the hood.

## Usage:

- Useful for testing membership, eliminating duplicates.

## Big O Complexity:

- Access: O(1)
- Search: O(1)
- Insertion: O(1)
- Deletion: O(1)

## Example:

`require 'set'`

# Creating a set

set = Set.new([1, 2, 3, 4, 5])

# Adding elements

set.add(6)

# Removing elements

set.delete(2)

# Checking membership

puts set.include?(3) # Output: true

# Iterating over elements

set.each do |element|

puts element

end

# 4. Strings

Strings are sequences of characters, essentially arrays of characters.

## Usage:

- Useful for text manipulation.

## Big O Complexity:

- Access: O(1)
- Search: O(n)
- Insertion: O(n)
- Deletion: O(n)

## Example:

`# Creating a string`

str = "Hello, world!"

# Accessing characters

puts str[7] # Output: w

# Adding to a string

str += " How are you?"

# Removing from a string

str.slice!(0, 5)

# Iterating over characters

str.each_char do |char|

puts char

end

# 5. Symbols

Symbols are immutable, reusable constants represented internally by an integer value.

## Usage:

- Useful for identifiers and keys, more memory efficient than strings.

## Big O Complexity:

- Symbols are generally more efficient in memory usage and comparison than strings due to their immutability.

## Example:

`# Creating symbols`

symbol = :my_symbol

# Comparing symbols

puts :a == :a # Output: true

puts :a == :b # Output: false

# 6. Ranges

Ranges represent an interval of values.

## Usage:

- Useful for creating sequences and checking inclusion.

## Big O Complexity:

- Access: O(1)
- Search: O(n) for inclusion checks
- Insertion: O(n) (but generally not used for insertion)
- Deletion: O(n) (but generally not used for deletion)

## Example:

`# Creating a range`

range = (1..10)

# Iterating over a range

range.each do |value|

puts value

end

# Checking inclusion

puts range.include?(5) # Output: true

# 7. Structs

Structs are a convenient way to bundle related attributes together using accessor methods.

## Usage:

- Useful for creating simple data structures without defining a full class.

## Big O Complexity:

- Access: O(1)
- Insertion: O(1)
- Deletion: O(1)

## Example:

`# Defining a struct`

Person = Struct.new(:name, :age)

# Creating a new struct instance

person = Person.new("Alice", 30)

# Accessing attributes

puts person.name # Output: Alice

puts person.age # Output: 30

# Modifying attributes

person.age = 31

puts person.age # Output: 31

# 8. OpenStructs

OpenStructs provide a flexible data structure similar to a hash but with object-like access.

## Usage:

- Useful for quick and flexible data structures.

## Big O Complexity:

- Access: O(1)
- Insertion: O(1)
- Deletion: O(1)

## Example:

`require 'ostruct'`

# Creating an OpenStruct

person = OpenStruct.new(name: "Alice", age: 30)

# Accessing attributes

puts person.name # Output: Alice

puts person.age # Output: 30

# Modifying attributes

person.age = 31

puts person.age # Output: 31

# 9. Queues

Queues follow the FIFO (First In, First Out) principle. Ruby does not have a built-in Queue class, but it can be implemented using an array.

## Usage:

- Useful for processing tasks in the order they arrive.

## Big O Complexity:

- Access: O(1)
- Insertion: O(1)
- Deletion: O(1)

## Example:

`class Queue`

def initialize

@elements = []

end

def enqueue(element)

@elements.push(element)

end

def dequeue

@elements.shift

end

def peek

@elements.first

end

def empty?

@elements.empty?

end

end

# Using the queue

queue = Queue.new

queue.enqueue(1)

queue.enqueue(2)

puts queue.dequeue # Output: 1

puts queue.peek # Output: 2

puts queue.empty? # Output: false

# 10. Stacks

Stacks follow the LIFO (Last In, First Out) principle. Ruby does not have a built-in Stack class, but it can be implemented using an array.

## Usage:

- Useful for managing nested structures or undo operations.

## Big O Complexity:

- Access: O(1)
- Insertion: O(1)
- Deletion: O(1)

## Example:

`class Stack`

def initialize

@elements = []

end

def push(element)

@elements.push(element)

end

def pop

@elements.pop

end

def peek

@elements.last

end

def empty?

@elements.empty?

end

end

# Using the stack

stack = Stack.new

stack.push(1)

stack.push(2)

puts stack.pop # Output: 2

puts stack.peek # Output: 1

puts stack.empty? # Output: false

# 11. Linked Lists

Ruby does not have a built-in LinkedList class, but it can be implemented.

## Usage:

- Useful for efficient insertion and deletion operations.

## Big O Complexity:

- Access: O(n)
- Search: O(n)
- Insertion: O(1)
- Deletion: O(1)

## Example:

`class Node`

attr_accessor :value, :next_node

def initialize(value)

@value = value

@next_node = nil

end

end

class LinkedList

def initialize

@head = nil

end

def append(value)

if @head.nil?

@head = Node.new(value)

else

current = @head

current = current.next_node until current.next_node.nil?

current.next_node = Node.new(value)

end

end

def delete(value)

return if @head.nil?

if @head.value == value

@head = @head.next_node

return

end

current = @head

while current.next_node && current.next_node.value != value

current = current.next_node

end

current.next_node = current.next_node.next_node if current.next_node

end

def display

current = @head

while current

print "#{current.value} -> "

current = current.next_node

end

puts "nil"

end

end

# Using the linked list

list = LinkedList.new

list.append(1)

list.append(2)

list.append(3)

list.display # Output: 1 -> 2 -> 3 -> nil

list.delete(2)

list.display # Output: 1 -> 3 -> nil

# 12. Trees

Ruby does not have a built-in Tree class, but it can be implemented.

## Usage:

- Useful for hierarchical data structures, like file systems.

## Big O Complexity:

- Access: O(log n)
- Search: O(log n)
- Insertion: O(log n)
- Deletion: O(log n)

## Example:

`class TreeNode`

attr_accessor :value, :left, :right

def initialize(value)

@value = value

@left = nil

@right = nil

end

end

class BinaryTree

def initialize

@root = nil

end

def insert(value)

if @root.nil?

@root = TreeNode.new(value)

else

insert_rec(@root, value)

end

end

def insert_rec(node, value)

if value < node.value

if node.left.nil?

node.left = TreeNode.new(value)

else

insert_rec(node.left, value)

end

else

if node.right.nil?

node.right = TreeNode.new(value)

else

insert_rec(node.right, value)

end

end

end

def inorder(node = @root)

return if node.nil?

inorder(node.left)

print "#{node.value} "

inorder(node.right)

end

end

# Using the binary tree

tree = BinaryTree.new

tree.insert(10)

tree.insert(5)

tree.insert(15)

tree.inorder # Output: 5 10 15

# Conclusion

Understanding data structures and algorithms is crucial for writing efficient and maintainable code. Ruby provides a rich set of built-in data structures and methods that allow you to solve complex problems effectively. By mastering these fundamental concepts, you’ll be better equipped to handle any programming challenge that comes your way.