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: Index Value Memory Address 0 10 1000 1 20 1004 2 30 1008 3 40 1012 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: A new array of size 15 (10 + 50% of 10) is created. The existing 10 elements are copied into the new array. 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

Apr 20, 2025 - 06:40

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:

Index	Value	Memory Address
0	10	1000
1	20	1004
2	30	1008
3	40	1012

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:

A new array of size 15 (10 + 50% of 10) is created.
The existing 10 elements are copied into the new array.
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