Arrays in Data Structures
An array stores elements of the same type in contiguous memory, giving constant time access by index.
- Arrays
What is an array?
An array is a collection of elements of the same data type stored in contiguous memory locations. Each element is reached through an index, and the first index is zero in most languages.
Memory layout
Because the elements sit next to each other, the address of any element is a simple calculation:
address(i) = base_address + (i * size_of_element)That is why indexing an array costs O(1).
Operations and complexity
| Operation | Time complexity |
|---|---|
| Access by index | O(1) |
| Search (unsorted) | O(n) |
| Insert at end | O(1) amortised |
| Insert at position | O(n) |
| Delete at position | O(n) |
Example
int[] numbers = {12, 7, 45, 3, 28};
int sum = 0;
for (int n : numbers) {
sum += n;
}
System.out.println("Sum = " + sum);Advantages
- Constant time random access.
- Cache friendly because of contiguous storage.
- Simple and memory efficient.
Limitations
- Fixed size in most languages.
- Insertion and deletion in the middle require shifting.
Conclusion
Arrays are the foundation on which lists, stacks, queues, heaps and hash tables are built. Understanding their cost model makes every later structure easier.