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).