3

For the method add of the ArrayList Java API states:

The add operation runs in amortized constant time, that is, adding n elements requires O(n) time.

I wonder if it is the same time complexity, linear, when using the add method of a LinkedList.

FranXh
  • 4,481
  • 20
  • 59
  • 78
  • 1
    possible duplicate of [Constant Amortized Time](http://stackoverflow.com/questions/200384/constant-amortized-time) – Brian Roach Feb 12 '12 at 22:59

3 Answers3

10

This depends on where you're adding. E.g. if in an ArrayList you add to the front of the list, the implementation will have to shift all items every time, so adding n elements will run in quadratic time.

Similar for the linked list, the implementation in the JDK keeps a pointer to the head and the tail. If you keep appending to the tail, or prepending in front of the head, the operation will run in linear time for n elements. If you append at a different place, the implementation will have to search the linked list for the right place, which might give you worse runtime. Again, this depends on the insertion position; you'll get the worst time complexity if you're inserting in the middle of the list, as the maximum number of elements have to be traversed to find the insertion point.

The actual complexity depends on whether your insertion position is constant (e.g. always at the 10th position), or a function of the number of items in the list (or some arbitrary search on it). The first one will give you O(n) with a slightly worse constant factor, the latter O(n^2).

Martin Probst
  • 9,497
  • 6
  • 31
  • 33
  • Ok, this makes sense. I am adding to the front of the lists so for the ArrayList will be quadratic then and for the linked list linear – FranXh Feb 12 '12 at 22:54
  • 2
    True, but adding to the front is better done with `ArrayDeque` which will excel for this task. There almost always are structures better than `LinkedList` :) – alf Feb 12 '12 at 23:01
  • @BrianRoach Adding an element to the head of an ArrayList would not be O(1), but rather O(n) as Martins said. – Roger Lindsjö Feb 12 '12 at 23:05
4

In most cases, ArrayList outperforms LinkedList on the add() method, as it's simply saving a pointer to an array and incrementing the counter.

If the woking array is not large enough, though, ArrayList grows the working array, allocating a new one and copying the content. That's slower than adding a new element to LinkedList—but if you constantly add elements, that only happens O(log(N)) times.

When we talk about "amortized" complexity, we take an average time calculated for some reference task.

So, answering your question, it's not the same complexity: it's much faster (though still O(1)) in most cases, and much slower (O(N)) sometimes. What's better for you is better checked with a profiler.

alf
  • 8,377
  • 24
  • 45
3

If you mean the add(E) method (not the add(int, E) method), the answer is yes, the time complexity of adding a single element to a LinkedList is constant (adding n elements requires O(n) time)

As Martin Probst indicates, with different positions you get different complexities, but the add(E) operation will always append the element to the tail, resulting in a constant (amortized) time operation

Cody Gray - on strike
  • 239,200
  • 50
  • 490
  • 574
rodrigo.garcia
  • 557
  • 7
  • 11
  • 1
    `add(E)` operation will always append the element to the tail, resulting in a constant time operation — not exactly true, it can well be O(N) for `ArrayList`. – alf Feb 12 '12 at 23:07
  • 1
    @alf That's true, when the `ArrayList` reaches it's limit and has to be regenerated. I added an aclaration that it runs in constant (amortized) time – rodrigo.garcia Feb 18 '12 at 00:49