Arrays

Definition

An array is a linear data structure that stores a collection of elements of the same data type in contiguous memory locations.
Each element is accessed using an index (zero-based in most programming languages).

Characteristics

• Fixed Size: The size of an array is defined at creation and cannot change (in most languages).
• Homogeneous Elements: Stores elements of the same type.
• Indexed Access: Elements can be accessed directly using an index.
• Contiguous Memory: Elements are stored sequentially in memory.

Advantages

• Fast Access: Constant time complexity O(1) for accessing an element using its index.
• Efficient Traversal: Easy to iterate through elements sequentially.
• Cache Friendly: Due to contiguous memory allocation.

Disadvantages

• Fixed Size: Cannot grow or shrink dynamically (unless using dynamic arrays like Python lists).
• Insertion & Deletion Cost: Inserting/deleting in the middle requires shifting elements → O(n).
• Memory Waste: If the allocated size is not fully used.

Operations & Complexity

Types of Arrays

• One-Dimensional Array: A simple list of elements.
• Multi-Dimensional Array: Arrays of arrays (e.g., 2D arrays like matrices).
• Dynamic Arrays: Arrays that can resize automatically (e.g., Python list, ArrayList in Java, vector in C++).

Example (in Python)

# Using Python list as a dynamic array
arr = [10, 20, 30, 40, 50]

# Access elements
print("First element:", arr[0])
print("Third element:", arr[2])

# Insert an element
arr.insert(2, 25)
print("After insertion:", arr)

# Delete an element
arr.remove(40)
print("After deletion:", arr)

# Traversal
for i in arr:
    print(i, end=" ")

Use Cases

• Storing a fixed collection of elements.
• Implementing other data structures (e.g., heaps, hash tables).
• Useful in scenarios where fast indexed access is needed.