Arrays - Data Structures

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together.

Introduction

Arrays are one of the most fundamental data structures in computer science. They provide a way to store and access multiple values of the same type efficiently.

Key Characteristics

• Fixed Size: Most arrays have a fixed size determined at declaration
• Contiguous Memory: Elements are stored in consecutive memory locations
• Index-based Access: Elements can be accessed using their index
• Homogeneous: All elements must be of the same type

Array Operations

1. Accessing Elements

Elements in an array are accessed using their index. In most programming languages, array indices start from 0.

arr = [10, 20, 30, 40, 50]
print(arr[0])  # Output: 10
print(arr[2])  # Output: 30

2. Insertion

Inserting an element at a specific position requires shifting elements.

Time Complexity: O(n) in worst case

3. Deletion

Deleting an element also requires shifting remaining elements.

Time Complexity: O(n) in worst case

4. Searching

Linear search has O(n) time complexity, while binary search on sorted arrays is O(log n).

Common Array Problems

1. Finding maximum/minimum element
2. Reversing an array
3. Rotating an array
4. Finding duplicates
5. Two-pointer technique
6. Sliding window problems

Advantages

• Fast access to elements using index
• Memory efficient
• Cache-friendly due to contiguous memory

Disadvantages

• Fixed size (in static arrays)
• Insertion/deletion is expensive
• Wasted space if array is not fully utilized

Applications

• Implementing other data structures (stacks, queues, heaps)
• Matrix representation
• String manipulation
• Dynamic programming problems