50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
# File 'lib/dsa_visualizer/data_structures/linked_list.rb', line 50
def self.demo
Visualizer.("LINKED LIST - Core Level Visualization")
Visualizer.print_section("1. Memory Model Comparison")
ruby_code = <<~RUBY
class Node
attr_accessor :data, :next
def initialize(data)
@data = data
@next = nil
end
end
# Each node is a Ruby object
# @next stores reference to next node
RUBY
cpp_code = <<~CPP
struct Node {
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
};
// Each node allocated on heap
// next is explicit pointer
CPP
explanation = "Ruby uses object references (implicit pointers), C++ uses explicit pointers. Both achieve same structure but Ruby adds GC overhead while C++ requires manual memory management."
Visualizer.print_comparison(ruby_code, cpp_code, explanation)
Visualizer.print_section("2. Creating Linked List")
tracker = MemoryTracker.new
list = LinkedList.new
Visualizer.print_step(1, "Adding nodes: 10, 20, 30")
[10, 20, 30].each do |value|
list.append(value)
tracker.track_operation("Append", "Added node with value #{value}")
end
puts "\n" + list.visualize
puts "\nš¦ Memory Layout:"
current = list.head
index = 0
while current
puts " Node #{index}:"
puts " Address: 0x#{current.object_id.to_s(16)}"
puts " Data: #{current.data}"
puts " Next: #{current.next ? "0x#{current.next.object_id.to_s(16)}" : "nil"}"
current = current.next
index += 1
end
puts "\nš Ruby Internals:"
puts " - Each Node is a Ruby object (heap allocated)"
puts " - @next is object reference (managed by GC)"
puts " - No manual memory management needed"
puts " - Overhead: object header + reference tracking"
puts "\nš C++ Internals:"
puts " - Each Node allocated with 'new'"
puts " - next is raw pointer (8 bytes on 64-bit)"
puts " - Must manually delete nodes"
puts " - No overhead beyond struct size"
Visualizer.print_section("3. Traversal")
Visualizer.print_step(2, "Traversing to find value 20")
puts "\nProcess:"
current = list.head
position = 0
while current
if current.data == 20
puts " Position #{position}: [#{current.data}] ā FOUND!".colorize(:green)
else
puts " Position #{position}: [#{current.data}]"
end
current = current.next
position += 1
end
Comparator.compare_complexity(
"Linked List Traversal",
"O(n) - must follow references",
"O(n) - must follow pointers",
"Both require sequential access. No random access like arrays. Cache performance worse due to non-contiguous memory."
)
Visualizer.print_section("4. Insertion at Beginning")
Visualizer.print_step(3, "Inserting 5 at head")
puts "\nBefore: " + list.visualize
new_node = Node.new(5)
new_node.next = list.head
list.instance_variable_set(:@head, new_node)
tracker.track_operation("Insert", "Inserted 5 at head")
puts "After: " + list.visualize
puts "\nš Ruby Process:"
puts " 1. Create new Node object (GC manages)"
puts " 2. Set new_node.next = current head"
puts " 3. Update head reference"
puts " 4. O(1) operation"
puts "\nš C++ Process:"
puts " 1. Allocate: Node* new_node = new Node(5)"
puts " 2. Set: new_node->next = head"
puts " 3. Update: head = new_node"
puts " 4. O(1) operation"
Visualizer.print_section("5. Memory Comparison")
puts "\nš Array vs Linked List:"
puts "\nArray:"
puts " ā Contiguous memory (better cache)"
puts " ā O(1) random access"
puts " ā O(n) insertion/deletion (middle)"
puts " ā Fixed size (or expensive resize)"
puts "\nLinked List:"
puts " ā O(1) insertion/deletion (at known position)"
puts " ā Dynamic size (no resize needed)"
puts " ā O(n) random access"
puts " ā Poor cache locality"
puts " ā Extra memory for pointers/references"
tracker.print_summary
puts "\n\nšÆ Key Takeaways:".colorize(:green).bold
puts " 1. Linked lists trade random access for efficient insertion/deletion"
puts " 2. Ruby's GC simplifies memory management vs C++ manual management"
puts " 3. Non-contiguous memory means poor cache performance"
puts " 4. Each node has pointer/reference overhead"
puts " 5. Best for frequent insertions/deletions, not random access"
end
|