40: Collections: List.

You’ll need to be able to work with groups or collections of items. A game that only has one character with one action that can be done and with one opponent isn’t going to win you any awards. You have choices and this episode continues more than a week long exploration of collection types available. You’ll learn when to use each type of collection and why. Up today is the list. I’ll explain what lists are and then give you some guidance on when to use them. Let’s say you have three instances of a letter class that you want to add to a list. A single linked list would look like this with arrows pointing from one item to the next: head -> node(A) -> node(B) -> node(C) The list class has a head member pointer that points to the first node in the list. The nodes are classes also that are designed to work with the list class. Their job is to point to the instances of the classes you actually want in the list as well as point to the next node. While I wrote in this example: node(A) think of this more like: node -> A it was just a bit confusing trying to draw two pointers in one line so I put the instances of the letter class in parenthesis. If this was a double linked list, then it would look like this: head -> node(A) <-> node(B) <-> node(c) <- tail Notice in this case how the head has a pointer to the first node but the first node does not point back to anything. It still has a pointer member variable. All node classes in a double linked list have two pointers, one called previous and another called next. The first node has no previous item so it’s previous pointer is null. The first node does point to the second node and the second node points back to the first node. That’s what I mean when I draw the arrow pointing in both directions. You can listen to the full episode or read the full transcript for more. Transcript Have you ever played a game where you follow a series of clues? You’re trying to find something but all you have is the first step. You don’t know how many steps will be needed so you figure out the first clue and that gives you the second clue. When you figure out the second clue, then you get the third clue. In effect, what’s happening is each object along the way points to the next object. This is a linked list because every item is linked into the list from the previous item. The items in a list are not next to one another and are normally completely out of order in memory. The have order based on the links. When all you have is a pointer to the first item, and normally, this is called the head of the list, and each item points to the next, then there’s only one direction you can follow. You start at the head and move from one item to the next. You’ll know when you get to the end because the last item will not point to anything. You can also have a list with nothing in it by setting the head to point to nothing. If you’re well into a list and decide that the item you really want was many steps back, there’s no way for the list to allow you go back. You either have to keep track of interesting items along the way or start over from the beginning. This type of linked list to be more specific is called a single linked list. What’s it take to add and remove items from a list? List items are really individual items that can live anywhere in memory. Adding an item to a list means that you just create a new list node class to hold the item and modify some pointers to link the item into the list. Why do you need a new list node class? Why can’t your item itself be placed directly into the list? Well it can if your class is already designed to be used in your list. This means it needs a pointer to the next item. The problem is that adding a pointer to your class usually has nothing to do with your class itself and only adds complexity that it doesn’t need. I advise that you keep your class