Java LinkedList interview questions

Is insertion always O(1)?

No. Endpoint insertion has constant link work. Adding at an arbitrary index can spend O(n) finding that position. Inserting through an already-positioned ListIterator changes links in O(1). State which operation you mean.

Why can indexed traversal become quadratic?

Each get(index) starts another traversal. A loop over all indices sums those walks. Use an iterator to follow each link once instead.

What does remove(1) mean for LinkedList<Integer>?

It removes the element at index one. To remove the first integer value one, call remove(Integer.valueOf(1)). The two overloads also have different return types.

Does ConcurrentModificationException make it safe to share?

No. Fail-fast detection is best-effort. It cannot replace coordination across reads and structural edits. Choose an explicit locking policy or a collection designed for the required concurrent behavior.

Would you use it for a service queue?

Not without checking the requirements. ArrayDeque may fit single-threaded endpoint work with fewer allocations. A service queue may also require capacity limits, concurrent access, persistence, ordering guarantees, and retry policy.

Connected lessons

Continue with Java LinkedList: operations, internals and failure cases, Java LinkedList quiz.

Common Mistakes

Do not invent fixed node sizes without naming a JVM layout. Do not claim LinkedList avoids all copying: copying a list still visits its elements and allocates storage.

Follow up on the representation choice

Ask what the caller already knows at insertion time. An already-positioned iterator avoids a fresh position search, but a caller holding only a numeric index may need to traverse. A claim about link-editing cost should identify that precondition rather than call every insertion constant time.

Ask whether a shallow copy isolates a mutable element. It does not. The copied node sequence holds the same referenced elements, so a field change on one shared element can be seen through both lists. Snapshot membership and element ownership are separate answers.

Ask how to stop a worker waiting for task admission and what survives restart. Neither LinkedList nor ArrayDeque supplies a blocking wait or durable retry record. Changing an implementation without adding those contracts does not create a production service queue.

Continue with owned-node algorithms

Continue with Find the shared node of two Java linked chains by identity, Copy a Java linked chain with random references without retaining aliases.