ArrayList vs LinkedList in Java: Implementation, Performance, and Usage

This article is part of a collection of Java interview questions and provides a detailed comparison between ArrayList and LinkedList, two fundamental collection classes in Java.

ArrayList is built on a dynamic array, offering fast random access and efficient addition of elements at the tail. However, inserting or deleting elements in the middle requires shifting array elements, which can be costly. When the internal array reaches its capacity, it expands by a factor of 1.5 (in JDK 1.8), and the maximum size is limited to Integer.MAX_VALUE-8 . The extra eight slots are reserved for header words, memory‑overflow protection, and to maintain the maximum capacity limit.

The article includes a portion of the ArrayList source code that demonstrates the expansion logic, accompanied by diagrams showing the growth process, tail insertion, and insertion at a specific index.

LinkedList, on the other hand, is implemented as a doubly linked list. Adding or removing elements only requires updating node pointers, making these operations fast, while random access requires traversing the list, resulting in slower average access times.

Source code excerpts illustrate how ArrayList.get(int index) directly accesses the underlying array, whereas LinkedList traversal is performed by a node(int index) method that walks the list from the head or tail.

In summary, for random‑access operations such as get and set , ArrayList outperforms LinkedList because the latter must move pointers. For frequent insertions and deletions, LinkedList has an advantage since ArrayList must shift elements. The article also presents a visual chart comparing the efficiency of both structures for various operations.

Source: blog.csdn.net/weixin_42468526/article/details/81178698