Nth Item In A Linked List

April 10, 2020

Here’s the program the student was having trouble writing:

(define (nth n xs)
  (if (null? xs)
      (error 'nth "out of range")
      (if (zero? n) (car xs)
          (nth (- n 1) (cdr xs)))))

The first if reports an error, the second if either returns the result or calls the function recursively. Here are some examples:

> (nth -1 '(0 1 2 3 4))
Exception in nth: out of range
Type (debug) to enter the debugger.
> (nth 0 '(0 1 2 3 4))
0
> (nth 1 '(0 1 2 3 4))
1
> (nth 2 '(0 1 2 3 4))
2
> (nth 3 '(0 1 2 3 4))
3
> (nth 4 '(0 1 2 3 4))
4
> (nth 5 '(0 1 2 3 4))
Exception in nth: out of range
Type (debug) to enter the debugger.

You can run the program at https://ideone.com/U99jt9.

Pages: 1 2

11 Responses to “Nth Item In A Linked List”

  1. John Cowan said

    Outside academia, most Scheme code seems to be pretty good code: people who go on working with Scheme are pretty good programmers to begin with. So there aren’t easily findable examples of really really awful code. I think it would be instructive to add the student’s code in a comment so we can see just how people screw up with the language. You wouldn’t have to write out an analysis of what’s wrong with it, just give us the data.

  2. Globules said

    A Haskell version. A Word is an unsigned type, so we don’t have to worry about negative arguments. (Which is a bit of a lie, since you can say, for example, -3 :: Word. However, it wraps around, so it’s still non-negative, albeit very large.)

    import Data.Word (Word)
    
    -- The n'th item of a list, where indexing begins at 0.  Return nothing if there
    -- are fewer than n elements in the list.
    nth :: [a] -> Word -> Maybe a
    nth []     _ = Nothing
    nth (x:_)  0 = Just x
    nth (_:xs) n = nth xs (n-1)
    
    main :: IO ()
    main = do
      print $ nth ""     3
      print $ nth "0123" 0
      print $ nth "0123" 2
      print $ nth "0123" 9
    
    $ ./nth
    Nothing
    Just '0'
    Just '2'
    Nothing
    
  3. Steve said

    Klong version

    
            :".f represents the currently computed function"
            nth::{:[~#x;"Null":|~y;*x;.f(1_x;y-1)]} 
    :dyad
    
            nth([];0)
    "Null"
    
            lst
    [2 3 4 5 6]
    
            :"'!5 executes function for number 0 through 4 and .p() prints the phrase"
            {.p(($x)," --> ",$nth(lst;x))}'!5;:ok 
    0 --> 2
    1 --> 3
    2 --> 4
    3 --> 5
    4 --> 6
    :ok
    
    
  4. Daniel said

    Here’s a solution in Common Lisp.

    [sourcecode lang="text"]
    (defun list-ref (lst n)
    (check-type n (integer 0 *))
    (cond ((null lst) (error “out of bounds”))
    ((zerop n) (car lst))
    (t (list-ref (cdr lst) (1- n)))))
    [sourcecode]

    Example usage:

    [sourcecode lang="text"]
    CL-USER> (list-ref ‘(1 2 3) 0)
    1
    CL-USER> (list-ref ‘(1 2 3) 1)
    2
    CL-USER> (list-ref ‘(1 2 3) 2)
    3
    [sourcecode]

  5. Daniel said

    Here’s the same comment, this time with the slash properly inserted in the closing sourcecode tags.

    (defun list-ref (lst n)
      (check-type n (integer 0 *))
      (cond ((null lst) (error "out of bounds"))
            ((zerop n) (car lst))
            (t (list-ref (cdr lst) (1- n)))))
    

    Example usage:

    CL-USER> (list-ref ‘(1 2 3) 0)
    1
    CL-USER> (list-ref ‘(1 2 3) 1)
    2
    CL-USER> (list-ref ‘(1 2 3) 2)
    3
    
  6. Steve said

    @Daniel: What does check-type do?

  7. Daniel said

    @Steve, the check-type macro enables run-time type checking, e.g., to ensure arguments are the expected types.

    The code above checks that the index argument is a non-negative integer. This check ends up being performed on each recursive call. Checking only once would have been sufficient, but would have complicated the code, e.g., by relying on a nested function that doesn’t perform the check.

  8. Steve said

    @Daniel: Thanks.

  9. Errichto94 said

    Class Node{
    int val;
    Node next;

    Node(int v){
      val = v;
      next = null;
    

    }

    }

    public int getNth(int index){
    Node current;
    int count = 0;

    while(current != null){
    if(count == index)
    return current.val;

     count++;
     current = current.next;
    

    }

    }

  10. Richard A. O'Keefe said

    @Errichto94 The question very explicitly called for a recursive solution.
    Here is a minimalist solution in Pop-2.

    function list_ref n xs;
       if n > 1 then list_ref(n-1, xs.tl) else xs.hd close
    end;
    
  11. r. clayton said

    A couple of solutions in Racket.

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: