# Linked Lists

## Table of Contents
0. [Another Use for Objects: New Data Structures](#s1)
1. [Building Linked Lists in Python](#s2)
2. [Implementing `append`](#s3)

A new drill should be available on Gradescope. It involves today's lecture material.

## Another Use for Objects <A name="s1"></A>

So far, we’ve mostly used objects to represent real-world entities (animals etc.). We can also use objects to implement data structures.

Let’s say we want a data structure that has the following operations:
* `append(value)`: stores a value
* `nth(n)`: retrieve the n-th value stored
* `remove(n)`: remove the nt-th value stored

These operations should sound familiar: they are the core operations on Python’s lists. We saw a similar type in Pyret: Pyret’s lists, defined as

data List:
  | empty
  | link(fst, rst :: List)
end

Python’s lists are implemented using contiguous chunks of memory. Pyret’s lists are different: they are constructed as a linked structure. Here's two pictures illustrating the difference.

### A Python List


### A Pyret List


Notice that the Pyret list is a bit more complicated. It's constructed from links that might be scattered around in memory, and those links are connected via _references_ to each link's successor (or `empty`, which means the list has ended).

I've used two colors to help contrast two different ways you'll see these lists drawn. In reality, the arrows from link to link (shown in the black-colored list) are references to memory addresses (made explicit in the orange-colored list).

This style of list is called a _Linked List_ (because of how it's structured).

### So what's the difference?

Both of these low-level data structures can provide all the features of a "list": adding, removing, accessing the $n^{th}$ element, and so on. But how long does each operation take? E.g.,
* Adding a new element to the end of the list:
* Python lists can add new elements to the end of the list in $O(1)$ time, _provided that there is unused room in the block of memory_.
* Pyret lists (as currently designed) need to find the end of the list before they can add a new element, meaning they need $O(n)$ time to add a new element to the end.
* Finding the $n^{th}$ element of the list:
* Python lists can find this element in constant time.
* Pyret lists need to count forward $n$ elements.

What are Pyret-style lists good for, then? Well... think about what happens if Python needs to insert a new element into the _middle_ of a list.

## Building Linked Lists in Python <A name="s2"></A>

Could we build something similar to Pyret's lists in Python? Yes! But where would we even get started?

Let's write down some examples first. In Pyret we might write:

empty
link(1, empty)
link(1, link(2, empty))

Let's write some classes that let us turn this into something we can write in Python. The picture above is a hint: we should probably have a kind of object to represent those links.

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

Now we can write `ListNode(1)` to represent the list storing the value `1`. But that's not yet enough: we need to handle the first and third examples (the empty list, and a list with multiple elements).

We'll do this by adding another class, one that represents an entire list in itself. We'll give it one field, `first`, to represent the first `ListNode` it contains. When we first make a `LinkedList`, it will be empty (represented by `None` in the `first` field).

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

#### I wonder...

How would the picture of the Pyret list above change to account for this new `LinkedList` class?

#### Updating our examples

Let's translate those rough Pyret examples into Python code that creates them.

* `empty` would be `LinkedList()`: just a list without any `ListNodes`.
* `link(1, empty)` would now be ...

Bother. We aren't done; we need some way of `append`ing new values to an existing list.

## Implementing `append` <A name="s3"></A>

(All code in this section is inside the `LinkedList` class; I've just left that out for readability.)

Let's start with an empty method:

    def append(self, data):
        pass

We'll proceed, as we have before, by making a skeleton of the method and adding details as we go. When `append` is called with a new piece of `data` to add, what do we have to work with? Just:
* the `data` value; and
* the fields of the `LinkedList` being appended to, `self`.

Probably we'll need to make a new `ListNode` object to hold the new data value, so let's do that now:

new_node = ListNode(data)

Now we need to add it into the list's chain of nodes. The list gives us one field, `self.first`, which points to the first node in the list. We could certainly change it:

self.first = new_node

Is that the right thing to do?

### The Empty-List Case

Well, _sometimes_ it is. If the list is empty, there is no first node and we're free to just make the new node the first node in the list. But if the list already contains nodes, we need to traverse the list until we find the end (and then add the new node there). So we'll split the function, leaving the second case unfinished for now:

    def append(self, data):        
        if not self.first:
            self.first = ListNode(data)
        else:
            pass # ??? need to update LATER in the list

### The Non-Empty List Case

Now we need to do 2 things:
* find the last node in the list; and
* add the new node as its successor.

Let's solve these problems backwards. If we find the last node, making the new node its successor is straightforward:

    last_node.next = ListNode(data)

(Remember that the new node will have `None` in its `next` field, and so the list will safely stop there.)

How can we get to the end of the list? We could use a loop, but this is also a great exercise in using recursion. We can write a function that passes the obligation to add a new value down the list, until (eventually) that obligation can be met:

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

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

And now we've written `append`!

Or have we? We couldn't write tests easily before, but now we can at least test that it's possible to append to a list!

Next time we'll have other methods that we can use to make our tests even better.