Why Would You Need a Linked List in Ruby?

I am learning more about linked lists, and one question that kept coming up for me is, what would you use a linked list for in Ruby or Rails programming?

This resource says that you use linked lists to avoid problems and complexity with memory allocation in C.

Basically, to create an array in C, you have to allocate memory, and you have to have some idea of how big the array will be if you want to do that. If the array gets much bigger than the original size, you will have to reallocate memory for the new elements.

Using a linked list is much simpler, because each element or node only needs memory for its content, and a pointer to the next node. Each time you add to the list, you are only adding memory for a new node. And you can add any datatype, of any size, at any node (although I’m not sure this is an issue for Ruby arrays).

But Ruby does all this for us, right?

This excellent article on sitepoint explains that yes, Ruby does this for us, and it does a pretty good job. But you still might want to use a linked list in special cases.  Allocating new memory to add more elements to an array still takes time. So if you have an array with thousands of elements, you might want to look at using a linked list for optimization if you will be adding to it.

But in most cases, it’s fine to add elements to an array, and Ruby will only resize the array if needed.  (It is faster, for larger arrays, to use push or pop instead of shift or unshift.)

Linked lists are also useful immutable data structures for functional programming, if you’re into that sort of thing.

And finally, searching an array and searching a linked list are both O(n) (aka linear) complexity.  You have to search through every element to find a specific element.  If you need a faster lookup time, you’ll need a hash table.

Ruby Array.zip

Learned a neat little trick today:

>>arr1 = [1, 2, 3, 4]
>>arr2 = [5, 6, 7, 8]
=> [[1,5],[2,6],[3,7],[4,8]]

Made me smile. It turns out you can use this to iterate over two arrays at the same time and execute a block of code. In JavaScript I’ve gotten used to using a for loop and then indexing using the iterator:

for (i = 0; i < arr.length; i++) {
if arr1[i] == arr2[i]
//do something...
//close brackets etc

But Ruby doesn’t really have a for loop that works that way. Array.zip() to the rescue!

>>arr1.zip(arr2).each do |x, y|
>>if y == x+4
>>puts "awesome!"

Everything looks like a nail

I finished the code kata I blogged about yesterday.  I won’t share the solution since others might want to try it.  But it’s interesting how my thought process was shaped by the challenge to try not to use a nested loop.  Because of this, I didn’t think about the simplest solution, or the most efficient solution.  I thought about how I could do it without using a nested loop.  I approached it as a coding challenge rather than a math challenge, which is what it actually was.

And once I solved it as a math problem, rather than as a coding problem, the complexity dropped from exponential to linear.  So the code was improved by stepping outside of the coding domain.

Benchmarking my Code

I joined Codewars.com last week and I’m a little addicted.  The coding challenges are a good motivation to learn new methods and techniques.

I’ve been working on this kata today.  The challenge states “props if you do it without a nested loop,”  so I tried a few different ways.  After a little noodling around, I decided on the strategy of creating an array of arrays, passing a block to Array.new which would insert the proper values as the array was created.  Then Array.reduce would sum it up for me neat and clean.

I had trouble coming up with the code to initialize the arrays though.  I tried Array.new(weeks) { Array.new(days) } but couldn’t figure out how to increment properly as I went along.  So I just started hacking away, keeping the original idea of creating an array of arrays, inserting the values, and then using reduce at the end.  Here is my first function that passed the tests:

with a loopAs you can see I ended up with a nested loop.  But the tests passed, so I hit submit!

Apparently there’s a cutoff time.  It took more than 6 seconds to complete the tests to pass submission.  So I tried benchmarking the code:

benchmarking benchmarks with a loopHoly crap!  Look at the jump in time.  I know enough about Big O to know this is not good.

So I simplified a little bit:

Screenshot from 2015-11-01 18:44:17No need to create all those arrays, so I just pulled them out.  The results, with the same parameters passed to Benchmark, were:

Benchmarking the sumMuch better.  But although it’s passing the first round of tests, it’s still not passing the 6 second cutoff time for the submit tests, so I’ll keep trying.

LOAD_PATH problem solved, another problem pops up

I’ve been working on the hangman project at the Odin Project.

I had a basic working program. I decided to break it up into some different files to get a better understanding of how classes and files interact with each other.

I had a lot of trouble with getting the dictionary to work once I did this. The game loads a word from a text file containing a long list of random words. Once I put the game into a couple different files, I couldn’t get the text file to load anymore. I was finally able to figure out a solution, although I still don’t completely understand what happened, once I read this blog post.

It seems that once a program has been executed, the file path for that program is set. So when I changed the file structure, the program was still looking for the dictionary (the “5desk.txt” file) in the same old place and couldn’t find it. This is strange, because I didn’t move the dictionary file, just split the ruby code into two different files. I added the following to my code:

File.join(File.expand_path(File.dirname(__FILE__)), "..", "5desk.txt")

and now things work.

I am still not 100% clear on how this works (more like 60%), so if any readers have reading materials or comments that can help me understand, please share!

Once I got the dictionary to work, I had to change the ruby code a little to reference the right instance variables. As it currently stands, the program runs, but the turns are borked. Instead of the turns variable counting up from 0, I can only run one game round, the turns variable gets set to the length of the word, and the program exits. I have pushed the code to github here, and I’ll copy some of it below since the github code will change in the future.


File.join(File.expand_path(File.dirname(__FILE__)), "..", "5desk.txt")
require_relative "lib/hangman.rb"
require_relative "lib/game_engine.rb"

play = GameEngine.new


require_relative "hangman.rb"

class GameEngine

def initialize
@game = Game.new
@turns = 0
@score = 0

attr_accessor :turns
attr_accessor :score
attr_accessor :game

def take_guess
puts "Guess a letter!"
print ">"
input = gets.chomp.downcase
i = 0
while i <= @game.word.length
if input == @game.word[i]
puts "The word contains #{input}!"
@game.word_board[i] = input
i += 1
i += 1
@turns += 1
print "#{@game.word_board.join} Guesses: #{@game.guesses.join} "

def play_game
print @game.word.join+"n"
print @game.word_board.join
while @turns < @game.word.length
puts " Turn #{@turns}"
#end class

require_relative "game_engine.rb"

puts "Hangman initialized"

class Game

def initialize
puts "New game initialized"
@word = pick_random.downcase.split(//).slice(0..-2)
@word_board = []
@guesses = []

attr_accessor :word_board
attr_accessor :word
attr_accessor :guesses

def pick_random
chosen_line = nil
File.foreach("5desk.txt").each_with_index do |line, number|
chosen_line = line if rand < 1.0/(number+1)
return chosen_line

def create_word_board
@word.length.times do
@word_board.push("_ ")