ArrayList size time complexity

Performance Analysis of ArrayList and LinkedList in Java

A detailed analysis of ArrayList and LinkedList in Java.

by

Anant Mishra

Like (5)

Comment

Save

Tweet

61.02K Views

Join the DZone community and get the full member experience.

ArrayListandLinkedListare frequently used classes in the Java collection framework. If you know only understand basic performance comparisons ofArrayListandLinkedList, but not the minor details of these two classes, then this article is for you.

" ArrayListshould be used where more search operations are required, and LinkedListshould be used where more insert and delete operation is needed."

ArrayListuses theArraydata structure, and LinkedList uses theDoublyLinkedListdata structure. Here, we are going to discuss how the underlying data structure affects the performance of insert, search, and delete operation onArrayListandLinkedList.

Below is an example of different operations usingArrayListandLinkedList.

Now, we will compare similar operations onArrayListandLinkedListand see which is more efficient in terms of performance and why.

Insert Value at Last Index(Block 1 and 2)

When we insert a value at last index, ArrayList has to —

• Check whether the underlying array is already full or not.

• If the array is full then it copies the data from the old array to new array(size double than an old array),

• Then add the value at the last index.

On the other hand, LinkedList simply adds that value at the tail of the underlying DoublyLinkedList.

Both have time complexity O(1), but due to the added steps of creating a new array in ArrayList its worst-case complexity reaches to order of N, that is why we prefer using LinkedList where multiple inserts are required.

Insert Value at Given Index(Block 3 and 4)

When we insert a value at a given index, ArrayList has to-

• Check whether the underlying array is already full or not.

• If the array is full then it copies the data from the old array to a new array(size double than an old array).

• After that, starting from the given index, shift values by one index to create space for the new value.

• Then add the value at the given index.

On the other hand, LinkedList simply finds the index and adds that value at a given index by rearranging pointers of underlying DoublyLinkedList.

Both have time complexity O(N), but due to the added steps of creating a new array in ArrayList, and copying the existing values to the new index, we prefer using LinkedList where multiple inserts are required.

Search by Value(Block 5 and 6)

When we search any value in ArrayList or LinkedList, we have to iterate through all elements. This operation has O(N) time complexity. It looks like ArrayList and LinkedList both will have the same performance.

Here we need to notice that array(underlying data structure of ArrayList) stores all values in a continuous memory location, but DoublyLinkedList store each node at a random memory location. Iterating through continuous memory location is more performance efficient than random memory location, that is why we prefer ArrayList over LinkedList when searching by value.

Get Element by Index(Block 7 and 8)

When we get an element by Index then ArrayList is a clear winner.

ArrayList can give you any element in O(1) complexity as the array has random access property. You can access any index directly without iterating through the whole array.

LinkedList has a sequential access property. It needs to iterate through each element to reach a given index, so time complexity to get a value by index from LinkedList is O(N).

Remove by Value(Block 9 and 10)

It is similar to adding value at a given index. To remove an element by value in ArrayList and LinkedList we need to iterate through each element to reach that index and then remove that value. This operation is of O(N) complexity.

The difference is that to remove an element from LinkedList, we just need to modify pointers, which is O(1) complexity, but In ArrayList, we need to shift all elements after the index of the removed value to fill the gap created.

As shifting is costly operation then modifying pointers, so even after the same overall complexity O(N), we prefer LinkedList where more delete by value operation is required.

Remove by Index(Block 11 and 12)

To remove by index, ArrayList find that index using random access in O(1) complexity, but after removing the element, shifting the rest of the elements causes overall O(N) time complexity.

On the other hand, LinkedList takes O(N) time to find the index using sequential access, but to remove the element, we just need to modify pointers.

As shifting is costly operation than iterating, so LinkedList is more efficient if we want to delete element by index.

Time complexity of array/list operations [Java, Python]

yourbasic.org

To write fast code, you must know the difference between constant and linear time array operations.

Accidentally inefficient list code with quadratic time complexity is very common and can be hard tospot, but when the list grows your code grinds to ahalt.

This text takes a detailed look at the performance of basic array operations and discusses alternatives to a standard array. It also includes cheatsheets ofexpen­sive list operations in Java and Python.

Introduction to Dynamic Array

To learn about Dynamic Array in depth, go through this article.

Problem with Array is that it has fixed size. If user does not know then size of array or data beforehand then the solution is to use Linked List.

The problem with Linked list is the memory access is slow. Hence, Dynamic Array comes into picture which is a modified version of Array.

Dynamic Array is also called ArrayList in Java and Vector in C++.

In Dynamic array, the size of the array can be changed at time of execution of program. Basically, what we do in Dynamic Array is create a resize function and the size is adjusted according to input by user.

The key idea is both adding and deleting element will continue as if it is an ordinary array but when there is no space left in the array, the size of the array will be doubled and all existing elements will be copied to the new location.

With addition to resize function, all elements of previous array is copied to new array and then new element is appended. This new array is Dynamic Array.

The previous array memory is then dis-allocated / freed.

Normally, we make the size of array twice but that totally depend upon situation or what user wants.

Operations in a Dynamic Array:

• Resize Method
• Add Method (with add at a specific index)
• Delete Method (with delete at a specific index)