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[0] 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]) = ~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]) = ~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];
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: