Section Menu

How do I use this section?

1. LESSON

What Is the Linked List Data Structure?

In the world of software development, when it comes to organizing data, there are many tools that could do the job. The trick is to know which tool is the right one to use for our given purpose. As a reminder: regardless of which language we start coding in, one of the first things that we encounter are data structures, which we should be fam...

41 minutes Mark Completed

2. LESSON

Points On Slow and Fast Pointers

Objective: In this lesson, we'll cover the Floyd-Warshall Algorithm, and focus on these outcomes: You'll learn what slow and fast pointers are. We'll show you how to use this concept in programming interviews. You'll see how to utilize this concept in challenges. There are so...

59 minutes Mark Completed

3. LESSON

Circular Linked List vs. Doubly Linked List

In the wonderful world of computer science, linked lists play a fundamental role in organizing and storing data. These dynamic data structures consist of elements known as nodes, each linking to the next, forming a chain of connected elements. Imagine a treasure hunt, where every clue leads to the next. Now, *picture two spec...

43 minutes Mark Completed

4. CHALLENGE

Find the Intersection of Two Linked Lists

Assume you have a Linked List implementation that has the following API: // prepend to start of list #prepend(val); // appends to end of list #append(val); // get an array of node values (for testing) #toArray(); Can you write a method getIntersection(list1, list2) to find the intersection of two linked lists? <img...

Difficulty: 4/10 Mark Completed

5. CHALLENGE

Grab a Random Node

Given a linked list, can you write a method to get a random node within it? Let's assume you're given a random node generator. The linked list will have at least 2 nodes, and may look something like this: 1 -> 2 -> 3 -> 4 The odds of getting any number between 1 and 4 inclusive should be the exactly the same. <img...

Difficulty: 4/10 Mark Completed

6. CHALLENGE

Swap Every Two Nodes in a Linked List

Write a recursive algorithm that swaps every two nodes in a linked list. This is often called a pairwise swap. For example: `js /* original list 1 -> 2 -> 3 -> 4 after...

Difficulty: 4/10 Mark Completed

7. CHALLENGE

Union of Linked Lists

Now that we've implemented a Linked List, let's start operating on it! Assume you have a Linked List implementation with this definition: `js class LinkedList { constructor() { this.head = null; this.tail = null; } prepend(newVal) { const currentHead = this.head; cons...

Difficulty: 4/10 Mark Completed

8. CHALLENGE

Delete Nodes From A Linked List

Now that we've implemented a linked list, can you write a method that will delete all nodes of a given value? You're given the foll...

Difficulty: 4/10 Mark Completed

9. CHALLENGE

Implement a Linked List

Let's implement a linked list, a data structure that serves as one of the fundamental building blocks of many other data structures. A linked list is defined as a linear data structu...

Difficulty: 4/10 Mark Completed

10. CHALLENGE

Merge Sorted Linked Lists

Write an algorithm to merge two sorted linked lists and return it as a new sorted list. The new list should be constructed by joining the nodes of the input lists. You may a...

Difficulty: 5/10 Mark Completed

11. CHALLENGE

Delete Node From End

Removing the Nth Node From a Linked List's End: A Single-Pass Approach Get ready to sail through a classic problem: Removing the nth node from the end of a linked list in a single pass. By the end of this lesson, you'll be able to wave goodbye to that pesky nth node and still maintain the list's structure. ![Linked List Vi...

Difficulty: 6/10 Mark Completed

12. CHALLENGE

Reverse a Linked List

You're sent a linked list of numbers, but it's been received in the opposite order to what you need. This has happened multiple times now, so you decide to write an algorithm to reverse the lists as they come in. The list you've received is as follows: 7 -> 2 -> 21 -> 6 -> 42 -> 10 Write an algorithm for a method `rever...

Difficulty: 6/10 Mark Completed

13. CHALLENGE

Linked List to Binary Search Tree

We're given a sorted singly linked list (that is, a linked list made of nodes with no pointers to the previous node) where the elements are already arranged in ascending order. `js // -9 -> -2 -> 3 -> 5 -> 9 // Linked List Node Definition: function Node(val) { this.val = val; this.next = null; } ` Can you...

Difficulty: 7/10 Mark Completed

14. CHALLENGE

Add Linked List Numbers

We're provided the following two linked lists: 1 -> 2 -> 3 -> 4 and 2 -> 5 -> 8 Each one represents a number in reversed order, so 1 -> 2 -> 3 -> 4 represents 4321 and 2 -> 5 -> 8 represents 852 (note: for an extra challenge, consider if they weren't reversed). The lists are guaranteed to have at least one node and...

Difficulty: 7/10 Mark Completed

15. CHALLENGE

Detect Loop in Linked List

What is the best way to find out if a linked list contains a loop? You're given the following data structure as the definition of a linked list node: `js class LinkedListNode { constructor(val) { this.val = val; this.next = null; } } ` A loop or a cycle in graph...

Difficulty: 7/10 Mark Completed

16. CHALLENGE

Design A Least Recently Used (LRU) Cache

A cache (pronounced cash) is a place of storage that allows for faster data retrieval. Separate from the main data storage, it's usually faster memory that houses frequently accessed values. With a cache in place, when a client application needs to access data, it'll check the cache first before going to main memory. As an e...

Difficulty: 7/10 Mark Completed

17. CHALLENGE

Merge K (Multiple) Sorted Lists

You're given an array of multiple sorted linked lists. Can you write a method that returns it transformed into a single sorted linked list? Each linked list can be represe...

Difficulty: 8/10 Mark Completed

Cheat Sheet

• Quick summary: a linear collection of elements ordered by links instead of physical placement in memory.
• Important facts:
  • Each element is called a node.
    • The first node is called the head.
    • The last node is called the tail.
  • Nodes are sequential. Each node stores a reference (pointer) to one or more adjacent nodes:
    • In a singly linked list, each node stores a reference to the next node.
    • In a doubly linked list, each node stores references to both the next and the previous nodes. This enables traversing a list backwards.
    • In a circularly linked list, the tail stores a reference to the head.
  • Stacks and queues are usually implemented using linked lists, and less often using arrays.
• Pros:
  • Optimized for fast operations on both ends, which ensures constant time insertion and deletion.
  • Flexible capacity. Doesn't require setting initial capacity, can be expanded indefinitely.
• Cons:
  • Costly access and search.
  • Linked list nodes don't occupy continuous memory locations, which makes iterating a linked list somewhat slower than iterating an array.
• Notable uses:
  • Implementation of stacks, queues, and graphs.
• Time complexity (worst case):
  • Access: O(n)
  • Search: O(n)
  • Insertion: O(1)
  • Deletion: O(1)
• See also:
  • What Is the Linked List Data Structure?
  • Implement a Linked List
  • Interview Problems: Linked Lists