Nth Item In A Linked List

April 10, 2020

[ I continue working at home. It’s no fun, and less productive than working in my office, but I’m coping. There remains much emergency work to be done related to moving all of our students online. I hope everyone is doing well during this time. ]

A student recently asked for help on a beginning-programmer forum to write a Scheme program that finds the nth item in a linked list, mimicking the list-ref built-in function. He posted his code, which was awful; I won’t repost it here. Instead of engaging him, I sent a private email suggesting that he consult either his professor or his teaching assistant, as his posted code showed several misconceptions about Scheme. He wrote back, saying he was sure there was only one thing wrong with his code and I could easily point it out. I didn’t respond, as there was far more than one thing wrong with his code.

Your task is to write a program to find the nth item in a linked list; your program must be recursive, as was required by the original assignment. 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

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: