Comparison of execution efficiency between ArrayList and LinkedList

1、 Concept:

Generally, we all know that ArrayList * is a list derived from an array. Used as a general-purpose object container to replace the original vector. Allows us to access elements quickly, but it's a little slower to insert and delete elements from the middle of the list. Generally, you should only use listiterator to traverse an ArrayList forward and backward, and do not use it to delete and insert elements; Compared with LinkedList, its efficiency is much lower. LinkedList provides optimized sequential access performance, and can efficiently insert and delete in the middle of the list. However, in random access, the speed is quite slow. At this time, you should use ArrayList instead.

2、 Testing

Originally, I wrote some test classes to test the performance comparison between ArrayList and LinkedList. I found that they were not satisfactory. Today, I saw such a piece of code in thinking in Java. I personally think it was well written.

3、 Summary

First of all, I really boast that this code is really well written. Both the application of internal classes and the understanding of object-oriented are properly considered, and the template method pattern in the design pattern is used.

The test results are slightly different every time, but it is not difficult to draw the following conclusions:

1. Random access (i.e. get ()) and loop repetition in ArrayList are the most cost-effective. The reason is that ArrayList is based on array, so each element has its corresponding index, so it is much faster to locate an element randomly.

2. It is more efficient to perform sequential access, insert and delete actions in the LinkedList. The reason is that for the LinkedList, you only need to change one node node of its arrangement for insertion and deletion, while for the ArrayList, you need to constantly move the following elements to the front position to delete an element.

3. As for sequential access, it has always been thought that ArrayList is based on array arrangement and is continuously arranged in memory, which should be much faster. Then, it is found that it is not as expected after many tests, or ArrayList does not show its advantages, or even worse than the access speed of LinkedList. The reason is that LinkedList provides optimized sequential access performance.

4. ArrayList is thread safe and LinkedList is thread unsafe. This reason also leads us to seldom see LinkedList in normal programming.