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 classes focused on just what they need to do. That means you can have a class designed just to be able to hold other classes and then link the other class into your list. That’s the job of a list node class.
If you want to add a new item to the beginning of a linked list, then you know exactly where the new item will fit in the list and inserting it is just a matter of changing some pointers to point to the new item. This is a Big-O of one operation. You could also keep track of the last item in the list which would allow you to add items to the end quickly too. Inserting anywhere else in the list is also a Big-O of one operation if you already know the position where you want to insert the new item. But if you don’t know where the item will fit in the list, then you need to walk the list one item at a time looking for the right place to do the insertion. This part of the process is a Big-O of N operation because you’re traversing the list one item at a time.
Removing an item from a list requires that you first find the item that comes immediately before the item you want to remove. You need to know the previous item because it’s the one that has the link to the item to be removed. That link needs to change to point to the next item or you’ll break your list. The whole operation of removing an item from a single linked list is a Big-O of N operation because you have to search the whole list for the previous item.
Now that you know what single linked lists are and how to use them, I’ll explain another type of list called a double linked list right after this message from our sponsor.
( Message from Sponsor )
With a little more programming, you can create a list that allows you to navigate in both directions. You start out by keeping track of the beginning or head of the list as well as the end or tail of the list. If your list only has a single item in it, then both the head and tail will point to the same item. And if your list has nothing in it, then both the head and tail will point to nothing. With this type of list, instead of each item only pointing to the next item, now you keep track of two pointers, one to the next item and another pointer to the previous item. This type of linked list is called a double linked list.
If you want to add a new item to the either the beginning or end of a double linked list, then you know exactly where the new item will fit in the list and inserting it is just a matter of changing some pointers to point to the new item. Inserting anywhere else in the list is just the same as inserting into a single linked list with just an extra pointer to keep track of.
Removing an item from a double linked list is faster than a single linked list because you don’t need to search for the previous item. The item you want to remove already points directly to it. You just modify the previous item to point to the next item and then modify the next item to point back to the previous item. This unlinks the item from the list since there’s no node in the list that now points to the item that was just removed.
Adding and removing items for both arrays and lists have the potential to be Big-O of N operations with some special cases that are only Big-O of one. The advantage of lists though is that there’s no need to ever move items around in memory. Once an item is in memory, lists can point to that item from anywhere. Lists also don’t need to allocate big sections of memory and don’t need to tie up two large sections of memory like when an array needs to be resized. This means that lists tend to perform better in tight memory or in memory that’s fragmented so that only small pieces are available. Just be aware that lists do need to manage extra pointers and those pointers need memory too. If your items are small, then it’s possible that a double linked list could require three times the amount of total memory that an array requires. If your memory is tight and you don’t need resizing, then maybe an array is better after all.