Which is faster - inserting an element at the end of an array or a linked list
arrays, java, linked-list
Solution
I assume you meant `ArrayList` when you said "array", since in Java you can't "add" to a full array.
Firstly if you're "inserting at the end" you're actually appending to the end not, "inserting". This distinction is important because inserting into an ArrayList at an arbitrary position is an O(n) operation, because all elements to the right must be "shifted" along by one position to make room for the element being inserted.
Adding to (the tail of) a `LinkedList` is always a O(1) (constant time) operation.
Adding to an ArrayList is usually a O(1) operation, but may be a O(n) operation if the backing array is full, because a new array must be allocated and every element copied across. In the general case of the array not being full, the performance of ArrayList is (slightly) faster than LinkedList, but the difference is very small.
The amortised cost of both is the same, but if constant time is required every time, only a LinkedList can do it.
Problem
Which is faster - inserting an element at the end of an array or a linkedlist ?