Q26: What are the operational differences between ArrayList and LinkedList?
ArrayList: Backed by a dynamically resizing array. Provides $O(1)$ fast random index access. Insertions/deletions in the middle require shifting elements ($O(n)$).LinkedList: Backed by a Doubly Linked List. Index access requires traversing nodes ($O(n)$). Inserting or deleting known node pointers is $O(1)$.
Key Takeaways
- Use
ArrayListfor frequent reads and index lookups. - Use
LinkedList(orArrayDeque) when frequent head/tail insertions occur.
Knowledge Check
What is the time complexity of retrieving an element by index (list.get(500)) in an ArrayList?