Understanding ArrayList and LinkedList Internals During a Java Interview

The author begins with a brief motivational note before describing a recent interview with a junior Java candidate who was only familiar with ArrayList and had limited knowledge of other List implementations.

During the interview, the interviewer asks about other List types, leading to a discussion of LinkedList and the fundamental differences between array‑based and node‑based collections.

He explains that an array occupies a contiguous block of memory, enabling constant‑time random access (O(1)). For example, accessing the second element translates to the pointer operation *(a + 1) , where the base address a is offset by one.

Because arrays have a fixed size, ArrayList internally creates a new, larger array and copies existing elements when the current array fills up, allowing dynamic growth while preserving O(1) index access.

In contrast, a LinkedList consists of nodes allocated individually by the operating system; each node stores its element and a reference to the next node. This scattered allocation means that to reach an element by index, the list must be traversed from the head, resulting in linear time complexity O(n) and no true random access.

The author uses metaphors—arrays as a straight, well‑paved road and linked lists as a winding trail—to illustrate the trade‑offs, emphasizing that while ArrayList implements the RandomAccess interface, LinkedList does not.

He concludes with a reflective after‑note, noting the candidate’s appreciation for the patient explanations and hinting that future posts will include source‑code analysis of linear‑list insertion and deletion.