MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Data Structures & Algorithms (DSA) Module 7

Linked lists interview questions

Interview questions on linked lists: short warm-ups, then what each harder question tests, the first step of a good answer and its follow-ups.

15 questions: 4 warm-ups and 11 with model answers · Levels: Fresher to senior

Warm-up questions

Short questions with short answers, each answered in full.

  1. Fresher

    Why does a singly linked list keep a tail reference, and what does keeping it cost?

    Answered in the lesson Singly linked lists: nodes and pointers

  2. Fresher

    Is deleting a node from a singly linked list O(1)?

    Answered in the lesson Singly linked lists: nodes and pointers

  3. Fresher

    What does a circular linked list give you that a list with head and tail references does not?

    Answered in the lesson Doubly linked and circular lists

  4. Fresher

    With fast and slow pointers on a list of even length, which middle do you get, and how do you get the other one?

    Answered in the lesson Fast and slow pointers: middles and cycles

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

  1. Fresher to mid

    An editor keeps each line of a 10-million-line log file as one node of a singly linked list. Inserting a line after the cursor is instant, but "go to line 5,000,000" takes about half a second. Explain both numbers, then change the design so that both operations are fast.

    What it tests
    Linking operation costs to memory access, estimating the time of a pointer walk, and choosing a structure that keeps cheap local edits while adding fast access by position.
    First step
    Count the work. Inserting after the cursor changes two links of a node the editor already holds. Reaching line 5,000,000 follows five million next references, and each is a read that cannot start before the previous one finishes. At roughly 100 ns for a read that misses the caches, five million reads take about 0.5 s. Then ask which operations the editor needs most often.
    Follow-ups

    From the lesson Singly linked lists: nodes and pointers

    Opening the model answers with your pass…

    Model answers open with any MySmartCoPilot pass.

    • Pro pass · 1 week₹79$2.99
    • 30 days₹179$5.99
    • 1 year₹1,699$45

    One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

    Choose a passI have a licence key

    It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  2. Fresher to mid

    Your linked-list class passes its unit tests, but in production its size counter and its tail reference sometimes disagree with the nodes, and appended values occasionally vanish. Which operations most likely break them, and how would you make this kind of bug impossible to miss?

    What it tests
    Treating cached fields as invariants, finding the edge cases that change the last node or the count, and catching drift with an invariant check and random tests against a simple model.
    First step
    List every operation that can change the last node or the count: appending, adding to an empty list, inserting after the tail, removing the last node, removing the only node and clearing. A vanished append means a stale tail, left on a node that is no longer reachable. Then write check(): walk from the head, count the nodes and compare the count and the last node with size and tail.
    Follow-ups

    From the lesson Singly linked lists: nodes and pointers

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  3. Fresher to mid

    After a deletion, your doubly linked list prints correctly from front to back, but walking from the back still shows the deleted item. What went wrong, how do you find every bug of this kind before release, and how do sentinel nodes change the code?

    What it tests
    Reasoning about paired links, writing an invariant that checks both directions, and using sentinels to remove the end cases where such slips hide.
    First step
    The forward walk follows next and the backward walk follows prev, so the deletion fixed the predecessor's next but not the successor's prev: a removal changes two links, and only one changed. Write check(): every node's next.prev and prev.next must point back at it, and both walks must count size. Then run it after every step of random tests.
    Follow-ups

    From the lesson Doubly linked and circular lists

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  4. Mid to senior

    A Java service buffers 20 million small integers in a LinkedList<Integer> used as a first-in, first-out queue, and the heap is far larger than the data suggests. Estimate the memory per element, compare ArrayDeque<Integer> and a ring buffer of int, and choose one.

    What it tests
    Estimating object overhead on the JVM, separating the cost of nodes from the cost of boxing, and choosing a queue by the operations it really needs.
    First step
    Count the objects per element. A LinkedList element is a node with three references, item, next and prev, plus an Integer. On a 64-bit JVM with compressed references that is about 24 + 16 = 40 bytes, so 20 million elements take about 800 MB. ArrayDeque drops the node and keeps a 4-byte slot per element, and an int ring buffer drops the Integer as well.
    Follow-ups

    From the lesson Doubly linked and circular lists

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  5. Mid to senior

    Design the run queue of a round-robin scheduler: jobs arrive at any time, finish at any time, and the next job must get its turn in O(1). Which list do you use, where does a new job go, and what goes wrong when a job finishes while it holds the turn?

    What it tests
    Choosing a circular or doubly linked structure for O(1) turns and removals, placing new arrivals fairly, and keeping the turn pointer valid through removals.
    First step
    Keep the jobs in a circular doubly linked list with a pointer to the job that holds the turn, and a map from job id to node so that a job finishing anywhere is removed in O(1). A new job goes just before the current one, at the back of the line, so that every job already waiting runs before it.
    Follow-ups

    From the lesson Doubly linked and circular lists

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  6. Fresher to mid

    Explain why, after the fast and slow pointers meet inside a loop, putting one pointer back on the head and stepping both one node at a time makes them meet exactly at the loop's first node. Use distances, and cover a loop that starts at the head.

    What it tests
    Proving an algorithm with distances and modular arithmetic instead of describing it, and checking the proof on the boundary cases.
    First step
    Name the lengths: a tail of μ nodes, a loop of λ, and a meeting a nodes past the loop's first node after t steps. The slow pointer walked t = μ + a; the fast one walked 2t, which is t plus whole laps. So t is a multiple of λ, and so is μ + a. Then ask where μ more steps from the meeting point lead.
    Follow-ups

    From the lesson Fast and slow pointers: middles and cycles

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  7. Mid to senior

    A nightly job follows parent links through 50 million records to find each record's root, and one night it never finishes: bad data created loops. Report every record on a loop while keeping the job linear in time. What memory does that need, and why is Floyd's method alone not enough?

    What it tests
    Moving from one chain to many chains that merge, why cycle detection from every record is quadratic, and marking records with a small state array.
    First step
    Every record has one parent, so the records form chains that merge into trees and end at a root or in a loop. Floyd's method from every record repeats the shared parts, up to O(n²) steps. Keep a state per record instead: unvisited, on the current walk, or done. That is two bits per record, about 12.5 MB for 50 million.
    Follow-ups

    From the lesson Fast and slow pointers: middles and cycles

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  8. Mid to senior

    A simulation advances a 200-byte state with a deterministic step function, and you must find when a state first repeats. Tests suggest it repeats after about 10⁸ steps. Compare a set of seen states, Floyd's method and Brent's method on time and memory, with numbers, and pick one.

    What it tests
    Turning a repeated-state problem into cycle detection, estimating memory and step counts, and trading stored states for recomputed steps.
    First step
    Treat the step function as next pointers: the states form a chain with a tail and a loop, about 10⁸ states in all. A set of seen states stores up to 10⁸ states of 200 bytes, 20 GB before any overhead. Floyd's and Brent's methods keep two states, 400 bytes, and call the step function a few times more often instead.
    Follow-ups

    From the lesson Fast and slow pointers: middles and cycles

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  9. Mid to senior

    A teammate defends a recursive list reversal because it is "tail recursive": each call ends with the recursive call. On a list of a million nodes, is it safe in Python, Java, C++ built with clang -O2, and Scheme? How would you make sure in each?

    What it tests
    Knowing which languages guarantee that tail calls use no stack, what an optimiser may or may not do, and checking a claim about stack depth with a test instead of a belief.
    First step
    Separate a guarantee from a hope. Scheme's standard requires proper tail calls, so the accumulator version runs in constant stack there. CPython keeps a frame for every call and stops at its recursion limit, 1,000 by default. Java does not remove tail calls either. A C++ compiler may turn the call into a jump at -O2, but the language promises nothing.
    Follow-ups

    From the lesson Reversing linked lists and sublists

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  10. Fresher to mid

    Reverse the nodes between positions left and right of a singly linked list in one pass. Walk through 1 → 2 → 3 → 4 → 5 with left = 2 and right = 4, name every pointer you change, and say which inputs break code that has no dummy node.

    What it tests
    Reconnecting both ends of a reversed sublist, counting the pointer writes, and finding the boundary cases that a dummy node removes.
    First step
    Walk to the node before the sublist, node 1, and remember node 2, which will end the reversed sublist. Reverse exactly right − left + 1 = 3 nodes with the three-pointer step. Then reconnect: node 1 points at node 4, and node 2 points at node 5, which the loop leaves in curr.
    Follow-ups

    From the lesson Reversing linked lists and sublists

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  11. Mid to senior

    How do you reverse a doubly linked list with head and tail sentinels in place, and which links do candidates usually forget? Then explain how a list class could offer reversal in O(1) time, and what that costs every other operation.

    What it tests
    Adapting the reversal to two links per node and to sentinels, checking it with the paired-link invariant, and trading a direction flag against the cost of every operation.
    First step
    In a doubly linked list every node already has both directions, so reversal is a swap: for every real node, exchange prev and next. The sentinels need care: either swap their roles, so that the old tail sentinel becomes the head, or relink them to the new first and last nodes. Then run the paired-link check from both ends.
    Follow-ups

    From the lesson Reversing linked lists and sublists

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

All Data Structures & Algorithms (DSA) interview questions · The Data Structures & Algorithms (DSA) track