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.

Posted by programmingpraxis

Filed in Exercises

11 Comments »

11 Responses to “Nth Item In A Linked List”

John Cowan said
April 10, 2020 at 12:32 PM
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.

Globules said

April 10, 2020 at 9:10 PM

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

Steve said

April 10, 2020 at 10:42 PM

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

Daniel said
April 11, 2020 at 1:30 AM
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]

Daniel said

April 11, 2020 at 1:32 AM

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

Steve said
April 11, 2020 at 2:40 AM
@Daniel: What does check-type do?
Daniel said
April 11, 2020 at 3:36 AM
@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.
Steve said
April 14, 2020 at 10:23 PM
@Daniel: Thanks.
Errichto94 said
April 16, 2020 at 8:42 PM
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;
```
}

}
Richard A. O'Keefe said
April 18, 2020 at 1:24 PM
@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;
```
r. clayton said
April 25, 2020 at 7:38 PM
A couple of solutions in Racket.

Programming Praxis