Well hello there fellow learner! Are you, like me, feeling overwhelmed at the prospect of preparing for technical interviews, fussing over each possible question interviewers could ask you about algorithms, data structures, and other computer science fundamentals that you’ve been trying to make sense of between your projects?
If you are nodding your head right now, read on. I’ve done a little research that I’ll be happy to share. I might not be an expert software developer yet (experts: please let me know if you spot a mistake in the comments!), but I’d just love it if the way I have made linked lists make sense for me brings some relief to your tech-interview prep efforts.
What are Linked Lists?
Well, why not start with what the hivemind of Wikipedia has to say about this data structure:
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence.
Okay, it’s a good definition but… not immediately obvious what that means in a practical sense. Let’s unpack it in stages.
Here’s what came to mind for me: Imagine a field filled with flowers. Dandelions, daisies, dahlias.. anything pretty with a long stem that you could weave into a chain. Linked Lists are kind of like that chained, linear series of flowers.
Flowers (nodes) can be picked from anywhere in the field (memory). The bloom (data) and stem (pointer/reference) are an essential part of each flower, even the last one in the chain! The last flower’s stem is attached to nothing (null/nil), but it still needs to be there to not fall off the chain. More often you’ll see a diagram that looks something like this:
It probably won’t surprise you to hear that the first node in the linked list is often called the head, the last is called the tail, and that linked lists really reinforce the importance of the order of the nodes (or flowers, if you’re up for some fun and colour).
Well goshdarnit, how’s this different from an array? Let’s consider a couple of practical things we do with data every day: Access and add more.
Accessing Data
We know arrays are indexed in contiguous (neighboring) spaces in memory, so we can just access that indexed value directly. The syntax to get the value in that space often looks like arrayName[n] to get the n-index value. This is just one operation, always, so we say that the complexity of doing this is constant time, a.k.a. gold standard speedy.
But chain-of-flowers linked lists aren’t stored in predictable places in memory like that! So to get to the n-th position in the list, you start at the head (0-th position), and follow that trail of pointers until you get to your desired position. That’s n-many steps, so we’re talking linear time. Not great, not terrible, but arrays win out for speed in this operation.
Adding Data
Back to the arrays! Let’s imagine that now, we want to add some data by putting it in at the n-th index. Remember, indexed means order is preserved because data is stored in fixed, predictable intervals across contiguous memory. If you’ve heard of Hilbert’s Hotel or have any siblings, you know it’s time for everyone to shuffle over. We’re talking linear time complexity to get this done. No big deal if your array is 5 elements long, but if it’s 31,415,926,535 elements long it’s a bit more of a commitment.
It’s time for linked lists to shine. The consensus is that the need to add some data is recognized while traversing the list, so we’re going to ignore the work that happens to access the n-th position in the chain in terms of analysing complexity. You might already be thinking: “Why not just adjust 2 stems (pointers) to add a new flower (node) to the linked list (chain) when I notice that bloom (data) needs to be added in?”. That’s exactly what you want to do. Inserting data will always be adjusting only 2 pointers, so constant time. Nice!
The point of these comparisons was not so much to say that an array is always better than a linked list or vice versa, but to highlight some classic examples of the strengths and challenges of each structure. That is to say:
What Next, for the Technical Interview?
I am far from an expert in this realm, but understanding the basics of this structure and operations and being able to implement them in a given language really seems to be a likely candidate to expect in a technical interview! I personally find implementing structures like this to be my favourite way to check my understanding and get ready.
You might also be asked to:
- Traverse a linked list
- Traverse a linked list and do something with the data along the way (eg. sum, multiply)
- Find a specific value in the list
- Reverse a list
- Delete a node
- Talk about doubly linked lists
- Talk about circular linked lists
And honestly, many more operations and twists on this deceptively simple structure idea. HackerRank and Structy.net have some great exercises if you’d like to get started practicing, including worked solutions to these exact types of problems that might come up in an interview! Even if a linked list doesn’t show up in your interview, this is a great way to practice topics like object-oriented programming and recursion as well.
In Closing…
I am still far from being an expert in data structures and linked lists, but I’m glad to have taken some time to explain what I’ve learned in my own words – I feel I understand it at least a little better having done my best to explain it to someone else, and if you've read this far I hope that you feel more confident too!
I’m looking forward to my next opportunity to consider using a linked list – maybe in action histories to support an undo-redo interaction, looping lists I want to traverse multiple times (a flower crown!), or playlists. I know I’ll be looking back at this post then, and I hope you do too!
Top comments (0)