<commit_before>% Layout

So what's a singly-linked queue like? Well, when we had a singly linked stack
we pushed onto one end of the list, and then popped off the same end. The only
difference between a stack and a queue is that a queue pops off the *other*
end. So from our stack implementation we have:

```text
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

stack push X:
[Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None)

stack pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
```

To make a queue, we just need to decide which operation to move to the
end of the list: push, or pop? Since our list is singly-linked, we can
actually move *either* operation to the end with the same amount of effort.

To move `push` to the end, we just walk all the way to the `None` and set it
to Some with the new element.

```text
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

flipped push X:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
```

To move `pop` to the end, we just walk all the way to the node *before* the
None, and `take` it:

```text
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)

flipped pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
```

We could do this today and call it quits, but that would stink! Both of these
operations walk over the *entire* list. Some would argue that such a queue
implementation is indeed a queue because it exposes the right interface. However
I believe that performance guarantees are part of the interface. I don't care
about precise assymptotic bounds, but rather "fast" and "slow". Queues guarantee
that push and pop are fast, and walking over the whole list is definitely *not*
fast.

One key observation is that we're wasting a ton of work doing *the same thing*
over and over. Can we memoize this work? Why, yes! We can store a pointer to
the end of the list, and just jump straight to there!

It turns out that only one inversion of `push` and `pop` works with this.
Because our list is singly-linked, we can't effeciently walk *backwards* in
the list. To invert `pop` we would have to move the "tail" pointer backwards.
But if we instead invert `push` we only have to move the "head" pointer
forwards, which is easy.

Let's try that:

```rust
use std::mem;
# fn main() {}

pub struct List<T> {<commit_msg>Fix typo<commit_after>% Layout

So what's a singly-linked queue like? Well, when we had a singly linked stack
we pushed onto one end of the list, and then popped off the same end. The only
difference between a stack and a queue is that a queue pops off the *other*
end. So from our stack implementation we have:

```text
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

stack push X:
[Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None)

stack pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
```

To make a queue, we just need to decide which operation to move to the
end of the list: push, or pop? Since our list is singly-linked, we can
actually move *either* operation to the end with the same amount of effort.

To move `push` to the end, we just walk all the way to the `None` and set it
to Some with the new element.

```text
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

flipped push X:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
```

To move `pop` to the end, we just walk all the way to the node *before* the
None, and `take` it:

```text
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)

flipped pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
```

We could do this today and call it quits, but that would stink! Both of these
operations walk over the *entire* list. Some would argue that such a queue
implementation is indeed a queue because it exposes the right interface. However
I believe that performance guarantees are part of the interface. I don't care
about precise asymptotic bounds, but rather "fast" and "slow". Queues guarantee
that push and pop are fast, and walking over the whole list is definitely *not*
fast.

One key observation is that we're wasting a ton of work doing *the same thing*
over and over. Can we memoize this work? Why, yes! We can store a pointer to
the end of the list, and just jump straight to there!

It turns out that only one inversion of `push` and `pop` works with this.
Because our list is singly-linked, we can't effeciently walk *backwards* in
the list. To invert `pop` we would have to move the "tail" pointer backwards.
But if we instead invert `push` we only have to move the "head" pointer
forwards, which is easy.

Let's try that:

```rust
use std::mem;
# fn main() {}

pub struct List<T> {
{'fraction_non_alphanumeric': 0.1125, 'fraction_numerical': 0.0, 'mean_word_length': 3.9583333333333335, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 39, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2090417', 'n_tokens_mistral': 1479, 'n_tokens_neox': 1434, 'n_words': 789}