Linked lists. Fun! I’d say the hardest thing about understanding them is the lack of a real index, a consequence of the lack of a real container. It just feels so odd, you know? Having all the elements floating around out there, as far as Python is concerned. Each element only aware of the next one’s location via that rest attribute. The next element not even aware of the element that is aware of it. So tenuous. In fact, it’s that unidirectional awareness that screwed us in labs. That damn prepend method and that damn remove_first method. I mean, queues are first in, first out. That means you’re using one side to put things on and the other to take things off. But both “pre” and “first” deal with just the one side. That was misleading. In order to deal with one side of a conveyor belt—putting things on sometimes and taking them off sometimes from the same side—you would either need a container or you would need the elements to be aware of themselves in both directions (i.e., each element would have an attribute “next” and another attribute “previous”, such that two adjacent elements would be pointing to each other, using up even more memory). Anyway, once we realized that the methods were misleading and decided that we had to ignore at least one of them, the problem became easier to solve, and the benefit of a linked list implementation for a queue ADT became clearer. After all, if you have no index… you have no index to update for each of the potentially millions of elements left in the queue whenever you dequeue.
What else? The midterm. Considering the fact that we only have two lectures this week and one of them hasn’t happened yet, I consider this a chance to unwind rather than to reflect on, well, things we’re about to learn. Therefore, enjoy this hilarious review of a terrible old game.