Overview
An array is a data structure that stores multiple elements under one variable name. Each element is identified by an index, allowing direct access to a position. In many languages, traditional arrays contain elements of the same declared type and have a fixed length.
Purpose
Arrays make it possible to manage collections of related values efficiently. They are useful when elements need to be accessed by position or processed in sequence.
Structure
example: A = [10, 20, 30, 40, 50]; indices: 0; 1; explanation: In a zero-based indexing language, the first element is at index 0 and the last element is at index 4.
Basic operations
operation: Access; description: Retrieve an element using its index.; typicalComplexity: O(1); operation: Update; description: Replace the value at a known index.; typicalComplexity: O(1); operation: Traversal; description: Visit every element in order.; typicalComplexity: O(n); operation: Search; description: Find an element by value.; typicalComplexity: O(n) for an unsorted array; O(log n) for binary search on a suitably sorted array.; operation: Insertion; description: Add an element while maintaining the required order.; typicalComplexity: O(n) in the general case when shifting is required.; operation: Deletion; description: Remove an element and preserve the remaining sequence.; typicalComplexity: O(n) in the general case when shifting is required.
Key concepts
name: Core idea; description: The central focus of arrays is the capability described here: An array is an indexed collection of elements stored in a defined order, commonly using contiguous memory locations.; name: Problem context; description: Arrays is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using arrays, check its assumptions, input requirements, expected output, and resource constraints.
Characteristics
Elements have a defined logical order.; Each element can be accessed using an index.; Traditional arrays commonly store elements of the same type.; Many array implementations use contiguous memory.; The length of a traditional array is often fixed after creation.; Indexing rules depend on the programming language.
Complexity
operation: Access by index; time: O(1); operation: Update by index; time: O(1); operation: Traversal; time: O(n); operation: Linear search; time: O(n); operation: Binary search; time: O(log n), when the array is sorted and supports efficient indexed access.; operation: Middle insertion or deletion; time: O(n) due to shifting in the general case.