Linked List Class Invariants + Queues + Stacks + Big O

We covered four big topics today:

1) How to think about invariants when you're doing your code. Basically, if there is a rule that has to be followed, every time you have a function that changes an object, you have to really stare at it and make sure that all the invariants will always be maintained.

2) Queues are ADTs that support two main commands: pushing at the back and popping off the front. They're used in real life in a lot of situations involving buffering, which is to say that one thing is producing data and another thing is consuming data, so you put a queue between them to mediate the relationship. They are a FIFO (first in first out) data structure.

3) Stacks are an ADT that are kinda the opposite of queues. They support pushing and popping off the top of the stack. They're used in a lot of contexts, such as the stack, doing parenthesis matching, and so forth. They are a LIFO (last in first out) data structure.

4) Big O is the main way we talk about the running time of algorithms and data structure operations in computer science. It is how we answer the question, "How much slower will this code run as the data structure gets bigger?"