Next To Last Item In A List
July 28, 2015
We begin with the function that gets the next-to-last item in a list; we return #f
if the list is too small, but depending on your application you may want to raise an error instead:
(define (next-to-last xs)
(cond ((or (null? xs) (null? (cdr xs))) #f)
((null? (cddr xs)) (car xs))
(else (next-to-last (cdr xs)))))
We have three test cases: list with no items, list with one item, and list with more items:
(define (test-next-to-last)
(assert (next-to-last '()) #f)
(assert (next-to-last '(1)) #f)
(assert (next-to-last '(1 2)) 1)
(assert (next-to-last '(1 2 3)) 2)
(assert (next-to-last '(1 2 3 4)) 3)
(assert (next-to-last '(1 2 3 4 5)) 4))
As always, no news is good news:
> (test-next-to-last)
The nth-to-last
function is a little bit harder. First we run through n items, reporting an error if there aren’t enough. Then we keep two pointers n items apart, reporting the item at the trailing pointer when the leading pointer reaches the end of the list:
(define (nth-to-last n xs)
(if (not (positive? n)) #f
(let loop ((n n) (leading xs))
(if (null? leading) #f
(if (< 1 n) (loop (- n 1) (cdr leading))
(let loop ((trailing xs) (leading (cdr leading)))
(if (null? leading) (car trailing)
(loop (cdr trailing) (cdr leading)))))))))
Testing is a little bit harder; because we want to test lots of combinations of n and xs, we have to have a way to generate them with known results:
(define (test-nth-to-last)
(assert (nth-to-last 0 '()) #f)
(assert (nth-to-last 0 '(1)) #f)
(do ((n 1 (+ n 1))) ((= n 7))
(do ((x 1 (+ x 1))) ((= x 7))
(let ((r (if (< x n) #f (- x n -1))))
(assert (nth-to-last n (range 1 (+ x 1))) r)))))
Notice that we had to test the case n = 0 separately, because the calculation of r in (- x n -1)
does the wrong thing. As before, no news is good news:
> (test-nth-to-last)
We used assert
and range
from the Standard Prelude. You can run the program at http://ideone.com/3HbSOt.
In Python. I assumed that n cannot exceed the length of the list. I did use a list for the linked list, but did not use len and slicing.
For testing I use the hopthesis library.
In Python. A simpler version.
With Lisp-style lists in Python, and a verbose option in the test function for checking that no news is any news at all.
Backwards indexing has always been tricky for me, including this time. Oh, and I let Python raise an exception when the list is too short, and then I test for that.
A solution in (Racket) Scheme.
nfl0 is the inefficient but clear functional specification, nfl is the implementation (using the double pointer approach). Both assume n is non-negative.
Test just compares the two functions over a suitable set of inputs.