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.
Programming Praxis 
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.
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.)
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 :okHere’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]
Here’s the same comment, this time with the slash properly inserted in the closing
sourcecodetags.(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:
@Daniel: What does check-type do?
@Steve, the
check-typemacro 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.
@Daniel: Thanks.
Class Node{
int val;
Node next;
}
}
public int getNth(int index){
Node current;
int count = 0;
while(current != null){
if(count == index)
return current.val;
}
}
@Errichto94 The question very explicitly called for a recursive solution.
Here is a minimalist solution in Pop-2.
A couple of solutions in Racket.