ArrayList in Java

All elements are stored in contiguous memory locations, like a traditional array, but with the ability to resize dynamically.

GET Operation:

Getting an element at a specific index takes O(1) time complexity.

The formula for retrieving an element at a specific index:

memory_address = base_address + (index * element_size)

base_address: the address of the first element element_size: 4 bytes for int, 8 bytes for double,…

Example:

• base_address = 1000 (address of the first element)
• element_size = 4 bytes (for int)
• To access the value at index 2: 1000 + (2 *4) = 1008

INSERT Operation:

Requires shifting subsequent elements (especially when inserting at the middle or beginning)

The complexity is O(n)

Best case: Adding an element to the end of the list takes O(1) time complexity when there is enough capacity.

Worst case: Adding an element to the middle or beginning of the list takes O(n) time complexity

DELETE Operation:

Requires shifting subsequent elements (especially when inserting at the middle or beginning)

The complexity is O(n)

Best case: Deleting the last element of the list has a time complexity of O(1) since no shifting is required

Worst case: Deleting an element at the middle or beginning of the list has a time complexity of O(n), which requires shifting all subsequent elements.

RESIZING:

The default capacity size is 10

When the ArrayList exceeds its current capacity, it will create a new, 50% larger array and copy all existing elements into a new array.

Example of Resizing:

Initial capacity: 10.
When adding the 11th element:

1. A new array of size 15 (10 + 50% of 10) is created.
2. The existing 10 elements are copied into the new array.
3. The new element is then added.

SUMMARY

• An ArrayList is not synchronized and stores its elements in contiguous memory locations.

• GET operation has O(1) time complexity

• ADDING and REMOVING have O(n) time complexity

When using:

• Random access is required

• Read heavy operations