Persistent Lists
Persistent lists are immutable data structures where elements cannot be modified after creation. Operations on persistent lists create new instances with the desired changes while preserving the original list. This ensures that the original list remains unchanged, making persistent lists ideal for functional programming.
Persistent lists can be implemented using various approaches, such as linked lists or trees.
Below is the Ruby program to implement a persistent list using a linked list structure:
class ListNode
attr_accessor :value, :next
def initialize(value, next_node = nil)
@value = value
@next = next_node
end
end
class PersistentList
attr_reader :head
def initialize(head = nil)
@head = head
end
def prepend(value)
new_head = ListNode.new(value, @head)
PersistentList.new(new_head)
end
def to_a
result = []
current = @head
while current
result << current.value
current = current.next
end
result
end
end
list1 = PersistentList.new
list2 = list1.prepend(1)
list3 = list2.prepend(2)
list4 = list3.prepend(3)
puts list1.to_a.inspect # => []
puts list2.to_a.inspect # => [1]
puts list3.to_a.inspect # => [2, 1]
puts list4.to_a.inspect # => [3, 2, 1]
Output:
How to Implement Data Structures in Ruby?
Data structures are fundamental components of any programming language, allowing developers to organize and manipulate data efficiently. In Ruby, a versatile and expressive language, implementing various data structures is straightforward. In this article, we’ll explore how to implement common data structures such as arrays, linked lists, stacks, queues, trees, graphs, and hashmaps in Ruby. The article focuses on discussing data structures in Ruby.
Table of Content
- Singly-Linked Lists
- Doubly-Linked Lists
- Circular Linked Lists
- Queues
- Stack
- Hash Tables
- Sets
- Binary Trees
- AVL Trees (Adelson-Velsky and Landis Trees)
- Graphs
- Persistent Lists
Contact Us