linked list - Using LinkedList to Compute the Addition of Large Size of Numbers (Java) -

I have written a program that calculates the time taken to calculate n integer (randomly generated) Calculates the amount of an ArrayList in the sum of all the values ​​and in a way, I can compare time to the linked list in nanosecond. The problem is that when I entered size 10 ^ 6 (1,000,000) for the calculation, Did not take the time for the linkedlist, only ArrayList for. I have been waiting for more than 20 minutes to show up, but there is no output yet, however, when I use small numbers for the size of 10 ^ 3 or 10 ^ 4, then it works fine. So, I was wondering if there is a limit on the size of the linked list or not. If so, can I get permission to calculate the values ​​of 10 ^ 6 using Linkedlists?

I think how your code looks like.

  test for public squares {public static zero main (string [] args) {int LENGTH = 1000000; & Lt; Integer & gt; List = New Arrestist & lt; & Gt; (); For (int i = 0; i & lt; LENGTH; i ++) {list.add ((int) (100 * Math.rendum ())); } // start time int = 0; For (int i = 0; i  

This will be faster, at the time the time is running, it is likely to be less than 10th of a second. bus change new ArrayList & lt; & Gt; () code> to new linked list & lt; & Gt; () ... A component of approximately 1 million is likely to be slower in the timeline (I can estimate it with high level of reliability that I will be correct ...)

but why?

This is due to the received (int) method call!

• The time taken to call an ArrayList is a small constant, maybe 10 to 20 hardware clock Chakra, on a specific system where there are hundreds of billions of clock cycles per second. Some nanoseconds

• A linkedlist a received (i) starts from the beginning of the list for the call and i Skipping on the link one at a time. The time taken is clearly proportional to the value of i .

In the case of your test, from i to one billion Then in the linkedlist version, you repeat 1 million of a loop, where there are 0.5 million steps per recurrence (average). (In fact, this can be 0.25 million because one is linked to linkedlist , and according to @Macoto, meets (i) operation starts or ends in the end The list, which is near i .)

---

In technical terms, the ArrayList version of the Big O-Hour of the exam program The complexity is O (N) , and linkedlist version is (n squared ...) where n is the length of the list.

---

The interesting thing is that if you rewrite such summaries, the performance problem is resolved in the LinkedList case:

  // start time int sum = 0; For (integer v: list) {sum + = v; } // stop timing and report  

... because now you are using an iterator and get instead of calling next ( I) to get value.