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.)
attr_accessor :value, :next_node, :list
def initialize(value, next_node=nil)
@value = value
@list = 
@next_node = next_node
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
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)
new_node = LinkedListNode.new(array.pop)
new_node = LinkedListNode.new(array.pop, node)
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.
def numberify(node, array=@list)
=> [7, 1, 6]
=> [5, 9, 2]
Once I had that method, I could reverse those arrays, then turn them into numbers.
So to sum both lists:
def sum(lista, listb)
return lista.reverse_n_join + listb.reverse_n_join
p sum(list1, list2)
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.
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.