Array (Data Structure) core concept and some common question

1. Definition

An array is a collection of elements, all of which are of the same data type, stored in contiguous memory locations. Each element in the array can be accessed using its index (starting from 0).

2. Key Characteristics

• Fixed size: The size of an array is determined when it is created and cannot be changed. This makes arrays a static data structure.
• Index-based access: Elements are stored in a continuous block of memory, so accessing any element via its index is very fast (constant time, O(1)).
• Same data type: All elements in an array must be of the same type (e.g., integers, strings, etc.).

3. Common Operations and Their Time Complexities

Here are some standard operations you might be asked to perform with arrays, along with their time complexities:

Accessing an element: O(1) (direct index access, e.g., arr[3])

Updating an element: O(1) (changing the value of an element at a given index)

Searching for an element:

• Linear search: O(n) (searching one by one)
• Binary search: O(log n) (for sorted arrays)

Inserting an element:

• At the end: O(1) if the array has space.
• At a specific index: O(n)…