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):

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
end
def initialize(array)
array.each {|value| append(value)}
return self
end
def append(value)
if @head
find_tail.next = LinkNode.new(value)
else
@head = LinkNode.new(value)
end
end
def 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 = LinkNode.new(value)
node.next.next = temporary
end
return node
end
def print
node = @head
puts node
while node.next
node = node.next
puts node
end
end
end

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
end
def initialize(array)
array.each {|value| append(value)}
return self
end
def append(value)
if !@head.nil?
temporary = DoubleLinkNode.new(value)
temporary.last = find_tail
find_tail.next = temporary
else
@head = DoubleLinkNode.new(value)
end
end
def 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
end
def 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
end
def 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
end
def inOrderTraversal(node = @root)
if !node.nil?
inOrderTraversal(node.left)
puts node.value
inOrderTraversal(node.right)
end
end
def preOrderTraversal(node = @root)
if !node.nil?
puts node.value
preOrderTraversal(node.left)
preOrderTraversal(node.right)
end
end
def postOrderTraversal(node = @root)
if !node.nil?
postOrderTraversal(node.left)
postOrderTraversal(node.right)
puts node.value
end
end
def 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
end
def enqueue(element)
@store << element
end
def dequeue(element)
@store.shift
end
def length
@store.length
end
def 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
end
def push(element)
@store << element
end
def pop(element)
@store.pop
end
def length
@store.length
end
def 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)
end
def 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
end
def lookup(key)
location = hash_function(key)
if @table[location]
return @table[location].assoc(key)
else
return nil
end
end
def delete(key)
hashed_key = lookup(key)
if !hashed_key.nil?
location = hash_function(key)
@table[location].delete(hashed_key)
end
end
def 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