InfosysJavaEasy
What is the difference between ArrayList and LinkedList?
JavaCollectionsArrayListLinkedListData StructuresPerformanceTime Complexity
Question
Compare ArrayList and LinkedList in Java. When would you use each? Explain the internal implementation, time complexity, memory usage, and real-world use cases.
Interview Answer
ArrayList uses a dynamic array and gives O(1) random access, while LinkedList uses nodes and is better for insertion/deletion at known positions. For most practical application code, ArrayList is the default choice because of better cache locality and lower memory overhead.
Explanation
ArrayList performs very well for reads and iteration due to contiguous memory layout. LinkedList avoids array-shift cost but pays traversal overhead for index-based operations. Use LinkedList for specific insertion patterns (head/middle with references), otherwise prefer ArrayList.
Key Points
- ArrayList: fast index access, better iteration speed
- LinkedList: efficient structural updates at known node positions
- Memory overhead is higher in LinkedList due to node pointers
- ArrayList is usually the better default in production
Common Mistakes
- Choosing LinkedList for frequent index lookups
- Ignoring traversal cost before insertion/deletion in LinkedList
- Assuming theoretical O(1) always wins in real JVM workloads
Likely Follow-Up Questions
- How does ArrayDeque compare for stack/queue use cases?
- When should CopyOnWriteArrayList be used?
- What happens to iterators during concurrent modification?
Interview Timing
Target speaking time: about 5 minutes.