Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Space Versus Time Tradeoffs
The automatic size changes provided by the ArrayList type can save you a lot of coding time. But what about the efficiency side of things? The JDK documentation provides some details about this. The following methods run in what is called constant time: size(), isEmpty(), get(), set(), iterator(), and listIterator(). So, you can expect these methods to be very efficient. The add operation is said to run in amortized constant time. This means that adding n elements requires O(n) time. So, additions require time proportional to the list size. It's important that this is the case. If the time required happened to be O(n2) or worse, then as the list grows, the efficiency would markedly deteriorate. You'll only see these issues becoming important when your list has hundreds of thousands of entries.
An application can improve its efficiency by explicitly increasing the capacity of an ArrayList instance before adding a large number of elements. This can be done using the ensureCapacity operation, and its use helps to reduce the amount of incremental memory reallocation.