Adventures in linked lists, part 2: converting an edge case into a typical case
To follow up on a previous post, here is what we learned:
Linked lists are made up of a series of "pair" objects, each of which holds a value and a pointer to the next pair. (At the end of a linked list, the pointer points to nil.)
Here is an example of a linked list consisting of two Pair objects, each consisting of an integer and a pointer to the next object.
class Pair
attr_accessor :a, :b
def initialize(a, b)
@a = a
@b = b
end
end
ll = Pair.new(4, Pair.new(5, nil))
Why use a linked list instead of an array? With a linked list, the list elements do not need to be stored all together in the same place in memory, which means you can add to or remove from the list without having to reorganize/reallocate memory for the whole list.
We wrote some functions to manipulate the linked lists, such as append, prepend, and insert. Then Jeremy asked us to write a filter method that would remove any elements with a given value from the list, like so:
Our initial approach was to iterate through the linked list with a while loop, keeping track of the current pair object and the previous pair object (initially set to the first pair object). Anytime we encountered the given value, take the previous element's pointer and point it to the next element's value.
def filter(ll, val)
first = ll
previous = ll
while ll != nil
if ll.a == val
previous.b = ll.b
else
previous = ll
end
ll = ll.b
end
first
end
That worked -- unless the first element had a value that we wanted to filter out. Meaning that we get these results from these inputs (written as an array for readability):
input [3, 4, 5, 4] -> filter 4 -> return [3, 5]
input [4, 3, 5, 6] -> filter 4 -> return [4, 3, 5, 6] (fail.)
The bug was that "previous" was set to the first pair object, so when the function found the matching value at the first pair, it would take the "previous" pointer, i.e. the current pointer, and point it to the next pair, i.e. what it was already pointing to. The result was that the first pair wouldn't get filtered out.
We added an if statement at the beginning of the function to catch the cases in which the first element was one we wanted to filter out. If that was the case, we'd toss the first element and enter the while loop with the modified linked list.
if ll.a == val
ll = ll.b
end
Our modified function gave these results:
input [3, 4, 5, 4] -> filter 4 -> return [3, 5]
input [4, 3, 5, 6] -> filter 4 -> return [3, 5, 6]
input [4, 4, 5, 6] -> filter 4 -> return [4, 5, 6] (fail.)
The problem was that after removing the first element from the list, we were running into the same bug that we had originally: our new first element was being passed into the loop that doesn't filter out the first element of a list.
So we changed our initial if statement to a while loop and added a statement to return nil if the pointer pointed to nil (in other words, if the list was nil or it was made up of only elements to be filtered out).
while ll.a == val
return nil if ll.b == nil
ll = ll.b
end
Jeremy also pointed out that if an element on the list caused the program to exit the first while loop, then it couldn't be the filter value. We added a line before the second while loop to skip having to check it again.
This way, we got all of these examples to pass:
input [3, 4, 5, 4] -> filter 4 -> return [3, 5]
input [4, 3, 5, 6] -> filter 4 -> return [3, 5, 6]
input [4, 4, 5, 6] -> filter 4 -> return [5, 6]
input [4, 4] -> filter 4 -> return nil
This is the solution that ended up in the second file of our gist. It worked, but we didn't like having to tack on two conditionals just for the one case where the first element was what we wanted to filter out. So Jeremy showed us a clever alternative approach to managing the edge case: convert it into a typical case.
Our initial solution failed only when the first element was one we wanted to filter out. Instead of writing conditionals to check for that case, we could simply prepend a dummy pair object to the beginning of the list, turning our special-case first element into a regular-case element. This is the code from the first file of the gist:
def filter(ll, val)
fake_ll = Pair.new(424242, ll)
previous = fake_ll
while ll != nil
if ll.a == val
previous.b = ll.b
else
previous = ll
end
ll = ll.b
end
fake_ll.b
end
Whatever the value of the dummy pair object is, it doesn't get filtered out, so at the end of the filter loop, all you have to do it return the rest of the list after the first element. Ingenious!
