Java LinkedList

About LinkedList operation time complexity:

Adding to either end of a linked list does not require a traversal, as long as you keep a reference to both ends of the list. This is what Java does for its add and addFirst/addLast methods.

Same goes for parameterless remove and removeFirst/removeLast methods - they operate on list ends.

remove(int) and remove(Object) operations, on the other hand, are not O(1). They requires traversal, so their costs are O(n).