# More on linked lists

We left off having defined a `LinkedList` class with some basic methods.

class ListNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.first = None

    def append_to(self, node: ListNode, data):
        if not node.next:
            node.next = ListNode(data)
        else:
            self.append_to(node.next, data)

    def append(self, data):
        if not self.first:
            self.first = ListNode(data)
        else:
            self.append_to(self.first, data)

The picture we've been describing looks something like this in memory.

But without implementing more, it's hard to test that our append method is doing what we expect! So let's keep going and make our class more functional. It's easy to guess what we might want to add, since the actions available to a `LinkedList` should be pretty similar to those available for a normal Python list.

## length

First: length. We'll follow exactly the same pattern as `append`, with a main method that does a cse distinction on whether there's a first element, and a recursive method that walks down the elements of a nonempty list.

    def length_from(self, node: ListNode) -> int:
        if not node.next:
            return 1
        return 1 + self.length_from(node.next)

    def length(self) -> int:
        if not self.first:
            return 0
        return self.length_from(self.first)

The `length_from` method starts at some node in our list, and counts the number of nodes that come after it (including itself). This is done recursively: if nothing comes after, return 1. Otherwise, count the length from `next`, and add 1 to that length.

There are two important things to notice here. First of all, `length` and `length_from` return a value, instead of modifying the list like `append`. So we need `return` in both the base and recursive cases. If the recursive case read `1 + self.length_from(node.next)` (without the `return`), it would compute the right length, but we couldn't access its value afterward.

Second, even though we don't use the `self` argument in `length_from`, we have to include it if `length_from` is a method of the `LinkedList` class. This is a little ugly, and indeed, it feels unnecessary. We could implement `length_from` as a regular function instead. Even better, we could implement it internally to the `length` function. After all, nobody should be calling `length_from` except from inside `length`! So an alternative way to write this would be:

    def length(self) -> int:
        def length_from(node: ListNode) -> int:
            if not node.next:
                return 1
            return 1 + length_from(node.next)
        
        if not self.first:
            return 0
        return length_from(self.first)

Either way, we can add some test cases that make sure our function works well with `append`.

l = LinkedList()
assert(l.length() == 0)

l.append("hello")
assert(l.length() == 1)

l.append("world")
assert(l.length() == 2)

## Access the nth value

The next useful part of a list interface is a function to access the `n`th value of a list. Here we have to be careful with the input. What if it's too high, or negative? Python lists throw an exception, so we'll do the same. More on this on Monday!

Note that if `n` is at least 0, and strictly less than the length of the list, the list cannot be empty. (In that case the length of the list would be 0.) So in `nth`, our bound check on `n` rules out that base case already.

The `nth_from` method is interesting. Like `length_from`, we have a base case and a recursive case. But the base case checks whether `n == 0` instead of whether `node.next` is `None`. This makes sense, because we want to stop our recursion when we reach the node we're looking for, which might not be the end of the list! Instead, we recurse with the value `n-1`, since taking `n` steps from `node` is the same as taking `n-1` steps from `node.next`.

    def nth_from(self, node: ListNode, n: int):
        if n == 0:
            return node.data
        return self.nth_from(node.next, n - 1)

    def nth(self, n: int):
        if n < 0 or self.length() <= n:
            raise Exception("index out of range")
        return self.nth_from(self.first, n)

Note the lack of type annotations. We don't know what type of value `nth` or `nth_from` will produce, because we don't know what type of value is stored in `data`.

Again, let's add some tests.

l = LinkedList()
assert(l.length() == 0)

l.append("hello")
assert(l.length() == 1)
assert(l.nth(0) == "hello")

l.append("world")
assert(l.length() == 2)
assert(l.nth(0) == "hello")
assert(l.nth(1) == "world")

Try out what happens if you ask for a value that's out of range.

## repr

Finally, if we want to see the entire lists we're building, we can implement `repr`:

    def repr_from(self, node):
        if not node.next:
            return repr(node.data)
        else:
            return repr(node.data) + ", " + self.repr_from(node.next)

    def __repr__(self):
        if not self.first:
            return "[]"
        return "[" + self.repr_from(self.first) + "]"