4

Which is faster - inserting an element at the end of an array or a linkedlist ?

Praveen Kishor
  • 2,413
  • 1
  • 23
  • 28
  • By array do you mean ArrayList or an actual Array? Because adding to any point in an array is the same speed but it can't get longer – Richard Tingle May 07 '17 at 17:20
  • 1
    The key things here: **subtle** details matter. So be might want to update your question to be really precise. And you want to look at: http://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations – GhostCat May 07 '17 at 17:55
  • Probably a duplicate of [Performance on Java ArrayList vs LinkedList, pertaining to only Creation/Insertion and sorting](http://stackoverflow.com/q/29584600/642706), [Java ArrayList and LinkedList - adding element at end implementation details](http://stackoverflow.com/q/14496638/642706), [When to use LinkedList over ArrayList?](http://stackoverflow.com/q/322715/642706), [ArrayList vs LinkedList Java](http://stackoverflow.com/q/24963620/642706), [java linkedlist slower than arraylist when adding elements?](http://stackoverflow.com/q/5346039/642706). – Basil Bourque May 07 '17 at 18:55

2 Answers2

10

I assume you meant ArrayList when you said "array", since in Java you can't "add" to a full array.

Firstly if you're "inserting at the end" you're actually appending to the end not, "inserting". This distinction is important because inserting into an ArrayList at an arbitrary position is an O(n) operation, because all elements to the right must be "shifted" along by one position to make room for the element being inserted.

Adding to (the tail of) a LinkedList is always a O(1) (constant time) operation.

Adding to an ArrayList is usually a O(1) operation, but may be a O(n) operation if the backing array is full, because a new array must be allocated and every element copied across. In the general case of the array not being full, the performance of ArrayList is (slightly) faster than LinkedList, but the difference is very small.

The amortised cost of both is the same, but if constant time is required every time, only a LinkedList can do it.

Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154
Bohemian
  • 412,405
  • 93
  • 575
  • 722
  • 1
    And to answer what was asked, adding to the "end" of an array will result in an `IndexOutOfBoundsException` if the index is `>=` the array length or `<0`, O(1) otherwise. – Lew Bloch May 07 '17 at 17:25
  • *"I assume you meant ArrayList when you said "array", since in Java you can't "add" to a full array."* Who said it was full? – Michael May 07 '17 at 17:52
1

Appending an element to the end of Array would be faster then Adding to a LinkedList as adding to a LinkedList always means creation of a cell at the end of the list and then adding a value to it. In Array you just add a value to existing cell. However, in Array if it is already full and doesn't have a space you will get IndexOutOfBoundsException while in the LinkedList you will never have this problem as the List will always grow according to your needs. Also there is distinct difference between LinkedList and ArrayList with ArrayList there is a random access which means the access to any element is always O(1) while in LinkedListit is always sequential access which means that access time will differ depending on the index and in worst case scenario is O(n). However, Appending to LinkedList is Always O(1) but not so in ArrayList With ArrayList if it is not full it will be O(1) but if it is full it will first grow by more then one cell and only ten it will add the value, so the worst case scenario is O(n)

Michael Gantman
  • 7,315
  • 2
  • 19
  • 36