Know Just Enough… CS || LinkedLists: You Filthy Data Structure, You.

So I had this interview the other day, right? We were chatting away about his project, what I’ve worked on, all that good stuff. Everything was going great! Then, the moment came:

“Okay, so I’m gonna ask you a few technical questions”

You got this, Bryan! You’ve been reading all these books, you’ve been doing all this programming, you’re ready! They started, and I was doing okay.

Then a question came up, and I kinda goofed. I don’t really expect to hear back from them. But it’s alright! I’ll get ’em next time!

What I have been learning is that being a self-taught programmer means that there will probably be some glaring holes in your knowledge base. Ask me when I would use a stateless functional component over a regular React class (whenever there isn’t state or lifecycle methods needed) and I’m golden. Ask me to figure out if this function is O(logN) or O(!n) or O(god_pls_help_me) and I’m gonna say the latter.

I have learned what I needed to know, or wanted to know, but not quite what hiring managers may want me to know. So I’m here to talk about what I don’t know!

Maybe we can learn something together! (I might write other ones of these but maybe not because I’m a notoriously bad blogger).

Here we go. Let’s get em, tiger!

(side note: the book I have been reading, The Imposters Handbook by Rob Conery is amazing and I can’t recommend it enough. The fact that I know what lambda calculus is now speaks volumes.)


Linked Lists vs. Arrays

My undoing from the previous anecdote.

I’m sure we all know what an array is, right?

['full', 'of', 'neat', 'stuff']← an array full of neat stuff.

How about a Linked List? It’s kinda like this:

let aLinkedList = 
{data: 'full', next: ->},
{data: 'of', next: ->},
{data: 'confusing', next: ->},
{data: 'stuff', next: null}

Kinda like that? It’s basically an object with some data and a pointer to the next bit of data. A better representation, stolen from the interwebs is:

Thats better.

So what is the difference? When would we use one over the other? My original answer was something like:

“*mumble mumble* something about performance… traversal… memory? *cough cough* next question pls”

Now that I’ve done some reading on it, let’s talk about it. Perhaps you will be prepared when a rouge hiring-manager/dev/recruiter asks you this question.

Linked Lists are great when you will be adding and removing things frequently and from random places within the list. Arrays need to know the size beforehand, and are saved as a big chunk of data. Linked lists are just bits of information with a pointer to the next bit of information, so changing the size of it doesn’t really mess too much up. For example:

let anArray = [1,2,3,4,5,6] ;
anArray.length; // 6
// now lets remove 3...
anArray = anArray.slice(0,2).concat(anArray.slice(3));
anArray; // [1,2,4,5,6]
anArray.length; // 5

Whoa. Not only was that kind of a pain, but after we removed the item, our program had to go back through and reallocated space for the array, shifting every item’s index after the one we removed back one to fill in the gap.

It’s not that big of a deal now when we’re working with 6 items, but what about 10,000? 10,000,000? A google? Idk, like I said, I’m new to all this CS stuff, but it seems like it could be a pretty big issue.

With a Linked List, all we need to do is:

wow. such art. Prints available in my e-shop for $250.00.

No need to shuffle anything around. Just remove our item, and change the previous pointer to item after the deleted one.

So thats cool. What about arrays?

Arrays are better… a lot of the time, it seems. We get some good methods with arrays already like push/pop/shift/unshift and slice/length/join/sort/reverse. Plus they have the added bonus of having an index associated with each item. With this, we can randomly pull out the item we are looking for with ease.

let anArray = [1,2,3,4,5,6];
anArray[1]; // 2
anArray[anArray.length - 1]; // 6

The power we get adding and removing things in the Linked List is slightly diminished when we need to go through each item to check and see if it is the one we are looking for. That’s pretty lame.

So:

Will you be adding and removing lots of things from all over the array AND only be going through in an orderly fashion? Maybe you wanna use a Linked List.

Will you be needing to find random bits of stuff from the list a lot? Probably better off with an array.


By no means is this exhaustive, or fully informative even. There are many use cases where one may be better equipped than the other, and there are many more where your personal preference is probably enough. But hey, hopefully after reading this you can at least spout off a bit more information than I did if someone asks you this question.

Till next time.

❤ Bryan


@spacebrayn on Twitter but I’m really bad at it. Hit me up and we’ll talk about nerd shit.