Day 79 Data Structures & Algorithms

Day 79 is in the books. Today we started off the day with a little something our instructor likes to call “Mind Fun”. It’s a nice way to get our brains warmed up. Typically we’re given some sort of challenge that requires us to identify a mathematical pattern or computer science concept in order to solve it. We needed a few hints, but eventually with the help of our instructor and one of our classmates we all got it. One of the really cool things about this program is that we have people from all kinds of backgrounds so typically one of us will find the solution. That’s what happened today. One of my classmates cracked the code and then helped explain it to me. That kind of collaboration has been one of the best parts of the program.

Quicksort

The second half of the morning was spent researching an algorithm. Initially I didn’t think we would have class time for this so I got up at 5:00 am this morning and made a presentation about quicksort. It was actually great to have some class time though because I got to really dig into the code and how it works. If you want to check out this simple slide deck I made about quicksort you can do so here. It includes a javascript implementation that was especially helpful for me. I’m understanding it pretty well at this point, but I plan to play around with the code a little more this week to really drive it home.

After lunch half of the groups did a quick presentation on the algorithms that they chose to research. We covered Bubble Sort, Insertion Sort, and Merge Sort. It was a really great way to learn more about each of those algorithms. It’s really interesting to see the different ways that people have gone about solving this problem of sorting elements in an array. It’s really good to understand the different use cases for each one as well so that you can use them appropriately when the need arises.

Linked Lists

During the last part of the day we were introduced to linked lists. A linked list is a type of data structure. Imagine if you had an object that was filled with other objects. The outer object will be our linked list in this example. Each of the inner objects is called a node, but they are just objects with certain types of properties. Each node stores a value and a pointer to the next node in the list. The first node in the list is referred to as the head because it’s the first item in the list. The last node in the list is referred to as the tail because it is the last item in the list. The outer object has a property called head which stores the value of the first node, and a property called tail which stores the value of the last node in the list. So we have a way to easily identify the first and last items in our list, but what about the items/nodes in between?

The only way that you can access the inner nodes is by working your way through the chain. It’s like playing a game of telephone. Let’s say you’re searching for the value of a specific node. You would have to check the first node in the list to see if it contains the value that you are looking for. If it does not then you would call next and go to the second item in the list. You would repeat this process until you find the value that you are looking for.

If you’re like me you might be wondering why on earth you would ever bother with a linked list when we have arrays which are so much better for accessing specific values or elements. It turns out that there are some good use cases for linked lists. For example linked lists are really good at growing in size. With arrays there are several operations happening under the hood when you increase the size. By default memory is allocated up front for an array. If you later decide to change the size the old array gets copied to a new location in memory with the new items added. The old copy then gets deleted from memory to free up that space. In javascript this happens automatically via a process called garbage collection. In other languages you have to manage your memory manually so this is even more difficult to do.

Linked lists are also great for some of the data structures that we see in the javascript event loop. For example the stack and queue are both linked lists and that makes a lot of sense if you think about it. The stack has to clear itself in order so each item on the stack just needs to know what to call after it’s work is done. The queue works in a similar fashion. The queue follows a first in first out protocol. Each item moves from the queue to the stack in an orderly fashion so the linked list is a perfect fit.

Summary

I’m really digging this computer science stuff. It’s definitely new territory for me and it’s stretching my brain in different ways, but I love that feeling of making my brain work hard. I know that it’s getting stronger each day and that is a cool feeling. That’s enough for today. I’m off to finish a job application before bed. Until next time…happy coding.

79 down 21 to go