ArrayList vs LinkedList.

Hook: Interviewers love this one because the “best” list is really about how data moves when you read, insert, and delete.

Question: ArrayList vs LinkedList.

Answer: ArrayList stores items in a growable array, so it is fast for index-based access like get(5) and usually faster to iterate. LinkedList stores items as separate nodes connected by links, so it is better when you do lots of insertions or removals at the ends and already have the position. In real Java code, ArrayList is the default choice most of the time.

Interview-Ready Answer: “I usually pick ArrayList because it gives fast random access and better iteration performance due to contiguous storage. LinkedList is a doubly linked list, so it can help for queue-style operations or frequent end insertions and removals, but it uses more memory and get(i) is linear time. In practice, unless I truly need deque behavior, I reach for ArrayList.”

Big Picture

Detailed Explanation: Think of ArrayList as a row of seats and LinkedList as a paper chain. A seat number gets you to the person instantly; a paper chain lets you add or remove links easily, but finding the 80th link means walking through the chain.

How they work under the hood

1. ArrayList keeps its elements in a backing Object[] array. The array is contiguous in memory, so get(i) is just direct indexing.
2. When the array fills up, ArrayList allocates a bigger array and copies the old elements over. That copy is why a single append can occasionally be expensive, but across many appends it is amortized O(1), meaning the average cost stays low over time.
3. LinkedList stores each element in a separate Node. A node is a small object that keeps the value plus links to the previous and next nodes.
4. Because the links can be rewired, adding or removing at the front or back is O(1) once you are already at that end.
5. But get(i) on a LinkedList must walk node by node from the head or tail, whichever is closer, so it is O(n).
6. That means a loop like for (int i = 0; i < list.size(); i++) list.get(i) is fine for ArrayList, but can become painfully slow for LinkedList.

Comparison table

When and why to use each one

• Use ArrayList when you read often, loop often, or need fast random access by index.
• Use LinkedList when you truly need deque behavior, such as frequent addFirst/removeFirst or offer/poll style operations.
• If you want queue or stack behavior, ArrayDeque is often better than LinkedList because it is usually smaller and faster.

Performance and edge cases

• ArrayList grows by copying; the occasional resize costs time, but the average append is still very good.
• LinkedList has a large per-element cost because each node stores links in addition to the value. On a 64-bit JVM, that overhead can be tens of bytes per element, which matters at scale.
• Both are not thread-safe.
• Both use fail-fast iterators, meaning they usually throw ConcurrentModificationException if the list is structurally changed while you iterate without using the iterator’s own remove.
• LinkedList.size() is O(1) in Java, because it stores the count; many candidates wrongly think it must walk the list.

Memory trick: the winner is usually the one with the fewest surprises. For most business code, that is ArrayList.

Real-World Example: Imagine a checkout service that keeps a list of pending orders to display in an admin dashboard. A developer switches from ArrayList to LinkedList because they expect lots of inserts, but the dashboard still reads order #500 by index and loops through the whole list on every refresh. The result is worse latency, more CPU time, and a bigger heap. In production, the symptoms look like p95 response time jumping from milliseconds to seconds, APM traces pointing at list traversal, and users seeing the dashboard time out while the logs keep showing normal business events. The bug is not just “wrong Big-O”; it is choosing a structure that fights the real access pattern.

Follow-up & Tricky Questions:

• Why is ArrayList usually faster to iterate? Because its elements sit in one contiguous array, the CPU can prefetch memory efficiently. LinkedList jumps from node to node, which causes more cache misses.
• When would you actually choose LinkedList? Mostly when you need deque operations and frequent additions/removals at the ends, especially if you are already using it through the Deque interface.
• What is amortized O(1) for ArrayList append? Most appends are constant time, but occasional resizing copies the whole array. Averaged over many appends, the cost per append stays constant.
• Is LinkedList better for inserting in the middle? Only if you already have the iterator or node at that position. Finding the position is still O(n), so the full operation is often not better.
• Are these lists thread-safe? No. If multiple threads modify them, you need external synchronization or a concurrent collection.
• Is ArrayDeque better for queues and stacks? Usually yes. It avoids the per-node overhead of LinkedList and is often the fastest general-purpose deque in Java.
• Is LinkedList.size() O(n)? No, in Java it is O(1) because the list tracks its size internally. That is a common trap question.
• Does ArrayList always resize on every add? No. It only resizes when full, so most adds do not copy the whole array.
• Is random access fast in LinkedList because it has links? No. Links help you move one step at a time; they do not let you jump directly to index i.

Common Mistakes:

• Picking LinkedList because it sounds better for insertions. Correction: if you still need to search for the position, the traversal cost usually wipes out the benefit.
• Using LinkedList for lots of get(i) calls. Correction: use ArrayList when random access matters.
• Assuming LinkedList uses less memory because it has no big array. Correction: it usually uses more memory because each element needs a separate node object and two links.
• Forgetting that queue/stack use cases often want ArrayDeque, not LinkedList. Correction: prefer the simpler, faster deque unless you have a strong reason not to.

Memory Hook: ArrayList = seats in a theater; LinkedList = people holding hands in a line. Seats let you point to row 12, seat 5 instantly. Holding hands makes moving the ends easy, but finding the middle takes a walk.

Cheat Sheet:

• ArrayList: fast get, fast iteration, good default choice.
• LinkedList: fast end insert/remove, poor random access.
• Both are List implementations and both are not thread-safe.
• LinkedList.size() is O(1) in Java.
• For queues and stacks, ArrayDeque is often better than LinkedList.
• Rule of thumb: if you are unsure, start with ArrayList.

Practice Tasks:

• Create both lists with 10,000 integers and print the time to loop over them with for-each.
• Write a small queue using Deque and compare LinkedList with ArrayDeque.
• Replace a few LinkedList.get(i) calls in old code with a different data structure and observe the speedup.