# Implementing Data Structures in Ruby

A good way to prepare for a software engineering interview is to implement data structures in the language of your choice. It’s a great way to practice coding in the language you plan to do your technical interview in and it helps to reinforce your understanding of the different data structures. You could really impress your interviewer by using one of these data structures in a white boarding problem if appropriate.

In this blog, I’ll do a basic implementation of the following data structures in Ruby.

**Linked List****Doubly Linked List****Binary Search Tree****Queue****Stack****Hash Table**

Before I get started:

**What are data structures?**

Basically, data structures are efficient ways to store, organize, read, and manipulate data.

Wikipedia’s definition:In computer science, a data structure is a data organization, management and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

Link: https://en.wikipedia.org/wiki/Data_structure

If you’re a visual learner like me, you might want to check out these websites that provide **visual representations **of different data structures (and algorithms):

- https://visualgo.net/en
- https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
- https://www.quora.com/How-do-I-visualize-some-basic-data-structures-and-algorithms * More comprehensive list of resources in this link

**Other study tools:**

# Linked Lists

**What’s a Linked List?**

“A Linked List is a data structure consisting of a group of nodes, which together represent a sequence. Under the simplest form, each vertex is composed of a data and a reference (link) to the next vertex in the sequence.” — VisuAlgo

**Pros/Cons**

- You don’t need to know how many items you have
- Insertion & Removal are constant time
- Single-linked list uses less RAM than a double-linked list

**Use Cases:**

- If you need to make lots of insertions and/or deletions into the middle of your list
- If you aren’t moving “backwards” in the list
- A single linked list is almost always the appropriate data structure for implementing a Stack or Queue
- Example: Implementing a to-do list manager.

**Big O:**

## The Link Node

`class LinkNode`

attr_accessor :next

attr_reader :value

def initialize(value)

@value = value

@next = nil

end

end

## The Linked List

class LinkedList

def initialize()

@head = nil

enddef initialize(array)

array.each {|value| append(value)}

return self

enddef append(value)

if @head

find_tail.next = LinkNode.new(value)

else

@head = LinkNode.new(value)

end

enddef find_tail

node = @head

while node.next

node = node.next

end

return node

enddef find(value)

node = @head

while node.next && node.value != value

node = node.next

end

if !node.next && node.value != value

return false

else

return node

end

enddef find_before(value)

node = @head

while node.next && node.next.value != value

node = node.next

end

if !node.next

return false

else

return node

end

enddef append_after(target,value)

node = find(target)

if node != false

temporary = node.next

node.next = LinkNode.new(value)

node.next.next = temporary

end

return node

enddef print

node = @head

puts node

while node.next

node = node.next

puts node

end

endend

# Doubly Linked List

**What’s a Doubly Linked List?**

“A Doubly Linked List (DLL) is a linked list that contains an extra pointer, typically called

previous pointer, together with next pointer and data which are there in singly linked list.” — Geeks for Geeks

**Pros/Cons**

- Good for lists that have to be kept sorted, especially if elements are added and deleted after the list has been initially populated
- Removing an item from the list means, changing the value of the pointers which point to the item. No need again to re-build the list.

**Use Cases:**

- Traversing a list bidirectionally

**Big O:**

Link: https://www.quora.com/What-are-the-advantages-of-a-single-linked-list-over-the-double-linked-list

## The Double Link Node

`class DoubleLinkNode`

attr_accessor :value, :next, :last

def initialize(value)

@value = value

@next = nil

@last = nil

end

end

## The Doubly Linked List

class DoublyLinkedList

def initialize()

@head = nil

enddef initialize(array)

array.each {|value| append(value)}

return self

enddef append(value)

if !@head.nil?

temporary = DoubleLinkNode.new(value)

temporary.last = find_tail

find_tail.next = temporary

else

@head = DoubleLinkNode.new(value)

end

enddef find_tail

node = @head

while node.next

node = node.next

end

return node

end

def find(value)

node = @head

while node.next && node.value != value

node = node.next

end

if !node.next && node.value != value

return false

else

return node

end

end

def find_before(value)

node = @head

while node.next && node.next.value != value

node = node.next

end

if !node.next

return false

else

return node

end

end

def append_after(target,value)

node = find(target)

if node != false

temporary = node.next

node.next = DoubleLinkNode.new(value)

node.next.last = node

node.next.next = temporary

node.next.next.last = node.next

end

return node

end

def append_before(target,value)

node = find(target)

if node != false

temporary = node.last

node.last = DoubleLinkNode.new(value)

node.last.last = temporary

node.last.last.next = node.last

node.last.next = node

end

return node

enddef print

node = @head

puts node

while node.next

node = node.next

puts node

end

end

end

# Binary Search Tree

**What’s a Tree?**

“Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees are hierarchical data structures.” — Geeks for Geeks

**What’s a Binary Tree?**

A tree where each element has a max of 2 children

**What’s a Binary Search Tree?**

A binary tree with the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.

• The right subtree of a node contains only nodes with keys greater than the node’s key.

• The left and right subtree each must also be a binary search tree.

— Geeks for Geeks

**Use Cases:**

“One reason to use binary tree or tree in general is for the things that form a hierarchy.”

• “They are useful in File structures where each file is located in a particular directory and there is a specific hierarchy associated with files and directories.”

• “Another example where Trees are useful is storing heirarchical objects like JavaScript Document Object Model considers HTML page as a tree with nesting of tags as parent child relations.” — Geeks for Geeks

**Big O:**

## The Tree Node

`class TreeNode`

attr_accessor :value, :left, :right

def initialize(value)

@value = value

@left = nil

@right = nil

end

end

## The Binary Search Tree

class BinarySearchTree

def initialize()

@root = nil

enddef insert(val,node=@root)

if !@root.nil?

if !node.nil?

if val < node.value

if node.left.nil?

node.left = TreeNode.new(val)

else

insert(val, node.left)

end

elsif val > node.value

if node.right.nil?

node.right = TreeNode.new(val)

else

insert(val, node.right)

end

elsif val = node.value

return false

end

end

elsif @root.nil?

@root = TreeNode.new(val)

end

enddef inOrderTraversal(node = @root)

if !node.nil?

inOrderTraversal(node.left)

puts node.value

inOrderTraversal(node.right)

end

enddef preOrderTraversal(node = @root)

if !node.nil?

puts node.value

preOrderTraversal(node.left)

preOrderTraversal(node.right)

end

enddef postOrderTraversal(node = @root)

if !node.nil?

postOrderTraversal(node.left)

postOrderTraversal(node.right)

puts node.value

end

enddef search(val, node = @root )

if !node.nil?

if val < node.value

search(val, node.left)

elsif val > node.value

search(val, node.right )

else

return node

end

else

return nil

end

end

end

**Note: **You should be comfortable traversing trees in any way (beyond the simple pre/post/in-order traversals). Interviewers could ask you to print tree values in any way.

**Queue**

**What’s a Queue?**

“A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).” — Geeks for Geeks

**Use Cases:**

- Queue is used in BFS(Breadth First Search) algorithm
- When data is transferred asynchronously
- Queue of people at any service point such as ticketing etc.
- Queue of processes in OS.
- In networking printers e.g. if a number of people are printing documents from the same printer machine
- Queue of air planes waiting for landing instructions.

Link: https://www.quora.com/What-are-some-real-world-applications-of-a-queue-data-structure-1

**Big O:**

## The Queue (using an array)

class Queue

def initialize

@store = Array.new

enddef enqueue(element)

@store << element

enddef dequeue(element)

@store.shift

enddef length

@store.length

enddef empty?

@store.empty?

end

end

# Stack

**What’s a Stack?**

“Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).” — Geeks for Geeks

**Use Cases:**

- Stack is used in DFS(Depth First Search) algorithm
- To reverse a word. You push a given word to stack — letter by letter — and then pop letters from the stack.
- Undo\redo operation in word processors
- Used in IDEs to check for proper parenthesis matching (Syntax Parsing)

Link: https://www.quora.com/What-are-the-real-life-applications-of-stack-data-structure

Link: https://www.quora.com/What-are-the-real-world-examples-of-stacks

**Big O:**

## The Stack (using an array)

class Stack

def initialize

@store = Array.new

enddef push(element)

@store << element

enddef pop(element)

@store.pop

enddef length

@store.length

enddef empty?

@store.empty?

end

end

# Hash Table

**What’s a Hash Table?**

“Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends of the efficiency of the hash function used.” — Geeks for Geeks

**The Use Cases:**

- Used for fast data lookup

**Big O:**

## The Hash Table

class HashTable

def initialize(bucket_amount = 20)

@size = bucket_amount

@table = Array.new(bucket_amount)

enddef insert(key,value)

location = hash_function(key)

@table[location] ||= []

# if @table[location].find { |hash_pair| hash_pair.first == key }

if @table[location].assoc(key)

return "Key exists"

else

@table[location] << [key, value]

end

enddef lookup(key)

location = hash_function(key)

if @table[location]

return @table[location].assoc(key)else

return nil

end

enddef delete(key)

hashed_key = lookup(key)

if !hashed_key.nil?

location = hash_function(key)

@table[location].delete(hashed_key)

end

enddef hash_function(key)

return key.hash % @size

end

Note:

`@table[location].assoc(key) `**is the same as **

@table[location].find {|hash_pair| hash_pair.first == key}

*Ruby has Hash Tables built in