Overview
An array is a linear data structure that collects multiple elements of the same type (usually) stored in contiguous memory locations. Elements are accessed using a numerical index.
Core Concepts
- Indexing: Most languages use zero-based indexing, where the first element is at index
0. - Contiguous Memory: Elements are stored side-by-side in memory, allowing for extremely fast access.
- Time Complexity:
- Access: $O(1)$ – Constant time to retrieve any element if the index is known.
- Search: $O(n)$ – Linear time to find a value in an unsorted array.
- Insertion/Deletion: $O(n)$ – Requires shifting other elements to maintain order.
Code Examples
// TypeScript/JavaScript
const fruits: string[] = ["Apple", "Banana", "Cherry"];
// Accessing an element
console.log(fruits[0]); // "Apple"
// Modifying an element
fruits[1] = "Blueberry";
// Adding an element
fruits.push("Date");Use Cases
- Lists: Storing a simple collection of similar items (e.g., a list of usernames).
- Buffers: Implementing queues or stacks for data processing.
- Matrices: Using multi-dimensional arrays to represent grids, images, or mathematical matrices.
Gotchas
- Off-by-One Errors: A common bug where a loop iterates one time too many or too few (e.g., trying to access
array[array.length]). - Fixed Size: In many lower-level languages (C, Java), arrays have a fixed size once declared. Dynamic arrays (like JS arrays or Python lists) handle resizing automatically but at a performance cost.
- Performance: Inserting or removing elements from the beginning or middle of a large array is expensive due to the need to shift elements.