4

I have written an algorithm that has a lot of appending and removing items to an end of a data structure (basically last in first out).

Now for some reason, when I do this operation with ArrayList, it is much faster than a LinkedList, even through ArrayList requires the overhead of relocations. It's not even slightly faster. It's faster by miles!

Why is this?

Yahya Uddin
  • 26,997
  • 35
  • 140
  • 231
  • 1
    I think the best way to implement LIFO behaviour with standard collections is with an `ArrayDeque`. It's a *lot* faster than a `LinkedList` and I think it's also slightly faster than an `ArrayList`. It's better to use an `ArrayDeque` anyway as the `Deque` interface is more appropriate for this than the `List` interface. – Paul Boddington Apr 22 '15 at 01:32

3 Answers3

6

Well, each time you insert into a LinkedList, a new object is allocated. When you insert into an ArrayList, allocation only occurs if there is no more space. At that point it doubles the available space and you won't allocate again until you are out of space. So the cost of creating the objects in the LinkedList is almost certainly the difference.

pens-fan-69
  • 979
  • 7
  • 11
-2

From this answer

The remove time complexity is O(n-index) for ArrayList, which is O(1) as you are removing the last element, while being O(n) for LinkedList.

Community
  • 1
  • 1
M. Shaw
  • 1,742
  • 11
  • 15
-2

Inserting and deleting at the end of a LinkedList means iterating all the way through it to get to the last elment. Once the pointer is there it is pretty simple.

Inserting to an ArrayList is a little more expensive if the amount of elements in the ArraList is already at the size of the class' array. Which will mean it would have to create a new array and copy the elements. Other than it has direct access to the last element which makes it really simple to add and remove elements.

P.S. you might also consider using a Stack. Not sure of your requirements but just as a sugestion.

truenite
  • 67
  • 1
  • 8
  • 1
    If you check the source code you will see the LinkedList maintains a tail pointer. It does not have to go all the way through the list to get to the end. Also, LinkedList implements Deque which works just fine for a Stack. – pens-fan-69 Apr 22 '15 at 01:09
  • That is true if he is using the Java util libraries classes. I guess the allocation time it is. – truenite Apr 22 '15 at 01:15
  • 1
    @truenite It is implicit in the Javadoc that any implementation has a tail pointer. Otherwise the following cannot be satisfied: "Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index." – user207421 Apr 22 '15 at 01:23
  • @EJP Yes. that is the case for java.util.LinkedList. – truenite Apr 22 '15 at 01:41