0
 public class program {


   public static void main (String [] args) {
    ArrayList Arraylist = new ArrayList();
    long elements_to_fill = (long) 1E7;

    long Current_milies = (long) System.currentTimeMillis();


    for (int i = 0; i < elements_to_fill; i++) {
       Arraylist.add(i);
   }

    System.out.println("Insertion in array list takes " + (System.currentTimeMillis()-Current_milies) + " ms");


    LinkedList linkedlist = new LinkedList();

   Current_milies = ( long ) System.currentTimeMillis();

   for (int i = 0; i <elements_to_fill; i++) {
       linkedlist.add(i);
   }

   System.out.println("insertion in linked list take " + (System.currentTimeMillis() - Current_milies) + " ms");

 }
}

Output:

insertion in array list takes 3652 ms

insertion is Linked list take 6862 ms

The same with : long elements_to_fill = (long) 1E5;

Output:

insertion in array list takes 16 ms

insertion in linked list takes 8 ms

Insertion is array list take less time compared to linked list if we add 1E7 elements

But on the other hand if we add 1E7 elements than insertion in insertion is array list takes more time compared to linked list. Why this is happening?

Community
  • 1
  • 1
Shahrukh
  • 16
  • 5
  • LinkedList: Slow access by index, efficient insert/delete at head, uses more memory, slower in most cases; ArrayList: fast access by index, slow insert/delete at head, efficient memory usage, faster in most cases. try with adding elements only at first place and not only at the end – XtremeBaumer Jul 21 '17 at 06:45
  • for `LinkedList`, it is an `O(1)` because you have a reference to the last element, for `ArrayList` it is also `O(1)` if there is no need to grow up the internal array – Andrew Tobilko Jul 21 '17 at 06:47
  • 1
    Beyond that: your attempts to **measure** are way to naive. Please read [this](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) in order to understand how to generate numbers that are meaningful. – GhostCat Jul 21 '17 at 06:49
  • Look at this, https://stackoverflow.com/questions/10656471/performance-differences-between-arraylist-and-linkedlist – Sagar Gautam Jul 21 '17 at 06:54
  • It's just that with 1E5 the real time of `add` is not significant, but at 1E7 it becomes – azro Jul 21 '17 at 08:02

1 Answers1

0
  • LinkedList: Slow access by index, efficient insert/delete at head, uses more memory, slower in most cases;
  • ArrayList: fast access by index, slow insert/delete at head, efficient memory usage, faster in most cases. try with adding elements only at first place and not only at the end As said in comment by XtremeBaumer

Example if you change to (with 1E5 elements (instead of E7 for you)) :

linkedList.add(0,i);   //9ms
arrayList.add(0,i);    //780ms  so 2 magnitude more

These numbers satisfy you ?

azro
  • 53,056
  • 7
  • 34
  • 70
  • if i change 1E7 to 1E5 than arraylist element insertion takes 11 ms while Linekdlist element insertion take 8 ms. how fast insertion take place by changing 1E7 to 1E5? – Shahrukh Jul 21 '17 at 07:22
  • @Shahrukh there is slightly a difference between `100000` and `10000000` elements which you insert. the time does increase the more elements you add. **but the most important point is to add elements at the beginning of the list and not at the end** – XtremeBaumer Jul 21 '17 at 07:36