## Next To Last Item In A List

### July 28, 2015

Today’s exercise is a reminder about the importance of writing good test code. We have two tasks. The first is to extract the next-to-last item from a linked list; for instance, given the list (1 2 3 4 5) the next-to-last item is 4. The second task is to extract the nth-from-last item from a linked last; for instance, given the same list, the second-from-last item is 4. In addition to writing the two functions, you should write test code that exercises the functions thoroughly.

Your task is to write the two functions and test code. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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];
```