40+ linked list questions and solutions (easy, medium, hard)

To ace your coding interview for a software engineering job, you’ll need to understand linked lists. They come up frequently in coding interviews and are fundamental to many other data structures too.

Let’s take a look at some typical linked list questions.

Below, we take a look at some more questions and provide you with links to high quality solutions to them. We explain how linked lists work, their variations, and the most important things you need to know about them, including a useful “cheat sheet” to remind you of the key points at a glance.

This is an overview of what we’ll cover:

1. Easy linked list interview questions
2. Medium linked list interview questions
3. Hard linked list interview questions
4. Linked list basics
5. Linked list cheat sheet
6. Mock interviews for software engineers

Click here to practice coding interviews with ex-FAANG interviewers

1. Easy linked list interview questions

You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of linked lists.

As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.

If you get stuck, go ahead and look at the solutions, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high quality answers.

Here are some of the easiest questions you might get asked in a coding interview. These questions are often asked during the "phone screen" stage, so you should be comfortable answering them without being able to write code or use a whiteboard.

2. Medium linked list interview questions

Here are some moderate-level questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.

3. Hard linked list interview questions

Similar to the medium section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.

4. Linked list basics

In order to crack the questions above and others like them, you’ll need to have a strong understanding of linked lists and how they work. Let’s get into it.

4.1 What is a linked list?

A linked list is a data structure used to store a collection of data elements. In this way, it is similar to an array. However, unlike an array, the data elements in a linked list do not need to be stored contiguously in memory. Rather, each node in a linked list has a pointer or reference to the memory location of the next node in the list. This means that linked lists do not have a fixed size like arrays, and can easily grow and shrink as elements are added or removed.

Another advantage linked lists have over arrays is that inserting or removing elements from a linked list is possible in constant time, whereas removing or inserting elements into an array generally takes linear time. 

Since the data elements are not stored sequentially in contiguous memory, linked lists are not as efficient as arrays at random access of elements. Indexes are commonly used to access any element in an array in constant time. Accessing an element in a linked list generally means walking the list from one node to the next. This takes linear time.

4.1.1 Types of linked lists (Java, Python, C++)

There are a number of variations on the standard singly linked list. 

A doubly linked list has nodes with links to next and previous nodes, making it possible to traverse the list in either direction. 

A circular linked list's last node has a link to the list's first node. This is useful for implementing certain types of circular buffers. It is also useful for implementing round-robin-type schemes. 

A multi-linked list has multiple links from each node. The different links point to the “next” node based on some ordering or logical criteria. In this way, it is possible to have the list ordered on multiple properties. For example, in a movie list, there could be a link to the next movie alphabetically, another link to the next movie chronologically, and another link to the next movie by the same director. Multi-linked lists are also useful for implementing sparse matrices, where a node has a link to the next number in the row, and the next number in the column.

Java has a built-in linked list implementation called "LinkedList." Python has a "deque" class in its collections module, which is implemented as a linked list. In the Standard Template Library (STL) in C++, there is a linked "list" class, which implements a doubly linked list.

4.1.2 How linked lists store data

Linked lists are made up of a string of nodes. Each node is a container which stores the data element along with a reference to the next node. The first node is known as the head of the list. This is often used as the entry point, or handle, to the linked list. The last node in the list generally has its next pointer set to null, except in circular linked lists, where the last node points to the head node. 

4.1.3 How linked lists compare to other data structures

Linked lists are mainly contrasted to arrays. Arrays have faster access time, in constant time, to access a random element through indexes. Accessing an element in a linked list takes linear time. Linked lists are faster at inserting and removing elements, which can be done in constant time if the target position of the node is known, whereas arrays take linear time. Linked lists can also grow to very large sizes more easily than arrays, as linked lists are not bound to available contiguous memory blocks as arrays are. 

Queues and stacks are often implemented using linked lists, as the size of these structures is often large and dynamic. Queues and stacks also do not require random indexed access to elements, as elements are added and removed from the ends. Linked lists perform well here, as adding or removing elements from the ends of the list can be done in constant time.

5. Linked list cheat sheet

Linked list definition:  A linked list is a collection of nodes representing a sequence. Each node contains data and a reference (a link) to the next and/or previous node in the sequence.

You can download this cheat sheet here.

Related algorithms and techniques

• Floyd’s Cycle detection Algorithm

• Reservoir sampling

• Dummy Node

• Two pointers

• Recursion

• Skip list

5.2 Cheat sheet explained

The cheat sheet above is a summary of information you might need to know for an interview, but it’s usually not enough to simply memorize it. Instead, aim to understand each result so that you can give the answer in context.

The cheat sheet is broken into time complexity (the processing time for various linked list operations) and algorithm complexity (the amount of time and space used for common algorithms).

For more information about time and space requirements of different algorithms, read our complete guide to big-O notation and complexity analysis.

5.2.1 Linked list time complexity

The important point to remember when considering time complexity with linked lists is that accessing or finding a random element in a linked list takes linear time, or O(n), whereas adding or removing a known element takes constant time. This is the inverse of an array’s time complexity, and understanding this will help you with questions about where to use a linked list vs an array.

To improve the performance of a linked list for accessing and searching elements, sorted linked lists can be augmented with ancillary structures. One such structure is known as a skip list. A skip list creates multiple layers of linked lists, or a hierarchy, each layer including some fraction of the number of the nodes of the original list. This makes it possible to find the places of significant elements in a list faster by trading off space for time. Skip lists can be thought of as pre-computing binary search nodes in a list, or as a sparse index. Using skip lists mitigates some of the performance deficiencies of linked lists compared to arrays, bringing down search time to O(log n) time, at the expense of using more space. 

5.2.2 Linked list algorithm complexity

Sorting and searching linked lists may not be as common as they are for arrays, but can still be done. 

Sorting a linked list allows you to easily change the position of an element in the list, simply by re-assigning the links to its containing node. Compare this to changing the position of an element in an array, which generally means copying and moving multiple other elements, using extra temporary space.

However, to access a random element takes far longer in a linked list than in an array. Mergesort is preferred over Quicksort with a linked list, as Quicksort has a heavier reliance on random access to elements, which is slower in linked lists than arrays.

Search algorithms operating naively on linked lists generally take longer than searching in an array, due to the lack of inherent random access required by algorithms such as binary search. However, these algorithms can be sped up to similar time orders of complexity by using techniques such as skip lists, and using fast and slow pointers.

6. Mock interviews for software engineers

Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only linked lists but also the rest of the relevant data structures. Check out our guides for questions, explanations and helpful cheat sheets.

• Arrays
• Strings
• Stacks and Queues
• Trees
• Graphs
• Maps
• Heap
• Coding interview examples (with solutions)

Once you’re confident on all the topics, you’ll want to start practicing answering coding questions in an interview situation.

One way of doing this is by practicing out loud, which is a very underrated way of preparing. However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your interview skills.

That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.

Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.