Data Structure & Algorithm Takeaway: Array

TipWhat is an array?

Array is representation of a linear list in which elements are stored in contiguous memory locations. Each element can be accessed directly using its index.

TipHow to store an array in computer memory?

An array is stored in contiguous memory locations. This means that all elements of the array are stored one after the other in a single block of memory.

TipIs there any requirement for the element? Why?

Yes. All elements in an array must be of the same data type, such as integers, floats, or strings, so that the block size is equal. This uniformity allows for efficient memory allocation and access, because the address of each element can be calculated directly using its index.

ImportantWhat are the time complexities of operations in an array?

The time complexities of common operations in an array are as follows ($n$ is the number of elements in the array):

• Structural operations:
  • Initialise an array with initial values: $O(n)$
  • Destroy an array: $O(1)$
  • Clear an array: $O(n)$
  • Check if the array is empty: $O(1)$
  • Get the length of the array: $O(1)$
• Element access operations:
  • Get an element by its index: $O(1)$
  • Search for an element by its value: $O(n)$
  • Traverse all elements with a specific operation on each element (such as printing): $O(n)$
• Element modification operations:
  • Update the value of an element by its index: $O(1)$
  • Insert a new element at a specific index: $O(n)$
    • Append an element to the end of the list: $O(1)$
    • Prepend an element to the beginning of the list: $O(n)$
  • Delete an element from a specific index: $O(n)$
    • Delete the last element of the list: $O(1)$
    • Delete the first element of the list: $O(n)$
• Sorting the elements: $O(n\log n)$ on average for efficient algorithms like quicksort and mergesort; $O(n^2)$ for simpler algorithms like bubble sort and insertion sort.

ImportantWhy is the time complexity $O(1)$ of get value and update operation?

Since arrays are stored in contiguous memory locations, the address of any element can be calculated directly using its index. In the following example, if we want to access x[2], we can calculate its address by $72+2\times 4=80$.

Array in RAM. Source: Snefru: Learning Programming with C

Through the address calculation, we can directly access or update the element in constant time, resulting in a time complexity of $O(1)$.

ImportantWhy is the time complexity $O(n)$ for search operation?

To search for an element in an array, we may need to check each element one by one until we find the target element or reach the end of the array. In the worst case, this requires checking all $n$ elements, resulting in a time complexity of $O(n)$.

ImportantWhy is the time complexity $O(n)$ for insert and delete operation?

Inserting or deleting an element at a specific index in an array may require shifting elements to maintain the contiguous memory layout. In the worst case, this may involve shifting all $n$ elements, resulting in a time complexity of $O(n)$.

TipWhat if the contiguous memory is occupied, when adding elements to the array?

When creating an array, its memory is pre-allocated. The size of the array must be specified at the time of creation so that a fully empty block of contiguous memory can be allocated. The array cannot grow beyond this size.

TipIs there a way to grow the array when added elements exceed its size?

There is a more flexible storage representation for linear list called dynamic array. It allows the array to grow and shrink in size as needed. Please refer to my article about dynamic array for details.

TipWhat are the pros and cons of storing linear list using array?

Pros:

• Fast access: Arrays allow for constant-time access to elements using their index, making them efficient for read operations.
• Memory efficiency: Arrays have a low memory overhead since they do not require additional pointers or metadata for each element.

Cons:

• Fixed size: The size of an array must be defined at the time of creation and cannot be changed later. This can lead to wasted memory if the array is not fully utilized or insufficient memory if the array needs to grow.
• Expensive insertions and deletions: Inserting or deleting elements in an array can be costly, as it may require shifting elements to maintain the contiguous memory layout.

WarningHow to implement an array in C and C++?

C has built-in support for arrays.

The array type in C is an implementation of the data structure array:

• Structural operations:
  • Initialise a linear list with initial values: int a[5] = {1, 2, 3, 4, 5};
  • Destroy an array: not needed, as arrays are automatically deallocated when they go out of scope.
  • Clear an array: memset(a, 0, sizeof(a)); (need to include <string.h> header)
  • Check if the array is empty: not applicable, as arrays have a fixed size.
  • Get the length of the array: sizeof(a) / sizeof(a[0]);
• Element access operations:
• Get an element : a[i] gives the $i+1$-th element;
• Search for an element by its value: not built-in, need to implement by yourself.

int search(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // Return the index if found
        }
    }
    return -1; // Return -1 if not found
}

• Traverse all elements with a specific operation on each element (such as printing):

void traverse(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

• Element modification operations:
  • Update: a[i] = value; updates the $i+1$-th element to value.
  • Insert: not built-in, need to implement by yourself.

  void insert(int arr[], int *size, int index, int value) {
      for (int i = *size; i > index; i--) {
          arr[i] = arr[i - 1]; // Shift elements to the right
      }
      arr[index] = value; // Insert the new element
      (*size)++; // Increase the size
  }

  • Delete: not built-in, need to implement by yourself.

  void delete(int arr[], int *size, int index) {
      for (int i = index; i < *size - 1; i++) {
          arr[i] = arr[i + 1]; // Shift elements to the left
      }
      (*size)--; // Decrease the size
  }

• Sorting: not built-in, need to implement by yourself or use library functions like qsort() from <stdlib.h> header.

WarningHow to implement an array in Python?

There is no built-in array type in Python that behaves exactly like arrays. The list type in Python is an advanced generic container that can be used as an linear list. List operations include all linear list operations, but they may not have the same time complexity as the array because the implementation is different.