In which data structure is inserting a new element faster: in LinkedList or in ArrayList?

Inserting a new element into a LinkedList is usually faster than into an ArrayList, especially if the insertion is not at the end of the list.

The reason is that a LinkedList is a doubly linked list, where each element contains references to the previous and next elements. To insert, it is enough to change a few links, which takes O(1) time if the position is known.

In contrast, data in an ArrayList is stored in an array. When inserting in the middle or at the beginning, all subsequent elements need to be shifted, which takes O(n) time.

However, if the insertion is at the end:

• ArrayList inserts the element in amortized O(1) time (if no array resizing is needed).
• LinkedList also inserts in O(1), if there is a reference to the last element.

Thus, for insertions at arbitrary positions, LinkedList is faster, and for insertions at the end — roughly the same.