Skip to content

Array

What is an Array?

An array is a fixed-size data structure that consists of a collection of elements of same type, each identified by an index. Arrays are one of the simplest and most widely used data structures in programming. They store elements of the same type in contiguous memory locations, allowing efficient access to any element using its index. The only downside is that the memory location has to be reserved at the time of creation and cannot be changed dynamically.

Kroki

Key Characteristics

  1. Fixed Size
  2. Homogeneous Elements
  3. Contiguous Memory Allocation
  4. Indexed Access

Types of Arrays

  1. One-Dimensional Array: A linear array where elements are accessed using a single index.

    • Example: int arr[5] = {1, 2, 3, 4, 5};

  2. Multi-Dimensional Array: Arrays with more than one dimension, such as two-dimensional arrays (matrices).

    • Example: int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

  3. Dynamic Arrays: Arrays that can change size dynamically during runtime, such as vectors in C++ or ArrayList in Java.

Operations on Arrays

  1. Accessing Elements

    • Elements are accessed using their index.
    • Example: arr[2] accesses the third element in the array arr.

  2. Insertion

    • Adding an element at a specific index requires shifting elements to make space.
    • Example: To insert an element at index 2, shift elements from index 2 onwards and then place the new element.

  3. Deletion

    • Removing an element requires shifting elements to fill the gap.
    • Example: To delete an element at index 2, shift elements from index 3 onwards one position to the left.

  4. Traversal

    • Visiting each element of the array for processing.
    • Example: Using a loop to print all elements of the array.

  5. Searching

    • Finding the index of an element in the array.
    • Linear Search: O(n) time complexity.
    • Binary Search: O(log n) time complexity (requires sorted array).

  6. Sorting

    • Arranging elements in a specific order (ascending or descending).
    • Example: Using sorting algorithms like Quick Sort, Merge Sort, or Bubble Sort.

Advantages of Arrays

  1. Constant-Time Access: Elements can be accessed in O(1) time using their index.
  2. Memory Efficiency: Arrays have a low memory overhead compared to other data structures like linked lists.
  3. Cache-Friendly: Contiguous memory allocation makes arrays more cache-friendly, leading to better performance in terms of memory access speed.

Disadvantages of Arrays

  1. Fixed Size: The size of the array is fixed and cannot be changed after its creation, leading to potential wastage of memory or insufficient space.
  2. Inefficient Insertion/Deletion: Inserting or deleting elements, especially in the middle, can be inefficient as it requires shifting elements.
  3. Homogeneous Data: Arrays can only store elements of the same type, limiting flexibility.

Applications of Arrays

  1. Storing and Accessing Data: Arrays are used to store data that needs to be accessed quickly using indices.
  2. Implementation of Other Data Structures: Arrays are the foundation for implementing other data structures like stacks, queues, and hash tables.
  3. Mathematical Computations: Arrays are used in scientific computations and matrix operations.
  4. Graphics and Image Processing: Arrays are used to store pixel values and manipulate images.