## 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.

Pages: 1 2

### 6 Responses to “Next To Last Item In A List”

1. Paul said

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.

```from hypothesis import given, Settings, Verbosity
import hypothesis.strategies as st
from itertools import tee, islice

def slidingwindow(iterable, n=2):
"""example: [1,2,3,4,5],3) -> (1,2,3), (2,3,4), (3,4,5)"""
its = tee(iter(iterable), n)
for i, it in enumerate(its):
next(islice(it, i, i), None)
return zip(*its)

def bf(seq, n):
"""for testing
assumption is that n cannot exceed the length of the sequence
"""
if len(seq) < n:
return None
return seq[-n]

# use list as linked list - you cannot use seq[-2] and len
def next_to_last_n(seq, n):
a = None
# slidingwindow(s,2) returns (s1,s2), (s2,s3), ....., (s_n-1, s_n)
for a, *b in slidingwindow(seq, n):
pass
return a

def next_to_last(seq):
return next_to_last_n(seq, 2)

# generate random lists of integers with random lengths, and generate a random n
@given(st.lists(st.integers(), average_size=20), st.integers(min_value=1, max_value=20),
settings=Settings(verbosity=Verbosity.normal))
def test_next_to_last_n(seq, n):
exp = bf(seq, n)
act = next_to_last_n(seq, n)
assert act == exp, "{} {} {}".format(act, exp, seq[-4:])

@given(st.lists(st.integers()))
def test_next_to_last(seq):
exp = bf(seq, 2)
act = next_to_last(seq)
assert act == exp, "{} {} {}".format(act, exp, seq[-4:])

if __name__ == "__main__":
test_next_to_last()
test_next_to_last_n()
print("OK")
```
2. Paul said

In Python. A simpler version.

```from collections import deque
def next_to_last_n(seq, n):
d = deque(seq, n) # d contains the last n values of seq
return d if len(d) == n else None
```
3. Jussi Piitulainen said

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.

```from functools import reduce

def nest(flat):
return reduce((lambda rest, elt: (elt, rest)), reversed(flat), ())

def tail(nested, n = 1):
'''Tail starting at index n.'''
for k in range(n):
_, nested = nested
return nested

def nthtolast(nested, n = 0):
'''Head of the tail of length n + 2.'''
slow, fast = nested, tail(nested, n + 2)
while fast:
_, slow = slow
_, fast = fast
elt, _ = slow
return elt

def test(n, verbose = False):
for data in ('abcdef'[:e] for e in range(7)):
if n + 1 < len(data):
x = nthtolast(nest(data), n)
assert x == data[-2-n]
( verbose and
print('nthtolast(({}), n = {}) => {}'
.format(' '.join(data), n, x)) )
else:
try:
nthtolast(nest(data), n)
assert False
except ValueError:
( verbose and
print('nthtolast(({}), n = {}) => ValueError'
.format(' '.join(data), n)) )

test(0)
test(1)
test(2)
```
4. r. clayton said

A solution in (Racket) Scheme.

5. matthew said

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.

```nfl0 n s
| n >= length s = Nothing
| otherwise = Just (s !! (length s - n - 1))

f 0 s t = g s t
f n s (_:t) = f (n-1) s t
f _ _ _ = Nothing
g (a:_) [] = Just a
g (_:s) (_:t) = g s t
nfl n s = f (n+1) s s

test0 m n =
nfl n [1..m] == nfl0 n [1..m]
test1 m = all (test0 m) [0..m+1]
test = all test1 [0..5]

main = print test
```
6. mcmillhj said
```fun next_to_last_item [] = ~1 (* return -1 on error *)
| next_to_last_item (x::y::nil) = x
| next_to_last_item (x::xs) = next_to_last_item xs

val test_valid_list = (next_to_last_item [1, 2, 3, 4, 5]) = 4
val test_empty_list = (next_to_last_item []) = ~1
val test_single_elem_list = (next_to_last_item ) = ~1

fun nth_from_last_item n [] = ~1
| nth_from_last_item n lst = let
val len = List.length lst
fun loop counter [] = ~1 (* counter goes past end of list *)
| loop counter (x::xs) = if len - counter = n then x
else loop (counter + 1) xs
in

loop 0 lst
end

val test_1st_from_last = (nth_from_last_item 1 [1, 2, 3, 4, 5]) = 5
val test_2nd_from_last = (nth_from_last_item 2 [1, 2, 3, 4, 5]) = 4

(* rewriting next_to_last_item using nth_from_last_item *)
fun next_to_last_item2 xs = nth_from_last_item 2 xs;
val test_valid_list2 = (next_to_last_item2 [1, 2, 3, 4, 5]) = 4
val test_empty_list2 = (next_to_last_item2 []) = ~1
val test_single_elem_list2 = (next_to_last_item2 ) = ~1

val all_test_pass =
List.all (fn x => x) [test_valid_list, test_empty_list, test_single_elem_list, test_1st_from_last, test_2nd_from_last, test_valid_list2, test_empty_list2, test_single_elem_list2];
```