It's a new year which means many of us are searching for our next role. It's no secret technical interviews are hard, so we've compiled (hehe) a list of six data structures you should be comfortable with in 2020.
If you're going through a technical interview, these are must-knows.
We chatted about data structures & algorithms on this week's Ladybug Podcast so I recommend checking that out if you haven't already! We'll cover a lot more than the six data structures here!
Since these data structures have been written about until the cows come home, here are some of our favorite resources for learning them!
Good luck, devs!
🐞 Arrays
Arrays are the bread and butter of data structures. They are list-like data structures which allow you to keep track of elements. These elements can be reference types, like objects or other arrays, or primitives, like numbers or strings.
The length of an array in JavaScript is not fixed, meaning you can add values to the array easily.
🐞 Linked Lists
Linked lists are a data structure which isn't built-in to JavaScript, but can be created out of other JavaScript data structures.
A linked list represents a series of nodes where each node points to the next node in the list.
There are also doubly-linked lists where each node also points to the previous node in the list.
This structure uses the LIFO, or last-in-first-out, method where nodes are added to and deleted from the same end.
- Ali's 'Thank U Next' blog post
- Emma's linked list blog post
- Kyle Shevlin's Egghead.io course on data structures with JS
🐞 Stacks
A stack is not a built-in JavaScript data structure but can be built using arrays.
A stack is based on the LIFO, or last-in-first-out, concept. A stack is like a pile (or stack) of books where you have to take the top book off before you can get to the bottom book (unless you're a savage).
Stacks allow for constant time adding and removing of an item but unfortunately they don't provide constant-time access to the nth item in the stack.
- Emma's 'Stacks vs. Queues in JavaScript' blog post
- Emma's 'Creating Three Stacks With One Array' blog post
- Stacks in JavaScript
🐞 Queues
A queue is similar to a stack, but uses the FIFO, or first-in-first-out, method. You can think of a queue like a line of people waiting to buy a movie ticket. The person who has been in line the longest (first) is the first to be serviced.
🐞 Binary Trees
Binary trees are a data structure consisting of a series of nodes where each node can have a maximum of two child nodes as well as a value. The root is the top node in the tree structure and doesn't have a parent node.
A binary search tree is another type of binary tree where all node values are distinct, every parent node has a left child whose value is less than it and a right child whose value is greater than it.
🐞 Graphs
Graphs are a data structure comprised of nodes with edges. If a graph is directed, that means each edge has a direction associated with it (like a one-way street). In contrast, undirected doesn't have associated edge directions.
You might have a graph of people (purple) and movies (green) where each person can have several favorite movies but movies don't have a favorite person.
What are some other resources you like for learning data structures and algorithms?!
Leave yours below! 👇
Latest comments (41)
Should just be retitled to"Six Data Structures You Should Know Now and Til The End of Time"
Arrays. That’s it. If you’re doing database work, then maybe graphs, too.
Graphs are just many-to-many relationships, like in a social network in which users can be connected to many users who are connected to many users. A graph is a bunch of nodes and the spider web of connections (called edges) between them.
A stack is a JavaScript array you add items to via push(), and get items from via unshift(). A queue is a JavaScript array you add items to via push(), and get items from via pop().
I’ve never once used a linked list or a binary tree outside of a job interview.
Here, I fixed that second paragraph:
“If you're going through a technical interview with interviewers who have zero idea how to qualify a dev (and thus lean on outmoded engineering interview dogma and arrogant “stump the dev” questions), these are must-know-how-to-fake-your-way-throughs.”
Definitely an essential data structure. Regarding resources, I have also shared some free online courses to learn Data Structure and Algorithms, you can check them here
I'd add a seventh one, too important to miss: the hash sets/hash tables/hash maps/dictionaries/maps.. in general, the constant time O(1) data structures that are sooo key to drastically improve performances sooo many times.
By the way, one of the best introductory articles to data structures I've ever seen!
A lot of the criticisms of linked lists vs ArrayList are language-specific...
In languages like C and Java, arrays (and the underlying arrays in ArrayLists) have to be created with a fixed size. This memory is allocated in a block. If you need to insert more items than your array has, you have to request a larger block of memory and copy things across. You also have the problem where the array is taking up memory even if it's not actually being used, although with modern tech this is largely irrelevant.
The linked list addresses this problem by allowing you to create a list by storing the items in disparate pieces of memory, and storing references. The memory allocation per item is higher, since you also have to store references, but the list can happily grow to any size and has a constant insertion/deletion cost.
The big tradeoff of Linked Lists is that you lose the ability to randomly access the list. If you want the nth element, you have to traverse the entire chain until you get there. This is actually a perfectly good tradeoff for setups where you need to constantly access the first element of the list, like a queue or stack.
Like all data structures, whether it's correct for you depends heavily on your situation. In languages like JavaScript that have dynamic arrays anyway, it's probably not worth thinking about.
But you're forgetting the cache tradeoff.. the cache tradeoff of linked lists vs dynamic arrays (aka. ArrayLists) is considerable.
It can make a very large performance difference if every time you access a new item in the list you have to suffer a cache miss.
Also I don't think these "criticisms" (I prefer comparison) are language specific. Underlying it all is the concept of a fixed block of memory you allocate for an array or for a node. How you do those allocations and what their dispositions in RAM are is very relevant when figuring out the practical performance behaviors.
It may be that Python or Javascript hides this from you by implementing the dynamic array outright, however, its the very selection of the data structures used in these languages that will dictate their performance characteristics.
I'm using Java as an example. But the underlying notions of how you create lists are the same.
Nice post, congratulations and thanks for sharing.
Just a quick observation, in Queue topic:
A queue is similar to a stack, but uses the FIFO, or first-in-first-out, method. You can think of a stack like a line of people waiting to buy a movie ticket. The person who has been in line the longest (first) is the first to be serviced.
I think is queue instead of stack, isn't it?
YES THANKS
Thanks to you for sharing your knowledge .
Great post
I came into data science as a second career without a CS degree. I can say that I have a fairly good understanding of how these are implemented in scripting languages like python and JavaScript. This episode was very interesting to hear just a bit deeper into some of these topics. The supplemental images in this post are also fantastic.
Evergreen ❤️