14

I return a List from my A class. I would like to remove the first element from the list and add it as the last element to the same list. I did it this way.

myList.add(myList.get(0));
myList.remove(0);

The target hardware is Android OS. Should I code my A class in a way that it returns an ArrayList, or a LinkedList? Which would be better for the following scenarios:

  1. myList has always 100 elements

  2. myList has always 10 elements

Maybe I see a problem where there is none. Do you think I shouldn't care for performance in this case, since the problem size is (for both 1 and 2) is small?

I am aware of the saying "premature optimisation is the root of all evil". That's why I am hesitating before changing my implemantation (as for now, my A object returns an ArrayList).

teobais
  • 2,820
  • 1
  • 24
  • 36
GA1
  • 1,568
  • 2
  • 19
  • 30
  • 2
    use `LinkedList` if you are adding/removing/updating element frequently . – N J Dec 28 '15 at 08:56
  • 2
    The `premature optimisation is the root of all evil` motto is **bullshit**. – Phantômaxx Dec 28 '15 at 09:27
  • If you are adding, and removing only from the first and last element, LinkedList is very good for that, as it contains a pointer to the first and last node. – WalterM Dec 28 '15 at 10:12
  • @Fantômas Choosing the correct collection is NOT premature optimization, it's simply good programming (Choosing the wrong collection is Very Bad Programming). Premature optimization is typically degrading code readability in exchange for an assumed and untested theoretical speed boost when it might not even be needed. – Bill K Nov 18 '19 at 18:54
  • @BillK I do love premature optimization. So, my point of view and yours. Two different schools. – Phantômaxx Nov 19 '19 at 08:26

1 Answers1

21

Short answer you should go for LinkedList if you are adding/removing/updating element frequently, especially for the case of first/last elements, as it contains a pointer to the first and last node

Long answer LinkedList add method gives O(1) performance while ArrayList gives O(n) in the worst case. LinkedList is faster. It will just reference the nodes so the first one disappears:


In addition, ArrayList is good for write-once-read-many or appenders, but bad at add/remove from the front or middle.

enter image description here

For instance, removing an element from a linked list costs O(1), while doing so for an array (array list) costs O(n).

But, this is not always a rule, as bigoh post states:

Big-oh notation can give very good ideas about performance for large amounts of data, but the only real way to know for sure is to actually try it with large data sets. There may be performance issues that are not taken into account by big-oh notation, eg, the effect on paging as virtual memory usage grows. Although benchmarks are better, they aren't feasible during the design process, so Big-Oh complexity analysis is the choice.

The above is validated with this post, where LinkedList also proved slow.

Finally, for further/future reference, please take a look at the use case comparison of them, according to javaconceptoftheday.com:enter image description here

References
http://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html http://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

Community
  • 1
  • 1
teobais
  • 2,820
  • 1
  • 24
  • 36