A Blog Post About Linked Lists

sometimes, there is no clever and informative post title pun

There comes a time in every programmer’s life where they must consume Cracking the Coding Interview. That time has come for me, and now I’m all wrapped up in data structures and algorithms.

Today, I’ll show you some things I’ve done with Singly Linked Lists.

First, I made some. It turns out you won’t always need a LinkedList class that stores the entire list — if you can reference the bottom node, it’ll know about the node above it (which in turn will know about the node above it). (Eventually, we’ll use the self.list attribute from the initializer to store more info, but we don’t need it.)

class LinkedListNode
attr_accessor :value, :next_node, :list
 def initialize(value, next_node=nil)
@value = value
@list = []
@next_node = next_node
end
 def print
p @value
if @next_node
@next_node.print
end
end
end

Then, because I’d heard this was a common interview question, I decided to write up a way to reverse them. I really dig recursion when it behaves itself.

def reverse(bottom_node, previous=nil)
head = bottom_node.next_node
bottom_node.next_node = previous
if head
reverse(head, bottom_node)
else
bottom_node
end
end

Then, I decided I wanted to see if I could use recursion to make a linked list out of an array. Answer? Yes I can!

def generate(array, node=nil)
if array.empty?
node
elsif node.nil?
new_node = LinkedListNode.new(array.pop)
generate(array, new_node)
else
new_node = LinkedListNode.new(array.pop, node)
generate(array, new_node)
end
end

Finally, I decided to actually tackle one of the problems in the book. The problem was as follows:

You have two numbers represented by a linked list, where each node contains a single digit. The digit are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
(7->1->6) + (5->9->2) => (9->1->2)
617 + 295 = 912

First, I made the two lists we need to make the problem.

node1 = LinkedListNode.new(6)
node2 = LinkedListNode.new(1, node1)
list1 = LinkedListNode.new(7, node2)
node3 = LinkedListNode.new(2)
node4 = LinkedListNode.new(9, node3)
list2 = LinkedListNode.new(5, node4)

At last, it was time to use my self.list attribute to store the entire list as an array.

class LinkedListNode
 def numberify(node, array=@list)
array.push(self.value)
if @next_node
@next_node.numberify(self, array)
end
end
end
list1.numberify(list1)
p list1.list
=> [7, 1, 6]
list2.numberify(list2)
p list2.list
=> [5, 9, 2]

Once I had that method, I could reverse those arrays, then turn them into numbers.

class LinkedListNode
def reverse_n_join
self.list.reverse.join(‘’).to_i
end
end

So to sum both lists:

def sum(lista, listb)
lista.numberify(lista)
listb.numberify(listb)
return lista.reverse_n_join + listb.reverse_n_join
end
p sum(list1, list2)
=> 912

But finally, I have to turn that integer back into a linked list! Luckily, I made that “generate” method earlier. I did make that for arrays, so I’ll need to coerce the data a few times to make it work here.

generate(sum(list1,list2).to_s.split(‘’).map(&:to_i)).print
=>9
=>1
=>2

Phew! I’m sure there is some refactoring I could be doing, but for now, I’ll leave you with a gist of all that code.

does anyone else get Missy Elliot’s “Work It” stuck in their head every time they use the reverse method?