Array

An array is a grouping of items, which you gain access to by their index. When stored in memory they will all be in a single "row" and so the size of the array must be known when creating the array so the computer knows just how large of a block to keep for the array, which makes it a fixed size. Imagine a movie theater being the memory of a computer, and an array would be a block of continuous seats. Seat A1 is taken already, so we will buy A2 - A8 for us and our 6 friends. As our friends RSVP to our invitation we give each one a ticket in our block, which would be analogous to us assigning items to different indices of the array. We have finished giving out tickets when a 7th friend shows up wanting a seat, but we are out of tickets! We go to purchase seat A9 but the theater has already sold that seat. So what we now need to do is sell back our seats, and find a new block of seats that will fit us. If another friend decides to come with we once again will have to do this.

You are now starting to see one of the problems with fixed length arrays; whenever the size of the array needs to grow, it needs to find a whole new block of memory to store the information which makes it expensive to actually grow the size of the array. The benefit of this though is that it is fast to access the next item in the array since you know exactly where it is (right next to the other one), and you also know right where it ends.

Arrays are also very fast when accessing the items, because all you do is ask for the item at a certain index (or in our example the person in seat X) and then we know exactly who is there. A problem though is reassigning those indices which is expensive since you have to reassign other indices as well. Let's pretend you have passed out all of your tickets to the movie but now James (A6) wants to sit next to Brenda (A2). The person in A5 moves into A6, A4 -> A5, A3 -> A4, and James sits into A3. Just this one person wanting to move caused a lot of trouble for everyone else!

List (linked-list, doubly linked-list)

A list is a lot like an array with a single item going into a single index, but differs in memory since you don't need to know the amount of items at the time of creation. The computer doesn't need to know the amount since it isn't going to store these in a single block of memory and instead just have each item contain a pointer, or reference, to the location of the next item.

Let's go back to our movie theater example to make this a bit more concrete. You want to see the midnight showing of the newest Star Wars movie so you and your buddies can talk about it together right away. Since tickets will be limited you each friend will buy a ticket as they decide to go. You were the first one to purchase a ticket and get seat A23. The next person bought seat number B1, and the next B5. In total you find out that there will be 10 of you going to the movie and seated throughout the theater -- A23, B1, B5, C11, E8, E10, E15, F1, F8, G11. Rather than you needing to keep track of each person's seat, you could just have each person know the seat assignment of the next person (don't know why you actually need to do this but it helps with the example). If another person wants to join the group going they just buy a ticket, and the person in G11 would learn their seat assignment. This would be a linked-list. This is one of the benefits of a linked-list because adding on additional items on the front or back of the list is fast (same with arrays) but you don't have to worry about outgrowing the amount of indices and having to get a new block of memory. Traversing over the list forwards (start to end) is also simple and fast since you just start at a spot then go to the next item.

Going backwards is impossible on a linked-list if it is only singly linked, and that is when you would employ a doubly linked-list. Each person now just needs to know the seat assignment of the person after them and before them. You can now go forward and backwards over the list with ease. The array has it beat in this regard since you needed to add a bit of information to be able to go forward and backwards and it is simply built into an array.

A spot where linked lists have arrays beat (besides never outgrowing amount of indices available) is insertion. Another silly example with the movie theater seats but oh well. While getting to your seat you realize just two seats down is another friend but since you can't just race to the person in G11 and tell them to memorize this location, you decide you will remember their seat position (A25) and ask them to remember seat position B1. So now your list looks like this -- A23, A25, B1, B5, C11, E8, E10, E15, F1, F8, G11. Boom, no one else go shifted down like you would have seen in the array (similar to James wanting to sit next to Brenda), and instead only two people were disturbed this time.

Use case

Okay, time to get away from the movie theater and into a real use case. Arrays and lists are great for keeping things in a particular order. They are also great for finding a specific item in that list even if you don't know the exact location of it.

You have a brand new deck of cards and you need to find the 8 of hearts. You can go through the deck and look at each card checking if it is the 8 of hearts, and while this will get you your answer it will take a long time. At worst you will have to look at all the cards. Another way to do this would be do a binary search.

Cut to the middle of the deck (or as close as you can) and see it is a king of clubs. Well, you know that since this is a USPCC deck of cards the order of the cards is ace to king spades, ace to king hearts, king to ace spades, and king to ace hearts. We know that the 8 will be the hearts, and so it will be on the right since it is higher in the sort. You have eliminated checking 26 cards. Cut to the middle again and you see the king of hearts, which again is too low in the order of cards and so you have eliminated another 13 cards. 13 cards left! Cut as close to the middle as you can and you have the 6 of hearts. Alright, too low. Now you just have 6 cards left, and cutting to the middle you get the 10 of hearts. So close! Eliminate that and anything above and just three cards left. Cut to the middle and it is 8 of hearts! Let's see, you had to look at king of clubs (1 card), king of hearts (2), 6 of hearts (3), 10 of hearts (4), and finally found your card (5). You checked only 5 cards to find a card in a deck of 52. At worst, you would have only had to check 6 cards because binary search uses log(n) because you are seeing how many time 2 needs to be multiplied by itself to be equal to or greater than 52, which is 6 (2 -> 4 -> 8 -> 16 -> 32 -> 64)

Final Thought

I started writing this blog post and got to talking about lists and realized that I wanted to brush up on these topics on my own and have started reading Grokking Algorithms which is a great resource. I was really excited to see that the author use the same analogy of movie theater seating for lists!